حل تقریبی (ویرایش ۴)

حل سوالهای ۱ و ۴ بیشتر توضیح داده شده است.

دریافت
حجم: 93.3 کیلوبایت

maximum coverage

https://www.cs.duke.edu/courses/fall13/compsci530/notes/lec16.pdf

درس ۱۰۰٪ حفظی

(دکتر) آبام اگر درسش حفظی نیست امتحان open book بگیره! :)

اصلاحیه صورت سوال تقریبی

سوال ۷ یک خط سوال اشتباه تایپی است! برای کران L چیزی نمی‌خواهد حساب کنیم.

سوال ۳ هزینه است نه تعداد یال.

اشکال در حل تمرین تقریبی

در سوال ۳ احتمالها یکنواخت نیستند. باید با derandomization (غیرتصادفی کردن) حل می‌کردیم.

حل تمرین تقریبی (ویرایش ۳)

اگر باز هم غلط داشت بگید! :))

دریافت
حجم: 92.7 کیلوبایت

اصلاحیه ۲ تمرین الگوریتم تقریبی

سوال ۵ هم قسمت اول سوال ثابت نشده است. (حلش را دارم به زودی درستش می‌کنم!)

سوال ۷ قسمت آخر نسبت کران بالا به پایین هنوز ایده‌ای برای حلش ندارم.

غلط های حل‌های قبلی از جمله املایی و نام گذاری و ... اصلاح شد.

اگر باز هم هست بگید!

دریافت
حجم: 90.9 کیلوبایت

تمرین الگوریتم تقریبی (نسخه اصلاح شده!)

از سوال ۷ قسمت پیدا کردن کران L مانده. در سوال ۵ هم اشکال هست. (خودم حل کرده بودم انگار!)

حل‌های فعلی را آپلود کردم اگر این‌ها اشکال دیگری دارند یا در مورد سوالهای ۷ و ۵ جواب بهتری دارید بگید.

دریافت
حجم: 90.9 کیلوبایت

اصلاحیه حل سوال ۷ تقریبی

گونه‌هایی از بشر واقعاً خنگ آفریده شده‌اند (خودم) من ایمیل زدم که چرا سوال 7-Acyclic graph شرط بدون دور بودن را ندارد؟ :)

حل قبلی که در وبلاگ زدم درست است!

وضعیت من بدون شرح است. دوستان در صورتی که چنین چیزهایی می‌بینید سریعاً اطلاع بدید!

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

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

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

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

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