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

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

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

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

 مثال 
200px داده: گراف متریک  باوزن روی یال‌ها200px  محاسبه درخت پوشای کمینه .200px  به دست آوردن مجموعه راس‌های  با درجه فرد در .200px  کاهش دادن  با راس‌های  ().200px  محاسبه مچینگ کامل  با کمترین وزن در .200px  اجتماع مچینگ و درخت پوشا ().200px  محاسبه دور اویلری در  (A-B-C-A-D-E-A).200px  حذف کردن رئوس تکراری و جابجایی آن با ارتباط‌های مستقیم (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.

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