سلام دوستان امیدوارم حالتون خوب باشه
دوستان سوال من در مورد تمرین ۱۳ فصل برنامه ریزی پویا کتاب Kleinberg است.
در این سوال فرض شده ما تعدادی شرکت داریم که بین این شرکت ها سهام رد و بدل میشه با نرخ ri,j ، ما باید بتونیم یک دور پیدا کنیم که بعد از بازگشت به شرکت اول سهام ما بیشتر از ۱ شده باشه و سود کرده باشیم .
چندین جا مطرح شده اگر سهم ها رو به صورت منفی لگاریتم در نظر بگیریم و بعد الگوریتم بلمن فورد رو اجرا کنیم جواب میده اما من میخواستم بدونم چطور میشه اون دور رو پیدا کرد ؟ متشکرم
(۰۳ اردیبهشت ۱۳۹۴ ۰۸:۲۹ ب.ظ)ashy نوشته شده توسط: چندین جا مطرح شده اگر سهم ها رو به صورت منفی لگاریتم در نظر بگیریم و بعد الگوریتم بلمن فورد رو اجرا کنیم جواب میده اما من میخواستم بدونم چطور میشه اون دور رو پیدا کرد ؟ متشکرم
سلام
تو این مسئله ما هیچ کاری با وزنها نداریم (جز ضرب کردن و مقایسه‌ی حاصل با ۱).
همون طور که خودتون هم مطرح کردین مسئله فقط تکرار روی حلقه‌های این گرافه. نکته اینجاست که یک گراف میتونه حلقه‌های خیلی زیادی داشته باشه اما خوشبختانه لازم نیست که همه‌ی حلقه‌ها بررسی بشن.
تنها کافیه روی گراف جستجوی اول عمق انجام بشه و اگه در بین حلقه‌های حاصل از back edgeهای این پیمایش پاسخی پیدا نشه، تضمین میشه که حلقه‌ی فرصت نداریم؛ چون این حلقه‌ها بنیادی هستند و همه‌ی حلقه‌های دیگه از روی اینها ساخته میشن.