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

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

ارسال:
  

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]
نقل قول این ارسال در یک پاسخ



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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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