تالار گفتمان مانشت
کوتاه ترین مسیر در گراف - نسخه‌ی قابل چاپ

کوتاه ترین مسیر در گراف - Sanazzz - 06 فروردین ۱۳۹۸ ۰۴:۵۵ ب.ظ

سلام
میشه لطفا توضیح بدین چرا با dfs نمیشه این سوال رو حل کرد [تصویر:  467115_ipnc_p_20190326_165336_vhdr_on_1.jpg]

RE: کوتاه ترین مسیر در گراف - ph0en1x - 06 فروردین ۱۳۹۸ ۰۸:۴۴ ب.ظ

(۰۶ فروردین ۱۳۹۸ ۰۴:۵۵ ب.ظ)Sanazzz نوشته شده توسط:  سلام
میشه لطفا توضیح بدین چرا با dfs نمیشه این سوال رو حل کرد [تصویر:  467115_ipnc_p_20190326_165336_vhdr_on_1.jpg]

چون dfs اصلاً کوتاه‌ترین مسیر رو پیدا نمیکنه. مثلاً اگه از a به b و c، و از b به c مسیر داشته باشیم و ترتیب جستجو رو در شرایط مساوی به ترتیب حروف الفبا در نظر بگیریم، درخت پوشای حاصل از dfs با شروع از a میشه a -> b -> c؛ در حالی که کوتاه‌ترین مسیر از a به c یه یال داره!
نمیدونم تونستم منظورمو برسونم یا نه، اگه متوجه نشدید بگید تصویر بکشم.

RE: کوتاه ترین مسیر در گراف - mreinollahi - 06 فروردین ۱۳۹۸ ۱۰:۰۷ ب.ظ

اگر کتاب هوش مصنوعی را مطالعه کنید متوجه میشید

فرض کنید جواب مسئله گره ۲ و۳ در شکل زیر است. که ۲ مسیر کوتاه و بهینه است

dfs ابتدا سمت چپ را تا انتها جستجو می کند و جواب در آخرین سطح را بر می گرداند که یعنس ۳

اما bfs جواب را سطح به سطح جستجو میکنه و ۲ رو بر میگردونه

[تصویر:  467118_binary_tree_search.png]

RE: کوتاه ترین مسیر در گراف - Sanazzz - 07 فروردین ۱۳۹۸ ۰۲:۵۷ ق.ظ

(۰۶ فروردین ۱۳۹۸ ۰۸:۴۴ ب.ظ)ph0en1x نوشته شده توسط:  
(06 فروردین ۱۳۹۸ ۰۴:۵۵ ب.ظ)Sanazzz نوشته شده توسط:  سلام
میشه لطفا توضیح بدین چرا با dfs نمیشه این سوال رو حل کرد [تصویر:  467115_ipnc_p_20190326_165336_vhdr_on_1.jpg]

چون dfs اصلاً کوتاه‌ترین مسیر رو پیدا نمیکنه. مثلاً اگه از a به b و c، و از b به c مسیر داشته باشیم و ترتیب جستجو رو در شرایط مساوی به ترتیب حروف الفبا در نظر بگیریم، درخت پوشای حاصل از dfs با شروع از a میشه a -> b -> c؛ در حالی که کوتاه‌ترین مسیر از a به c یه یال داره!
نمیدونم تونستم منظورمو برسونم یا نه، اگه متوجه نشدید بگید تصویر بکشم.

خیلی خیلی ممنونممم
تشکرات ویژهههههههه

(۰۶ فروردین ۱۳۹۸ ۱۰:۰۷ ب.ظ)mreinollahi نوشته شده توسط:  اگر کتاب هوش مصنوعی را مطالعه کنید متوجه میشید

فرض کنید جواب مسئله گره ۲ و۳ در شکل زیر است. که ۲ مسیر کوتاه و بهینه است

dfs ابتدا سمت چپ را تا انتها جستجو می کند و جواب در آخرین سطح را بر می گرداند که یعنس ۳

اما bfs جواب را سطح به سطح جستجو میکنه و ۲ رو بر میگردونه

[تصویر:  467118_binary_tree_search.png]

بی نهایت تشکر
ممنونممممم