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

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

ارسال:
  

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مسیر ساده با کمترین تعداد یال - IT 86 delete4all ۴ ۷۰۶ ۲۳ اسفند ۱۳۹۵ ۰۸:۳۰ ق.ظ
آخرین ارسال: delete4all
  گراف در طراحی الگوریتم Rehe1994 ۱ ۷۸۴ ۱۵ اسفند ۱۳۹۵ ۱۰:۵۲ ب.ظ
آخرین ارسال: alireza01
  وزن منفی در گراف و الگوریتم دایجسترا Rehe1994 ۱ ۷۱۴ ۲۷ دى ۱۳۹۵ ۱۲:۵۸ ب.ظ
آخرین ارسال: Jooybari
  کمترین هزینه در ارتباط گره های گراف ها kamal3401 ۳ ۹۶۳ ۱۷ خرداد ۱۳۹۵ ۱۱:۵۷ ب.ظ
آخرین ارسال: Behnam‌
  پیدا کردن با ارزش ترین مسیر در یک ماتریس kamal3401 ۵ ۱,۳۸۰ ۱۶ خرداد ۱۳۹۵ ۰۹:۳۳ ب.ظ
آخرین ارسال: Behnam‌
  خلوت بودن یا شلوغ بودن گراف behnazmahrokh ۴ ۷۷۷ ۰۷ اردیبهشت ۱۳۹۵ ۰۹:۳۷ ب.ظ
آخرین ارسال: behnazmahrokh
  گراف naserqw ۱ ۶۰۷ ۰۵ اردیبهشت ۱۳۹۵ ۰۲:۵۸ ب.ظ
آخرین ارسال: sixsixsix
  سوال گراف پوران Baranmalihe ۶ ۱,۳۷۸ ۲۹ دى ۱۳۹۴ ۰۴:۲۷ ب.ظ
آخرین ارسال: Baranmalihe
  توضیح در مورد ارایه طولانی ترین پیشوند مشترک (lcp) mahtab engineer ۰ ۵۵۳ ۰۷ آذر ۱۳۹۴ ۰۳:۰۷ ب.ظ
آخرین ارسال: radman@123
  پیدا کردن چرخه فرصت در گراف ashy ۱ ۹۰۰ ۰۴ اردیبهشت ۱۳۹۴ ۱۲:۱۷ ق.ظ
آخرین ارسال: MShariati

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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