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

پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور

ارسال:
  

Aurora پرسیده:

پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور

پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور از چه مرتبه ای است؟ یعنی از یک راس مبدا شروع کنیم و به راس مقصد برسیم.
میشه در زمان چند جمله ای حلش کرد؟

۰
ارسال:
  

atharrashno پاسخ داده:

پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور

لینک مشاهده کردم دوست من:
جوای اون مساله را را تو تاپیگش میدم حتما نظرتون را بگید اما به نظرتون میشه کلا با عمقی و سطحی بهترین مسیر را تو گراف های جهت داری پیدا کرد اگر ترتیب یالها صعودی نباشه؟
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

atharrashno پاسخ داده:

پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور

در حافظه‌ام دارم که استاد سید جوادی فرمودند چون دور نداریم میتونیم روی راس با بیشترین هزینه پیمایش اول عمق بزنیم و در پیمایش اول عمق هم هزینه o(e+n) پیچیدگی ما می باشد
پس درجه پیدا کردن طولانی ترین مسیر چند جمله ای می باشد

منطقی هم می باشد لکن دوستان دیگر تایید کنند...
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

Aurora پاسخ داده:

RE: پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور

ممنون ولی مثلا در شکل زیر چطوری با پیمایش اول عمق می شود مسیر را پیدا کرد؟ با شروع از بالاترین راس؟

۰
ارسال:
  

atharrashno پاسخ داده:

پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور

خوب این قاعده برای گراف بدون جهت بود اما یک نکته وقتی گراف با دور جهت دار داشته باشیم میشه با تغییر در بلمن فورد طولانی ترین مسیر را بدست اورد یعنی o(n^3 حالا که گرافمون بدون دور هست خوب قطعا پیچیدگی از این کمتر میشه


اگر بتونیم جواب این سوال شما را بدیم در حقیقت این سوال را هم جواب دادیم چرا که در این جا هم دنبال بیشترین طول هستیم و مثلث را میشه به گراف جهت دار تبدیل کرد و با توجه به گزینه‌ها قطعا ج.واب چند جمله ای خواهد بود

[تصویر:  66948_1_1379095321.JPG]
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

Aurora پاسخ داده:

RE: پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور

بله اتفاقا من هم به دنبال این سوال شما رسیدم به این مطلب.

۰
ارسال:
  

atharrashno پاسخ داده:

پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور

کتاب اقای قلزم گفته اگر در گراف جهت دار بدون دور وزن یال‌ها از مبدا به پایین صعودی باشه کوتاه ترین مسیر و طولانی ترین مسیر با o(n+e)پیدا میشه (اینو بعد از مطالب دکستری به عنوان تمرین داده خوب یعنی مرتبطه دیگه نه؟)
نظر شما چیه
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

Aurora پاسخ داده:

RE: پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور

فکر کنم منظورش topological sort هست. ولی اینجا که به صورت صعودی مرتب نیست ؟
شکلش این طوری میشه درسته؟

۰
ارسال:
  

atharrashno پاسخ داده:

پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور

نه چرا فک کردی منظورش اینه؟
این شکل که شما کشیدی صعودی نیست که
این نکته اقای قلزم به خاطر تو این تاپیگ گفتم که بگم بله طولانی ترین مسیر گراف جهت دار در زمان چند جمله ای قابل حله اما به شرط صعودی بودن یالها

حالا شکل پست ۳ را نمیشه حل کرد چون صعودی نیست
این سوال شما سوال من هم هست کاش دوستان جواب بدن
مشاهده‌ی وب‌سایت کاربر

۰
ارسال: #۱۰
  

Aurora پاسخ داده:

RE: پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور

این‌ها رو نگاه کنید.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

صفحه ۱۷ pdf
quiz2-sol.pdf
اندازه فایل: ۱۹۱/۵۷ KB

فکر کنم اگه وزن همه‌ی یال‌ها منفی بود مییشد حل کرد . همه‌ی یال‌ها رو در -۱ ضرب می کردیم با دیکسترا کوتاهترین مسیر رو پیدا می کردیم. بعد هم در آخر جواب آخر را در -۱ ضرب می کردیم.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  ازدواج دور از جوانان، جوانان دور از ازدواج (هرچه می خواهد دل تنگت بگو...) morweb ۲,۶۹۵ ۶۰۳,۹۱۵ ۲۱ مرداد ۱۴۰۲ ۰۷:۴۴ ب.ظ
آخرین ارسال: gogooli
  درخواست راهنمایی جهت اتمام پایان نامه Maryam-X ۰ ۰ ۰۶ شهریور ۱۴۰۱ ۰۸:۵۸ ق.ظ
آخرین ارسال: Maryam-X
  پیدا کردن دستگیره manager_66 ۵ ۴,۳۵۳ ۲۸ آذر ۱۴۰۰ ۱۲:۴۴ ب.ظ
آخرین ارسال: blackhalo1989
  دکتری بدون آزمون wskf ۱ ۲,۱۳۲ ۱۷ بهمن ۱۳۹۹ ۱۱:۴۴ ب.ظ
آخرین ارسال: hmaryam567
  گرامر زبان انگلیسی:صفت های ed و ing دار cyruskingsolomon ۳ ۲,۶۱۸ ۱۵ بهمن ۱۳۹۹ ۰۶:۴۱ ب.ظ
آخرین ارسال: cyruskingsolomon
  تا به حال شده خدا فرصت زندگی کردن دوباره رو بهت بده؟مرگ از جلوی چشمات رد شده؟ abraham ۲۱ ۱۴,۴۹۷ ۲۰ دى ۱۳۹۹ ۱۰:۵۶ ب.ظ
آخرین ارسال: raam
  جایی برای پیدا کردن توابع آماده جاوااسکریپت f.b ۷ ۴,۰۰۹ ۲۰ آذر ۱۳۹۹ ۰۴:۰۸ ب.ظ
آخرین ارسال: calm
  پیدا کردن موضوع پایان نامه k1.technology ۲ ۷,۷۴۲ ۲۱ خرداد ۱۳۹۹ ۱۲:۵۴ ب.ظ
آخرین ارسال: bankabzar
  دوره آموزشی آنلاین Hadoop و Apache Spark به زبان فارسی Happiness.72 ۰ ۲,۲۳۴ ۰۲ خرداد ۱۳۹۹ ۱۰:۳۸ ب.ظ
آخرین ارسال: Happiness.72
  انتقال داده از ص a به ص b بدون php با js amirmtf ۰ ۱,۹۵۴ ۰۲ اردیبهشت ۱۳۹۹ ۱۲:۱۷ ب.ظ
آخرین ارسال: amirmtf

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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