زمان کنونی: ۲۳ آذر ۱۴۰۳, ۱۲:۴۱ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

کوتاه ترین مسیر در گراف

ارسال:
  

Sanazzz پرسیده:

کوتاه ترین مسیر در گراف

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

۰
ارسال:
  

ph0en1x پاسخ داده:

RE: کوتاه ترین مسیر در گراف

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

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

ارسال:
  

Sanazzz پاسخ داده:

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 یه یال داره!
نمیدونم تونستم منظورمو برسونم یا نه، اگه متوجه نشدید بگید تصویر بکشم.

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

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

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

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

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

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

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

۰
ارسال:
  

mreinollahi پاسخ داده:

RE: کوتاه ترین مسیر در گراف

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

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

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

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

[تصویر:  467118_binary_tree_search.png]
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  فراخوان داستان کوتاه fas ۱ ۳,۰۳۳ ۰۱ مهر ۱۳۹۹ ۱۱:۰۳ ق.ظ
آخرین ارسال: mehrad1011
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۲,۱۴۰ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  تعداد مسیرها در گراف ss311 ۰ ۲,۰۴۶ ۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ
آخرین ارسال: ss311
  انخاب مسیر آینده ؟ آینده دکترا چه خواهد شد ؟ shivap ۱۰ ۱۱,۴۴۸ ۰۲ آذر ۱۳۹۸ ۱۲:۳۶ ق.ظ
آخرین ارسال: WILL
  پر استفاده ترین مدل های هواپیما در ایران abolfazlda ۱ ۳,۰۵۴ ۱۱ آبان ۱۳۹۸ ۰۱:۴۶ ب.ظ
آخرین ارسال: marvelous
Rainbow فروش کامل ترین منابع کنکور ارشد کامپیوتر maneshti_sharifi ۶ ۵,۳۴۱ ۱۸ شهریور ۱۳۹۸ ۰۶:۲۰ ب.ظ
آخرین ارسال: Masoud05
  طراحی گرافیکی simaakbari ۰ ۲,۴۹۲ ۱۶ خرداد ۱۳۹۸ ۰۴:۵۴ ب.ظ
آخرین ارسال: simaakbari
  کتاب خوب در باره نظریه گراف ماهی ۲۵۸ ۰ ۲,۰۱۰ ۲۸ شهریور ۱۳۹۷ ۱۲:۲۸ ب.ظ
آخرین ارسال: ماهی ۲۵۸
Rainbow رنگین‌ترین شهرها در سرتاسر دنیا αɾια ۱۰ ۵,۱۷۹ ۰۲ تیر ۱۳۹۷ ۱۰:۰۱ ق.ظ
آخرین ارسال: hivakish
  بهترین و کاربردی ترین متد آموزش زبان !؟ khayyam ۰ ۱,۸۲۶ ۰۱ تیر ۱۳۹۷ ۱۲:۴۴ ب.ظ
آخرین ارسال: khayyam

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close