سلام دوستان.میشه این سوال رو جواب بدید؟
ایا جستجوی سطحی این گراف جواب بهینه میده؟
فکر نکنم
اگه اشتباه نکنم هزینه ی جست و جوی سطحی این گراف ۱۰
البته با جست و جوی عمقی هم بهینه نیست
(۱۷ آذر ۱۳۹۱ ۱۰:۰۲ ب.ظ)nina69 نوشته شده توسط: فکر نکنم
اگه اشتباه نکنم هزینه ی جست و جوی سطحی این گراف ۱۰
ولی با جست و جوی عمقی ۴
خب منم نظرم همینه که با سطحی بهینه نیست البته با عمقی هم بهیبه نیست به نظرم.ولی در کتاب سنجش طلایی گفته با bfsبهینه است و مسیر SAGرا طی میکنه........میشه درخت معادلش رو برام بکشید؟شاید من اشتباه رسم میکنم...
رشتم هوش نیست ولی پیمایش تو الگوریتم فکر کنم به این شکله.
پیمایش سطحی از چپ بخون
SABDGC
پیمایش عمقی از چپ بخون
SADCGB
من اول یک برداشت دیگه کرده بودم از مسئله ولی الان این جواب به ذهنم اومد:
در پیمایش 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 از صف خارج کنین.
سوال گفته bfs مسیر بهینه میده ؟دنبال مسیر بهینه نیستیم فقط میخواد ببینه bfsچه مسیری میده؟حالا اون بهینه هست یا نه.bfs هم طبق شکل پیوست بسط میده نود ها رو.
ممنونم از همه .مشکلم حل شد.
(۱۷ آذر ۱۳۹۱ ۱۱:۵۵ ب.ظ)farhadk نوشته شده توسط: من طریقه پیمایشو میگم ببینین مشکلتون حل می شه.من توضیحی که شما دادید رو میدونستم.ولی چون صورت سئوال در مورد مسیر بهینه بود و در بخش درس هوش هم مطرح شده بود ، مسیر بهینه رو ذکر کردم.
روش پیمایش و ترتیب گرهها جزو مباحث طراحی الگوریتم هست و توی هوش مطرح نمیشه.
ولی اگر منظور سئوال نحوه پیمایش گرهها بوده جوابی که دادید درسته
بعدا این سئوال به بخش طراحی الگوریتم منتقل خواهد شد