سلام
میشه لطفا توضیح بدین چرا با dfs نمیشه این سوال رو حل کرد
![[تصویر: 467115_ipnc_p_20190326_165336_vhdr_on_1.jpg]](https://img.manesht.ir/467115_ipnc_p_20190326_165336_vhdr_on_1.jpg)
(۰۶ فروردین ۱۳۹۸ ۰۴:۵۵ ب.ظ)Sanazzz نوشته شده توسط: سلام
میشه لطفا توضیح بدین چرا با dfs نمیشه این سوال رو حل کرد
چون dfs اصلاً کوتاه‌ترین مسیر رو پیدا نمیکنه. مثلاً اگه از a به b و c، و از b به c مسیر داشته باشیم و ترتیب جستجو رو در شرایط مساوی به ترتیب حروف الفبا در نظر بگیریم، درخت پوشای حاصل از dfs با شروع از a میشه a -> b -> c؛ در حالی که کوتاه‌ترین مسیر از a به c یه یال داره!
نمیدونم تونستم منظورمو برسونم یا نه، اگه متوجه نشدید بگید تصویر بکشم.
اگر کتاب هوش مصنوعی را مطالعه کنید متوجه میشید
فرض کنید جواب مسئله گره ۲ و۳ در شکل زیر است. که ۲ مسیر کوتاه و بهینه است
dfs ابتدا سمت چپ را تا انتها جستجو می کند و جواب در آخرین سطح را بر می گرداند که یعنس ۳
اما bfs جواب را سطح به سطح جستجو میکنه و ۲ رو بر میگردونه
![[تصویر: 467118_binary_tree_search.png]](https://img.manesht.ir/467118_binary_tree_search.png)
(۰۶ فروردین ۱۳۹۸ ۰۸:۴۴ ب.ظ)ph0en1x نوشته شده توسط:(06 فروردین ۱۳۹۸ ۰۴:۵۵ ب.ظ)Sanazzz نوشته شده توسط: سلام
میشه لطفا توضیح بدین چرا با dfs نمیشه این سوال رو حل کرد
چون dfs اصلاً کوتاه‌ترین مسیر رو پیدا نمیکنه. مثلاً اگه از a به b و c، و از b به c مسیر داشته باشیم و ترتیب جستجو رو در شرایط مساوی به ترتیب حروف الفبا در نظر بگیریم، درخت پوشای حاصل از dfs با شروع از a میشه a -> b -> c؛ در حالی که کوتاه‌ترین مسیر از a به c یه یال داره!
نمیدونم تونستم منظورمو برسونم یا نه، اگه متوجه نشدید بگید تصویر بکشم.
خیلی خیلی ممنونممم
تشکرات ویژهههههههه
(۰۶ فروردین ۱۳۹۸ ۱۰:۰۷ ب.ظ)mreinollahi نوشته شده توسط: اگر کتاب هوش مصنوعی را مطالعه کنید متوجه میشید
فرض کنید جواب مسئله گره ۲ و۳ در شکل زیر است. که ۲ مسیر کوتاه و بهینه است
dfs ابتدا سمت چپ را تا انتها جستجو می کند و جواب در آخرین سطح را بر می گرداند که یعنس ۳
اما bfs جواب را سطح به سطح جستجو میکنه و ۲ رو بر میگردونه
بی نهایت تشکر
ممنونممممم