جواب سوال ۷ تمرین الگوریتم تقریبی

گراف جهت‌داری داده شده است که یالهای آن علاوه بر طول، وزن هم دارند. می‌خواهیم به ازای دو رأس مشخص s و t مسیر با کمترین هزینه از s به t را پیدا کنیم که طول آن از L بیشتر نباشد.

ما حل مسأله را در حالتی که طول همه‌ی یالها برابر باشند بلدیم: کوتاهترین مسیر را روی وزن یالها اجرا می‌کنیم. پس اگر اختلاف کوتاهترین مسیر و طولانی‌ترین مسیر کم باشد می‌توانیم آن را تقریبی حل کنیم. اگر بتوانیم با عملی مانند جستجوی دودویی کرانهای بالا و پایین را به هم نزدیک کنیم به نتیجه مورد نظر می‌رسیم. برای این کار طول مسیر را بر (n-1) تقسیم می‌کنیم و برای یالها کران به دست می‌آوریم بعد با تقسیم وزن یالها به این مقدار تعداد وزن‌های متمایز را محدود می‌کنیم و می‌توانیم با dynamic programming مسأله را حل کنیم. هر بار طول مسیر را یکی زیاد می‌کنیم و در صورتی که جواب بهتر شد آن را جایگزین جواب قبلی می‌کنیم.

؟؟ در مقاله اصلی گفته شده که رأسها را طوری شماره‌گذاری می‌کنیم که اگر بین دو رأس یال باشد رأس اول شماره کمتری از رأس دوم دارد. این topological sort است که نیاز به شرط نبودن دور در گراف دارد.

دو الگوریتم بر حسب طول مسیر و وزن مسیر داده است که اولی از مرتبه‌ی تعداد یالهای * حداکثر طول یال و دومی از مرتبه‌ی تعداد یالها * هزینه مسیر بهینه است. (هر دو dp). الگوریتم‌های دقیق هستند برای حالتی از مسأله که ماکسیمم طول مسیر مشخص باشد.