ادامه تمرین های الگوریتم تقریبی - فصل 3 وزیرانی
4- نسخه ای از فروشنده دوره گرد متریک را در نظر بگیرید که در آن هدف پیدا کردن مسیر ساده شامل همه ی راسهای گراف است. سه مساله مختلف بر حسب تعداد سرهای مسیر که داده شده اند (0، 1، 2) وجود دارد. الگوریتم های تقریبی زیر را به دست آورید:
- اگر 0 یا 1 سر داده شده، الگوریتم با ضریب تقریب 3/2 بدهید.
- اگر هر دو سر مشخص شده اند، الگوریتم با ضریب 5/3 بدهید.
راهنمایی: از ایده الگوریتم 3.10 استفاده کنید. (الگوریتم 3.10 فروشنده دوره گرد متریک با ضریب 3/2 است که فقط راسهای درجه فرد را اصلاح می کرد.)
حل: اگر از دور بخواهیم یال حذف کنیم، الزاما به مسیر خوبی نمی رسیم، یعنی ممکن است آخرین یال یک دور خیلی بد باشد و به خاطر همین آن را انتخاب نکرده باشیم، اما اگر مسیر بخواهیم دیگر آن یال را لازم نداشته باشیم و جواب خیلی بهتر شود.
الف)
همان الگوریتم 3.10 را اجرا می کنیم، فقط به جای اینکه در آخر یک دور بسازیم، یک مسیر می سازیم:
در حالت 1 سر داده شده: یال ورودی به راس داده شده را حذف می کنیم.
در حالت 0 سر داده شده: یال با بیشترین وزن در دور را حذف می کنیم.
اثبات: یک تطابق کامل با کمترین وزن هزینه ای کمتر از نصف هزینه ی مسیر گذرنده از تمام رئوس دارد: چون اگر یالهای مسیر را یکی در میان حذف کنیم یک تطابق کامل می شود.
هزینه ی درخت هم از هزینه ی جواب بهینه کمتر است. پس کل هزینه از 3/2 جواب بهینه کمتر است. پس ضریب تقریب الگوریتم 3/2 است.
ب)
همان الگوریتم 3.10 را اجرا می کنیم، فقط به جای گراف اویلری، گراف نیمه اویلری می سازیم که درجه ی دو راس داده شده در آن فرد باشد. برای این کار می توانیم اگر درجه آنها فرد بود آن را تغییر ندهیم، در غیر این صورت در تطابقمان این راسها را هم در نظر بگیریم. در حالت اول جوابی که به دست می آید 3/2 جواب بهینه است. در حالت دوم جوابی که به دست می آید از هزینه MST + دو سوم هزینه مسیر TSP کمتر است.
5- فرض کنید گراف کامل بدون جهت داده شده که طول یالهای آن 1 یا 2 است (بدیهی است که در نامساوی مثلث صدق می کند). یک الگوریتم با ضریب تقریب 4/3 برای فروشنده دوره گرد در این گرافها بدهید.
راهنمایی: از پیدا کردن 2-تطابق مینیمم شروع کنید. یک 2-تطابق زیرمجموعه ای از یالهاست که هر راس دقیقا دو یال مجاور دارد.
حل: یک تطابق کامل مینیمم پیدا می کنیم و یالهای آن را حذف می کنیم، بعد یک تطابق کامل مینیمم دیگر پیدا می کنیم و یالهای این تطابق و تطابق قبلی را به عنوان 2-تطابق مینیمم در نظر می گیریم.
به MST در راسهایی که درجه فرد دارند از 2-تطابق کمینه یال اضافه می کنیم. می دانیم هزینه ی جواب بهینه از هزینه ی یالهای 2-تطابق کمینه بیشتر است. وزن 2-تطابق کمینه از وزن جواب بهینه مساله کمتر مساوی است. (چون در جواب بهینه یک دور داریم اما اینجا یک یا چند دور داریم.)
