صفحه‌ها: ۱ ۲
سلام،
دوستان اگه لطف کنن جواب سوال ۱۳۸ (دفترچه ۲، صفحه ۱۲) رو توضیح بدن ممنون میشم. تو پاسخنامه گفته جستجوی اول سطح مسیر بهینه پیدا میکنه، اما بنظر من نه اول عمق پیدا میکنه نه اول سطح
ممنون میشم دوستانی که سوال دارن راهنمایی کنند.
من سوالالت سنجش رو ندارم
اما اگه هزینه مسیر‌ها با هم برابر باشن الگوریتم Bfs مسیر بهینه رو پیدا می کنه .
[attachment=1655]اینم سوال واسه دوستانی که ندارن.
dfs فرزند چپ رو گسترش میده تا پایین، بنابراین راه حلش تو این مسئله بهینه نیست.
bfs اول چپ بعد راست رو گسترش میده بعد میاد سراغ فرزند فرزند چپ، بنابراین این هم در این مسئله نمی تونه به جواب بهینه برسه.
اگه جایی از برداشتم اشتباه راهنماییم کنید.
ممنون
من هم نظرم همون گزینه‌ی ۳ اه
راستی پیمایش BFsو dfs رو روی گراف های وزن دار چطوری عمل می کنن؟ من که جایی پیاده سازی این پیمایش‌ها رو روی گراف های وزن دار ندیدم اگه دوستان دیدن یه توضیحی بدن
سوال دیگه ای هم که هست اینکه اگه bfs اینجا راه حل بهینه رو پیدا نمیکنه پس چطور میگیم این الگوریتم بهینه است؟
الگوریتم Bfs سطح به سطح پیمایش میکنه یعنی قبل از هر راس در فاصله‌ی ۱+K تمام راس هادر فاصله k از راس شروع رو پیدا می کنه و چون با اولویت اونا رو پیمایش می کنه پس حتما تا فاصله‌ی K مسیری رو که بهینه است پیمایش می کنه.( البته زمانی که وزن یالها یکسان باشن)
bfs مسیر بهینه را پیدا می کند ولی dfs مسیر بهینه را پیدا نمی کند(در صورتی که‌تر تیب گسترش گره‌ها بر اساس حروف الفا باشه). خودشون کدوم گزینه را جواب اعلام کردند؟
(۲۳ آبان ۱۳۹۰ ۰۸:۰۳ ب.ظ)pos نوشته شده توسط: bfs مسیر بهینه را پیدا می کند ولی dfs مسیر بهینه را پیدا نمی کند(در صورتی که‌تر تیب گسترش گره‌ها بر اساس حروف الفا باشه). خودشون کدوم گزینه را جواب اعلام کردند؟
bfs کم عمق ترین هدف رو بر میگردونه که این لزوماً جواب بهینه نخواهد بود
(۲۳ آبان ۱۳۹۰ ۰۸:۱۷ ب.ظ)Masoud05 نوشته شده توسط:(23 آبان ۱۳۹۰ ۰۸:۰۳ ب.ظ)pos نوشته شده توسط: bfs مسیر بهینه را پیدا می کند ولی dfs مسیر بهینه را پیدا نمی کند(در صورتی که‌تر تیب گسترش گره‌ها بر اساس حروف الفا باشه). خودشون کدوم گزینه را جواب اعلام کردند؟
bfs کم عمق ترین هدف رو بر میگردونه که این لزوماً جواب بهینه نخواهد بود
خوب الان که حالت کلی را نخواسته. جواب را با توجه به گراف می خواد. مگه توی این گراف bfs راه حل بهینه را نمیده؟ در حالت کلی هم فکر کنم bfs فکر کنم جواب بهینه را برمیگرداندا. شما مطمئنی bfs در حالت کلی بهینه نیست؟
(۲۳ آبان ۱۳۹۰ ۰۸:۲۵ ب.ظ)pos نوشته شده توسط:ارسالم در واقع جواب شما بود . بله مطمئنم که bfs در حالت عادی بهینه نیست برای توضیح بیشتر حالتی در نظر بگیر که چند هدف داریم و هدف بهینه در عمق پایین‌تر از مابقی اهداف هست، پس bfs هدف های سطح بالاتر رو برمیگردونه .اما اگه هزینه مسیر برای هر یال یه مقدار مثبت بود و هر عمق هزینه مسیر بیشتر بشه، اونوقت کم عمق ترین هدف هدف بهینه میشه.(23 آبان ۱۳۹۰ ۰۸:۱۷ ب.ظ)Masoud05 نوشته شده توسط:(23 آبان ۱۳۹۰ ۰۸:۰۳ ب.ظ)pos نوشته شده توسط: bfs مسیر بهینه را پیدا می کند ولی dfs مسیر بهینه را پیدا نمی کند(در صورتی که‌تر تیب گسترش گره‌ها بر اساس حروف الفا باشه). خودشون کدوم گزینه را جواب اعلام کردند؟
bfs کم عمق ترین هدف رو بر میگردونه که این لزوماً جواب بهینه نخواهد بود
خوب الان که حالت کلی را نخواسته. جواب را با توجه به گراف می خواد. مگه توی این گراف bfs راه حل بهینه را نمیده؟ در حالت کلی هم فکر کنم bfs فکر کنم جواب بهینه را برمیگرداندا. شما مطمئنی bfs در حالت کلی بهینه نیست؟
Masoud05 من توضیحی که ارائه دادین رو متوجه نشدم اگه میشه واضحتر و ساده‌تر برای من بی سواد توضیح بدین
من یه توضیحی هم در مورد بهینه بودن Bfs بدم
من در پست قبلیم گفتم اگه یالها وزن یکسانی داشته باشنBfs بهینه است چون کوتاه ترین مسیر از نظر تعداد یالها از راس شروع رو بر می گردونه اینی که من گفتم درسته دیگه؟ نه؟
(۲۳ آبان ۱۳۹۰ ۰۹:۱۲ ب.ظ)ahmadnouri نوشته شده توسط: Masoud05 من توضیحی که ارائه دادین رو متوجه نشدم اگه میشه واضحتر و ساده‌تر برای من بی سواد توضیح بدین
من یه توضیحی هم در مورد بهینه بودن Bfs بدم
من در پست قبلیم گفتم اگه یالها وزن یکسانی داشته باشنBfs بهینه است چون کوتاه ترین مسیر از نظر تعداد یالها از راس شروع رو بر می گردونه اینی که من گفتم درسته دیگه؟ نه؟
شما استادین، اینی که شما میگید درسته.
اگه یالها وزن نداشت و یا وزن منفی هم داخلش باشه لزوما کم عمق ترین هدف، هدف بهینه نیست . یه مثال برا خودت بزن که چند تا هدف داخلش باشه و هدف بهینه خودت جوری انتخاب کن که عمقش از مابقی اهداف بیشتر باشه تا به چیزی که گفتم بررسی . البته داخل کتاب پوران این نکته رو مستقیماً آورده.( فصل حل مسئله با استفاده از جستجو )
خودشون گفتن bfs. ولی من هنوزم معتقدم نه bfs نه dfs تو این سوال جواب بهینه نمیدن.( شاید چون یالها وزن دارند)
من جواب سوالم هنوز نگرفتم!
توی جستجوی عمقی اگر انتخاب یالها به ترتیب حروف الفبا باشه میشه SADCG که مسیر بهینه نیست. ولی در جستجوی اول سطح ابتدا S انتخاب میشه بعد فرزندانش که میشه AB و در سطح بعد ابتدا D بعد G که برابر با هدف هست پس مسیر میشه SAG که مسیر بهینه هست.
استدلال شما درسته ولی خب تو صورت سوال اشاره ای به انتخاب بر اساس حروف الفبا نشده، پیش فرض ذهنی هم فرزند چپ اول بعد راست هستش.
ممنون از پاسختون