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

پیدا کردن چرخه فرصت در گراف

ارسال:
  

ashy پرسیده:

پیدا کردن چرخه فرصت در گراف

سلام دوستان امیدوارم حالتون خوب باشه
دوستان سوال من در مورد تمرین ۱۳ فصل برنامه ریزی پویا کتاب Kleinberg است.
در این سوال فرض شده ما تعدادی شرکت داریم که بین این شرکت ها سهام رد و بدل میشه با نرخ ri,j ، ما باید بتونیم یک دور پیدا کنیم که بعد از بازگشت به شرکت اول سهام ما بیشتر از ۱ شده باشه و سود کرده باشیم .
چندین جا مطرح شده اگر سهم ها رو به صورت منفی لگاریتم در نظر بگیریم و بعد الگوریتم بلمن فورد رو اجرا کنیم جواب میده اما من میخواستم بدونم چطور میشه اون دور رو پیدا کرد ؟ متشکرم
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

MShariati پاسخ داده:

RE: پیدا کردن چرخه فرصت در گراف

(۰۳ اردیبهشت ۱۳۹۴ ۰۸:۲۹ ب.ظ)ashy نوشته شده توسط:  چندین جا مطرح شده اگر سهم ها رو به صورت منفی لگاریتم در نظر بگیریم و بعد الگوریتم بلمن فورد رو اجرا کنیم جواب میده اما من میخواستم بدونم چطور میشه اون دور رو پیدا کرد ؟ متشکرم

سلام
تو این مسئله ما هیچ کاری با وزنها نداریم (جز ضرب کردن و مقایسه‌ی حاصل با ۱).
همون طور که خودتون هم مطرح کردین مسئله فقط تکرار روی حلقه‌های این گرافه. نکته اینجاست که یک گراف میتونه حلقه‌های خیلی زیادی داشته باشه اما خوشبختانه لازم نیست که همه‌ی حلقه‌ها بررسی بشن.

تنها کافیه روی گراف جستجوی اول عمق انجام بشه و اگه در بین حلقه‌های حاصل از back edgeهای این پیمایش پاسخی پیدا نشه، تضمین می‌شه که حلقه‌ی فرصت نداریم؛ چون این حلقه‌ها بنیادی هستند و همه‌ی حلقه‌های دیگه از روی اینها ساخته میشن.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پیدا کردن دستگیره manager_66 ۵ ۴,۳۵۹ ۲۸ آذر ۱۴۰۰ ۱۲:۴۴ ب.ظ
آخرین ارسال: blackhalo1989
Information راهنمایی برای فرصت باقیمانده تا کنکور ۱۴۰۰ marge_setare ۷ ۵,۰۶۵ ۱۰ بهمن ۱۳۹۹ ۱۰:۴۸ ق.ظ
آخرین ارسال: fatemehbin
  تا به حال شده خدا فرصت زندگی کردن دوباره رو بهت بده؟مرگ از جلوی چشمات رد شده؟ abraham ۲۱ ۱۴,۵۱۰ ۲۰ دى ۱۳۹۹ ۱۰:۵۶ ب.ظ
آخرین ارسال: raam
  جایی برای پیدا کردن توابع آماده جاوااسکریپت f.b ۷ ۴,۰۱۲ ۲۰ آذر ۱۳۹۹ ۰۴:۰۸ ب.ظ
آخرین ارسال: calm
  پیدا کردن موضوع پایان نامه k1.technology ۲ ۷,۷۴۶ ۲۱ خرداد ۱۳۹۹ ۱۲:۵۴ ب.ظ
آخرین ارسال: bankabzar
  فرصت استفاده از استعداد برای ورودی دکتری wskf ۳ ۲,۹۵۸ ۲۴ فروردین ۱۳۹۹ ۰۵:۵۷ ب.ظ
آخرین ارسال: wskf
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۱,۸۹۰ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  مسدود کردن سایت و نرم افزار تلگرام wiisconsin ۶ ۶,۴۷۳ ۲۴ بهمن ۱۳۹۸ ۰۵:۳۸ ق.ظ
آخرین ارسال: one hacker alone
  تعداد مسیرها در گراف ss311 ۰ ۱,۷۹۳ ۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ
آخرین ارسال: ss311
  طراحی گرافیکی simaakbari ۰ ۲,۲۴۳ ۱۶ خرداد ۱۳۹۸ ۰۴:۵۴ ب.ظ
آخرین ارسال: simaakbari

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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