تالار گفتمان مانشت

سلام
میشه لطفا توضیح بدین چرا با dfs نمیشه این سوال رو حل کرد

(06 فروردین 1398 04:55 ب.ظ)Sanazzz نوشته شده توسط: [ -> ]سلام
میشه لطفا توضیح بدین چرا با dfs نمیشه این سوال رو حل کرد

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

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

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

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

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

(06 فروردین 1398 08:44 ب.ظ)ph0en1x نوشته شده توسط: [ -> ]

(06 فروردین 1398 04:55 ب.ظ)Sanazzz نوشته شده توسط: [ -> ]سلام
میشه لطفا توضیح بدین چرا با dfs نمیشه این سوال رو حل کرد

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

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

---

(06 فروردین 1398 10:07 ب.ظ)mreinollahi نوشته شده توسط: [ -> ]اگر کتاب هوش مصنوعی را مطالعه کنید متوجه میشید

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

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

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

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