تقریب کریستوفایدز

هدف الگوریتم تقریب کریستوفایدز (به خاطر تلاش‌های نیکول کریستوفایدز نامگذاری شده‌است) پیدا کردن راه حلی برای مثال‌هایی از مسئله فروشنده دوره‌گرد (TSP) است، به صورتی که وزن یال ها، نابرابری مثلثاتی را رعایت کنند. فرض کنید $G=(V,w)$ مثالی از TSP باشد. به این معنی که $G$ یک گراف کامل با یک سری رأس $V$ با تابع وزن $W$ است که به هر یال از $G$ یک وزن واقعی و غیرمنفی نسبت می‌دهد.

الگوریتم

به صورت شبه‌کد:

1. درخت پوشای کمینه $T$ را از $G$ بسازید.
2. فرض کنید $O$ شامل رئوسی با درجه فرد در درخت $T$ باشد. سپس تطابق کامل $M$،با کمترین وزن را در گراف کاملی شامل رئوس $O$ بیابید.
3. یال‌های گراف $M$ و $T$ را با هم ترکیب کنید و گراف چندگانه $H$ را بسازید.
4. یک دور اویلری در $H$ تشکیل دهید. ($H$ اویلری است، زیرا گراف توسط رئوس با درجه زوج مرتبط شده‌است)
5. چرخهٔ به دست آمده در قدم قبلی را با استفاده از نادیده گرفتن رئوس دیده شده، همیلتونی کنید.

نسبت تقریبی

هزینهٔ جواب درست شده توسط این روش بیشتر از ۳/۲ برابر جواب بهینه نیست اثبات: فرض بگیرید الگو:Math گراف حاصل از مجموعهٔ یال‌های جواب بهینه مسئله TSP برای گراف الگو:Math باشد به خاطر این که الگو:Math همبند است، می‌توان در آن یک درخت پوشای کمینه مانند الگو:Math یافت، و این که می‌دانیم الگو:Math و بعد فرض بگیرید $B$ گراف حاصل از مجموعه یال‌های جواب بهینهٔ مسئلهٔ TSP برای گراف کامل روی رئوس $O$ باشد به خاطر وجود ویژگی مثلثی بر روی یال‌های موجود گذر از راس‌های اضفه نمی‌توان هزینه را کم‌تر کند یعنی الگو:Math است. نشان می‌دهیم مچینگ کاملی وجود دارد که هزینهٔ آن حداکثر نصف الگو:Math باشد، پس الگو:Math کران بالایی برای الگو:Math می‌شود (چون $M$ مچینگ کامل کمینه است) به این گونه که چون مقدار رئوس $O$ زوج است، مچینگ کاملی در آن وجود دارد، فرض بگیرید الگو:Math مسیر اویلری در $(O,B)$ باشد بدیهتا هم الگو:Math وهم الگو:Math هرکدام مچینگ کامل هستند وزن حداقل یکی از آن‌ها بیشتر از الگو:Math نیست پس الگو:Math و به خاطر ویژگی مثلث به این روش تقریبی ۳/۲ است.

مثال

	داده: گراف متریک $G=(V,E)$ باوزن روی یال‌ها
	محاسبه درخت پوشای کمینه $T$.
	به دست آوردن مجموعه راس‌های $V^{\prime }$ با درجه فرد در $T$.
	کاهش دادن $G$ با راس‌های $V^{\prime }$ ($G{|}_{V^{\prime }}$).
	محاسبه مچینگ کامل $M$ با کمترین وزن در $G{|}_{V^{\prime }}$.
	اجتماع مچینگ و درخت پوشا ($T\cup M$).
	محاسبه دور اویلری در $T\cup M$ (A-B-C-A-D-E-A).
	حذف کردن رئوس تکراری و جابجایی آن با ارتباط‌های مستقیم (A-B-C-D-E-A). در گراف متریک این مرحله نمی‌تواند طول دور را بیشتر کند. دور به وجود آمده بعد از این مرحله جواب الگوریتم است.

منابع

• NIST Christofides Algorithm Definition
• Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

[[[:en:Christofides algorithm]]]