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

هدف الگوریتم تقریب کریستوفایدز (به خاطر تلاش‌های نیکول کریستوفایدز نامگذاری شده‌است) پیدا کردن راه حلی برای مثال‌هایی از مسئله فروشنده دوره‌گرد (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. چرخهٔ به دست آمده در قدم قبلی را با استفاده از نادیده گرفتن رئوس دیده شده، همیلتونی کنید.

نسبت تقریبی

هزینهٔ جواب درست شده توسط این روش بیشتر از ۳/۲ برابر جواب بهینه نیست اثبات: فرض بگیرید A گراف حاصل از مجموعهٔ یال‌های جواب بهینه مسئله TSP برای گراف G باشد به خاطر این که (V,A) همبند است، می‌توان در آن یک درخت پوشای کمینه مانند T یافت، و این که می‌دانیم w(A) ≥ w(T) و بعد فرض بگیرید $B$ گراف حاصل از مجموعه یال‌های جواب بهینهٔ مسئلهٔ TSP برای گراف کامل روی رئوس $O$ باشد به خاطر وجود ویژگی مثلثی بر روی یال‌های موجود گذر از راس‌های اضفه نمی‌توان هزینه را کم‌تر کند یعنی w(A) ≥ w(B) است. نشان می‌دهیم مچینگ کاملی وجود دارد که هزینهٔ آن حداکثر نصف w(B) باشد، پس w(B)/2 کران بالایی برای w(M)/2 می‌شود (چون $M$ مچینگ کامل کمینه است) به این گونه که چون مقدار رئوس $O$ زوج است، مچینگ کاملی در آن وجود دارد، فرض بگیرید e₁,... ,e_2k مسیر اویلری در $(O,B)$ باشد بدیهتا هم e₁,... ,e_2k وهم e₁,e₃,... ,e_2k-1 هرکدام مچینگ کامل هستند وزن حداقل یکی از آن‌ها بیشتر از w(B)/2 نیست پس w(M)+w(T) ≤ w(A) + w(A)/2 و به خاطر ویژگی مثلث به این روش تقریبی ۳/۲ است.

مثال

	داده: گراف متریک $G=\left(V,E\right)$ باوزن روی یال‌ها
	محاسبه درخت پوشای کمینه $T$.
	به دست آوردن مجموعه راس‌های $V'$ با درجه فرد در $T$.
	کاهش دادن $G$ با راس‌های $V'$ ($G|_{V'}$).
	محاسبه مچینگ کامل $M$ با کمترین وزن در $G|_{V'}$.
	اجتماع مچینگ و درخت پوشا ($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]]]