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

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

الگوریتم 
به صورت شبه‌کد:
 درخت پوشای کمینه  را از  بسازید.
 فرض کنید  شامل رئوسی با درجه فرد در درخت  باشد. سپس تطابق کامل ،با کمترین وزن را در گراف کاملی شامل رئوس  بیابید.
 یال‌های گراف  و  را با هم ترکیب کنید و گراف چندگانه  را بسازید.
 یک دور اویلری در  تشکیل دهید. ( اویلری است، زیرا گراف توسط رئوس با درجه زوج مرتبط شده‌است)
 چرخهٔ به دست آمده در قدم قبلی را با استفاده از نادیده گرفتن رئوس دیده شده، همیلتونی کنید.

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

مثال

منابع 

 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]]]

الگوریتم‌های تقریبی
الگوریتم‌های گراف
درخت پوشا
علوم رایانه در ۱۹۷۶ (میلادی)
مسئله فروشنده دوره‌گرد
مقاله‌های ایجاد شده توسط ایجادگر