رشتم هوش نیست ولی پیمایش تو الگوریتم فکر کنم به این شکله.
پیمایش سطحی از چپ بخون
SABDGC

پیمایش عمقی از چپ بخون
SADCGB

فکر نکنم
اگه اشتباه نکنم هزینه ی جست و جوی سطحی این گراف ۱۰
البته با جست و جوی عمقی هم بهینه نیست

(۱۷ آذر ۱۳۹۱ ۱۰:۰۲ ب.ظ)nina69 نوشته شده توسط:  فکر نکنم
اگه اشتباه نکنم هزینه ی جست و جوی سطحی این گراف ۱۰
ولی با جست و جوی عمقی ۴

خب منم نظرم همینه که با سطحی بهینه نیست البته با عمقی هم بهیبه نیست به نظرم.ولی در کتاب سنجش طلایی گفته با bfsبهینه است و مسیر SAGرا طی میکنه........میشه درخت معادلش رو برام بکشید؟شاید من اشتباه رسم میکنم...

من اول یک برداشت دیگه کرده بودم از مسئله ولی الان این جواب به ذهنم اومد:
در پیمایش bfs اول همه گرههای هم سطح (که والد یکسان دارند) بسط داده میشن.پس در اینجا از s شروع میکیم و گرههای aوb را بسط میدیم. بین aوb هم کم هزینه ترین گره یعنی a را انتخاب میکنیم.بعد گرههای متصل به a را بسط میدیم ، که گرههای dوg هستند . که g هم هدف است . هزینه جستجو bfs هم ۴ است

(۱۷ آذر ۱۳۹۱ ۱۱:۰۵ ب.ظ)fatima1537 نوشته شده توسط:  من اول یک برداشت دیگه کرده بودم از مسئله ولی الان این جواب به ذهنم اومد:
در پیمایش bfs اول همه گرههای هم سطح (که والد یکسان دارند) بسط داده میشن.پس در اینجا از s شروع میکیم و گرههای aوb را بسطمیدیم. بین aوb هم کم هزینه ترین گره یعنی a را انتخاب میکنیم.بعد گرههای متصل به a را بسط میدیم ، که گرههای dوg هستند . که g هم هدف است . هزینه جستجو bfs هم ۴ است

این پیمایش امکان نداره چون تو پیمایش سطحی ما برای پیمایش از صف استفاده میکنیم.
تو پیمایش سطحی امکان پیمایش SAG پشت سر هم نیست.
چون وقتی S شناسایی شد A و B در صف قرار می گیرن.
بعد از شناسایی A بچه های A بعد از B در صف قرار می گیرن. پس امکان نداره G زودتر از B در پیمایش سطحی خونده بشه.

دقیقا منم مشکلم همینه..در BFS حتما اول B دیده میشه چون با A هم سطحه.

(۱۷ آذر ۱۳۹۱ ۱۱:۱۳ ب.ظ)aida fazeli نوشته شده توسط:  دقیقا منم مشکلم همینه..در BFS حتما اول B دیده میشه چون با A هم سطحه.

کتابهای تست اشتباه زیاد دارن.
این کتاب هم اشتباهاش طلاییه.

(۱۷ آذر ۱۳۹۱ ۱۱:۱۳ ب.ظ)aida fazeli نوشته شده توسط:  در BFS حتما اول B دیده میشه چون با A هم سطحه.

هم سطح بودن دلیلی بر زودتر دیده شدن نیست . اگر هم زودتر دیده بشه تاثیری توی انتخابش نداره چون میخواد کم هزینه ترین گره رو انتخاب کنه که a هست

(۱۷ آذر ۱۳۹۱ ۱۱:۱۰ ب.ظ)farhadk نوشته شده توسط:  این پیمایش امکان نداره چون تو پیمایش سطحی ما برای پیمایش از صف استفاده میکنیم.
تو پیمایش سطحی امکان پیمایش SAG پشت سر هم نیست.
چون وقتی S شناسایی شد A و B در صف قرار می گیرن.
بعد از شناسایی A بچه های A بعد از B در صف قرار می گیرن. پس امکان نداره G زودتر از B در پیمایش سطحی خونده بشه.

من هم میدونم در پیمایش سطحی اول همه گرههای هم سطح در صف قرار میگیرند
ولی اینجا منظور سئوال مسیر بهینه بود (نه درخت پیمایش) و من هم مسیر رو ذکر کردم . وقتی توی پیمایش سطحی گرههای هم سطح به ترتیب پیمایش شدند گرهی که هزینه کمتری داره انتخاب میشه ، که در اینجا a هست ، و مجددا a بسط داده میشه و گره هدف انتخاب میشه

(۱۷ آذر ۱۳۹۱ ۱۱:۴۱ ب.ظ)fatima1537 نوشته شده توسط:  من هم میدونم در پیمایش سطحی اول همه گرههای هم سطح در صف قرار میگیرند
ولی اینجا منظور سئوال مسیر بهینه بود (نه درخت پیمایش) و من هم مسیر رو ذکر کردم . وقتی توی پیمایش سطحی گرههای هم سطح به ترتیب پیمایش شدند گرهی که هزینه کمتری داره انتخاب میشه ، که در اینجا a هست ، و مجددا a بسط داده میشه و گره هدف انتخاب میشه

خودتون هم دارین می گین اول باید گره های هم سطح پیمایش بشن.
من طریقه پیمایشو میگم ببینین مشکلتون حل می شه.
S شناسایی می شه صف به شکل زیره از چپ
AB

A شناسایی می شه صف به شکل زیره از چپ
BDG

B شناسایی می شه چیزی به صف اضافه نمی شه چون G قبلا شناسایی شده صف به شکل زیره از چپ
DG
D شناسایی می شه صف به شکل زیره از چپ
DGC
بقیه هم به ترتیب از صف میان بیرون

---

(۱۷ آذر ۱۳۹۱ ۱۱:۴۱ ب.ظ)fatima1537 نوشته شده توسط:  هم سطح بودن دلیلی بر زودتر دیده شدن نیست . اگر هم زودتر دیده بشه تاثیری توی انتخابش نداره چون میخواد کم هزینه ترین گره رو انتخاب کنه که a هست

اینجا دارین اشتباه می کنین.
اگه زودتر دیده بشه می ره تو صف اونوقت موقع خارج شدن از صف نمی تونین G را قبل از B از صف خارج کنین.

از همه دوستان ممنون.ایشالا همتون تک رقمی بشید.

(۱۷ آذر ۱۳۹۱ ۱۱:۵۵ ب.ظ)farhadk نوشته شده توسط:  من طریقه پیمایشو میگم ببینین مشکلتون حل می شه.

من توضیحی که شما دادید رو میدونستم.ولی چون صورت سئوال در مورد مسیر بهینه بود و در بخش درس هوش هم مطرح شده بود ، مسیر بهینه رو ذکر کردم.
روش پیمایش و ترتیب گرهها جزو مباحث طراحی الگوریتم هست و توی هوش مطرح نمیشه.
ولی اگر منظور سئوال نحوه پیمایش گرهها بوده جوابی که دادید درسته
بعدا این سئوال به بخش طراحی الگوریتم منتقل خواهد شد