الگوریتم تقریبی: فروشنده دوره گرد دارای فاصله

فروشنده دوره گرد: در یک گراف وزن دار دور با کمترین وزن را پیدا کنید که هر راس را دقیقا یک بار ببیند. (دور همیلتونی)

فروشنده دوره گرد با فاصله: در یک گراف وزن دار دور با کمترین وزن را پیدا کنید که هر راس حداقل یک بار دیده شده باشد.

دلیل نام گذاری فروشنده دوره گرد با فاصله این است که اگر گراف دیگری بسازیم که بین دو راس آن یک یال با وزن کوتاهترین فاصله بین این دو راس باشد، اگر گراف اولیه همبند باشد تشکیل یک تابع فاصله می دهد.

تابع فاصله:

1) فاصله دو راس نامنفی است

2) اگر فاصله یک راس تا راس دیگر 0 باشد دو راس یکی هستند

3) تقارن

4) نامساوی مثلث

این یک مساله کمینه کردن است. پس دنبال کران برای OPT می گردیم. چند تا از ایده های ممکن MST و قطر گراف و مسیر فروشنده دوره گرد (مسیر همیلتونی با کمترین وزن) هستند.

برای چک کردن اینکه کدام یک از این معیارها خوب هستند به این نکته توجه می کنیم که کدام بیشتر به جواب نزدیک می شود. یعنی اگر یک ویژگی را انتخاب کنیم که برای یک ورودی بزرگ 100 برابر جواب بهینه باشد ضریب تقریب ما از 100 بهتر نمی شود. مثلا قطر در حالتی که گراف دارای یالهای با وزن مساوی باشد n برابر جواب بهینه می شود که خوب نیست.

نکته ی دیگری که در انتخاب معیار هست ساده تر بودن از محاسبه ی جواب بهینه است. مسیر فروشنده دوره گرد ساده تر نیست.

اما MST با کمترین وزن را راحت می شود به دست آورد پس سعی می کنیم از آن استفاده کنیم.

اگر روی MST گراف dfs بزنیم می بینیم:

ALG = 2*MST <= 2*OPT

یعنی یک جواب 2-تقریبی از فروشنده دوره گرد با فاصله است.

آیا می شود این تحلیل را بهتر کرد؟

نه، چون می شود ورودی هایی مثال زد که حالت تساوی اتفاق می افتد. مثل: گراف خط. (هر راسی به راس بعدی وصل است جز آخری). یعنی داریم:

opt(I) = 2(n-1)=2f(I)

از این نتیجه می گیریم با معیار MST به جواب بهتری نمی رسیم اما با روشهای دیگر ممکن است برسیم.

در واقع کاری که ما اینجا کردیم این بود که MST رو به گراف اویلری تبدیل کردیم (گرافی که بدون برداشتن دست از روی کاغذ بتوانیم رسم کنیم) و از این استفاده کردیم که یک دور اویلری داریم. اگر بتوانیم به روش بهتری MST را به گراف اویلری تبدیل کنیم به ضریب تقریب بهتری می رسیم.

یک دور اویلری وجود دارد اگر و تنها اگر هر راسی درجه زوج داشته باشد (با این فرض که از یک راس شروع کنیم و به همان راس برگردیم). پس اگر یک matching بین همه ی گره های با درجه فرد در MST پیدا کنیم و این یالها را به درخت اضافه کنیم مساله حل می شود.

تطابق بیشینه ی با کمترین وزن گراف را به دست بیاورید و راسهای با درجه ی زوج آن را در نظر بگیرید، وزن آن کمتر مساوی نصف وزن دور TSP با کمترین هزینه روی گراف است.

اثبات: به دلیل خاصیت فاصله، وزن دور TSP روی راسهای تطابق بیشینه با کمترین وزن، کمتر مساوی OPT است. این دور شامل دو تطابق می شود (می توانیم یالهایی که نگه می داریم با آنهایی که نگه نمی داریم جا به جا کنیم!)، تطابق کوچکتر حداکثر نصف جواب بهینه وزن دارد.

الگوریتم: فروشنده دوره گرد با فاصله

M: درخت پوشای کمینه (MST) روی G

U: مجموعه راسهای درجه زوج M

P: مینیمم هزینه ی تطابق کامل U با بقیه راسهای G

دور اویلری روی M اجتماع P را برگردان.

قضیه: الگوریتم بالا 3/2 تقریبی است برای فروشنده دوره گرد با فاصله.

اثبات:

تعداد راسهای با درجه فرد در MST باید زوج باشد، پس یک تطابق کامل روی این راسها انجام می دهیم تا گراف اویلری داشته باشیم.

گفتیم هزینه ی تطابق کامل کمتر مساوی 1/2 OPT است پس:

alg <= MST+matching <= 3/2OPT

نکته: در اثبات از دو کران پایین استفاده کردیم. هر کدام به تنهایی کافی نیستند اما ترکیب آنها با هم نتیجه خوبی می دهد.