อัลกอริทึม Christofidesหรืออัลกอริทึม Christofides–Serdyukovเป็นอัลกอริทึมสำหรับค้นหาคำตอบโดยประมาณของปัญหาพนักงานขายเดินทางในกรณีที่ระยะทางก่อตัวเป็นปริภูมิเมตริก (มีความสมมาตรและเป็นไปตามอสมการสามเหลี่ยม ) ^{[ 1 ]} เป็นอัลกอริทึมการประมาณค่าที่รับประกันว่าคำตอบจะอยู่ภายในปัจจัย 3/2 ของความยาวคำตอบที่เหมาะสมที่สุด และตั้งชื่อตามNicos Christofidesและ Anatoliy Serdyukov ( ภาษารัสเซีย : Анатолий Иванович Сердюков ) Christofides เผยแพร่อัลกอริทึมในปี 1976; Serdyukov ค้นพบมันอย่างอิสระในปี 1976 แต่เผยแพร่ในปี 1978 ^{[ 2 ] [ 3 ] [ 4 ]}

ให้G = ( V , w )เป็นตัวอย่างหนึ่งของปัญหาพนักงานขายเดินทาง นั่นคือGเป็นกราฟสมบูรณ์บนเซตVของจุดยอด และฟังก์ชันwกำหนดค่าน้ำหนักจริงที่ไม่เป็นลบให้กับขอบทุกเส้นของGตามอสมการสามเหลี่ยม สำหรับจุดยอดสามจุดu , vและx ใดๆ จะต้องเป็นไปตามเงื่อนไขที่ว่าw ( uv ) + w ( vx ) ≥ w ( ux )

จากนั้นอัลกอริทึมสามารถอธิบายได้ในรูปแบบรหัสเทียมดังต่อไปนี้^{[ 1 ]}

1. สร้างต้นไม้แผ่คลุมน้อย ที่สุดTของG
2. ให้Oเป็นเซตของจุดยอดที่มีดีกรี คี่ ในTโดยทฤษฎีบทการจับมือ (handshaking lemma) O จะมีจำนวนจุดยอดเป็นเลขคู่
3. จง หา คู่สมบูรณ์ที่ มีน้ำหนักน้อยที่สุดMในกราฟย่อยที่เกิดจากOในG
4. รวมขอบของกราฟMและT เข้าด้วยกัน เพื่อสร้างกราฟหลายจุด เชื่อมต่อ Hซึ่งแต่ละจุดยอดมีดีกรีเป็นเลขคู่
5. สร้างวงจรออยเลอร์ในH
6. แปลงวงจรที่พบในขั้นตอนก่อนหน้าให้เป็นวงจรแฮมิลโทเนียนโดยการข้ามจุดยอดที่ซ้ำกัน ( การใช้ทางลัด )

ขั้นตอนที่ 5 และ 6 ไม่ได้ให้ผลลัพธ์เพียงอย่างเดียวเสมอไป ดังนั้น วิธีการเชิงฮิวริสติกนี้จึงสามารถให้เส้นทางที่แตกต่างกันได้หลายเส้นทาง

ความซับซ้อนในกรณีที่เลวร้ายที่สุดของอัลกอริทึมนั้นถูกครอบงำโดยขั้นตอนการจับคู่ที่สมบูรณ์แบบ ซึ่งมีความซับซ้อน^{[ 2 ]}บทความของ Serdyukov อ้างถึงความซับซ้อน^{[ 4 ]}เนื่องจากผู้เขียนทราบเพียงอัลกอริทึมการจับคู่ที่สมบูรณ์แบบที่มีประสิทธิภาพน้อยกว่า^{[ 3 ]}${\displaystyle O(n^{3})}$${\displaystyle O(n^{3}\log n)}$

ต้นทุนของโซลูชันที่ได้จากอัลกอริทึมนั้นอยู่ภายใน3/2ของค่าที่เหมาะสมที่สุด เพื่อพิสูจน์สิ่งนี้ ให้Cเป็นเส้นทางการเดินทางของพนักงานขายที่เหมาะสมที่สุด การลบขอบออกจากCจะสร้างต้นไม้แผ่คลุม ซึ่งต้องมีน้ำหนักอย่างน้อยเท่ากับต้นไม้แผ่คลุมขั้นต่ำ ซึ่งหมายความว่าw ( T ) ≤ w ( C ) - ขอบล่างของต้นทุนของโซลูชันที่เหมาะสมที่สุด

อัลกอริทึมนี้แก้ปัญหาที่ว่าTไม่ใช่เส้นทางเดินโดยการระบุจุดยอดที่มีดีกรีคี่ทั้งหมดในTเนื่องจากผลรวมของดีกรีในกราฟใดๆ ก็ตามเป็นเลขคู่ (ตามทฤษฎีบทการจับมือ ) ดังนั้นจึงมีจำนวนจุดยอดดังกล่าวเป็นเลขคู่ อัลกอริทึมนี้จะค้นหาการจับคู่ที่สมบูรณ์แบบที่มีน้ำหนักน้อยที่สุดMในบรรดาจุดยอดที่มีดีกรีคี่ เหล่านั้น

ถัดไป กำหนดหมายเลขให้กับจุดยอดของOตามลำดับแบบวนรอบCและแบ่งCออกเป็นสองชุดของเส้นทาง: ชุดที่จุดยอดแรกในลำดับแบบวนรอบมีหมายเลขคี่ และชุดที่จุดยอดแรกมีหมายเลขคู่ แต่ละชุดของเส้นทางจะสอดคล้องกับการจับคู่ที่สมบูรณ์แบบของOที่จับคู่จุดปลายทั้งสองของแต่ละเส้นทาง และน้ำหนักของการจับคู่นี้จะมีค่าสูงสุดเท่ากับน้ำหนักของเส้นทาง ในความเป็นจริง จุดปลายแต่ละจุดของเส้นทางจะเชื่อมต่อกับจุดปลายอีกจุดหนึ่ง ซึ่งมีจำนวนการเยี่ยมชมเป็นเลขคี่เช่นกัน เนื่องจากลักษณะของเส้นทาง

เนื่องจากเส้นทางทั้งสองชุดนี้แบ่งขอบของC ออก เป็นส่วนๆ ดังนั้นชุดหนึ่งในสองชุดจะมีน้ำหนักไม่เกินครึ่งหนึ่งของCและด้วยอสมการสามเหลี่ยม การจับคู่ที่สอดคล้องกันจะมีน้ำหนักไม่เกินครึ่งหนึ่งของน้ำหนักของC เช่นกัน การจับคู่ที่สมบูรณ์แบบที่มีน้ำหนักน้อยที่สุดไม่สามารถมีน้ำหนักมากกว่านี้ได้ ดังนั้นw ( M ) ≤ w ( C )/2การเพิ่มน้ำหนักของTและMจะได้น้ำหนักของเส้นทางออยเลอร์ ซึ่งไม่เกิน3w ( C ) /2ด้วยอสมการสามเหลี่ยม แม้ว่าเส้นทางออยเลอร์อาจจะกลับไปที่จุดยอดเดิม การใช้ทางลัดจะไม่เพิ่มน้ำหนัก ดังนั้นน้ำหนักของผลลัพธ์จึงไม่เกิน3w ( C ) /2เช่น กัน ^{[ 1 ]}

มีข้อมูลป้อนเข้าบางประเภทของปัญหาพนักงานขายเดินทางที่ทำให้ขั้นตอนวิธีของคริสโตฟิเดสพบคำตอบที่มีอัตราส่วนการประมาณค่าใกล้เคียงกับ3/2 อย่างไม่จำกัด ข้อมูลป้อนเข้าประเภทหนึ่งดังกล่าวคือเส้นทางที่มี จุดยอด nจุด โดยที่ขอบของเส้นทางมีน้ำหนัก1ร่วมกับชุดของขอบที่เชื่อมต่อจุดยอดที่อยู่ห่างกันสองขั้นในเส้นทาง โดยมีน้ำหนัก1 + ε สำหรับค่าεที่เลือกไว้ใกล้ศูนย์แต่เป็นค่าบวก

ขอบที่เหลือทั้งหมดของกราฟสมบูรณ์จะมีระยะทางที่กำหนดโดยเส้นทางที่สั้นที่สุดในกราฟย่อยนี้ จากนั้นต้นไม้แผ่คลุมขั้นต่ำจะกำหนดโดยเส้นทางที่มีความยาวn − 1และจุดยอดคี่เพียงสองจุดจะเป็นจุดปลายของเส้นทาง ซึ่งการจับคู่ที่สมบูรณ์แบบประกอบด้วยขอบเดียวที่มีน้ำหนักประมาณn / 2

การรวมกันของต้นไม้และการจับคู่เป็นวงจรที่ไม่มีทางลัดที่เป็นไปได้ และมีน้ำหนักประมาณ3 n /2อย่างไรก็ตาม วิธีแก้ปัญหาที่เหมาะสมที่สุดจะใช้ขอบที่มีน้ำหนัก1 + εร่วมกับขอบที่มีน้ำหนัก-1 สอง ขอบที่เชื่อมต่อกับจุดปลายของเส้นทาง และมีน้ำหนักรวม(1 + ε )( n − 2) + 2ซึ่งใกล้เคียงกับnสำหรับค่าε ที่เล็ก ดังนั้นเราจึงได้อัตราส่วนการประมาณค่า 3/2 ^{[ 5 ]}

	กำหนดให้: กราฟสมบูรณ์ที่มีค่าน้ำหนักของขอบเป็นไปตามอสมการสามเหลี่ยม
	คำนวณต้นไม้แผ่คลุมขั้นต่ำT
	คำนวณเซตของจุดยอดOที่มีดีกรีคี่ในT
	สร้างกราฟย่อยของGโดยใช้เฉพาะจุดยอดของO เท่านั้น
	สร้างการจับคู่ที่สมบูรณ์แบบM ที่มีน้ำหนักน้อยที่สุด ในกราฟย่อยนี้
	รวมต้นไม้จับคู่และต้นไม้แผ่ขยายT ∪ Mเพื่อสร้างมัลติกราฟแบบออยเลอร์
	คำนวณเส้นทางออยเลอร์เส้นทางนี้คือ A→B→C→A→D→E→A หรืออีกเส้นทางหนึ่งที่ถูกต้องคือ A→B→C→A→E→D→A
	ลบจุดยอดที่ซ้ำกันเพื่อให้ได้ผลลัพธ์ของอัลกอริทึมหากใช้เส้นทางอื่น ทางลัดจะเป็นการเดินทางจาก C ไป E ซึ่งจะทำให้ได้เส้นทางที่สั้นกว่า (A→B→C→E→D→A) หากเป็นกราฟแบบยุคลิด เนื่องจากเส้นทาง A→B→C→D→E→A มีเส้นตัดกัน ซึ่งพิสูจน์แล้วว่าไม่ใช่เส้นทางที่สั้นที่สุด

อัลกอริทึมนี้ไม่ใช่อัลกอริทึมการประมาณค่าแบบพหุนามที่ดีที่สุดสำหรับ TSP บนปริภูมิเมตริกทั่วไปอีกต่อไป Karlin, Klein และ Gharan ได้นำเสนอ อัลกอริทึมการประมาณค่า แบบสุ่มที่มีอัตราส่วนการประมาณค่า 1.5 − 10 ⁻³⁶โดยใช้หลักการที่คล้ายคลึงกับอัลกอริทึมของ Christofides แต่ใช้ต้นไม้ที่เลือกแบบสุ่มจากการกระจายแบบสุ่มที่เลือกอย่างระมัดระวังแทนต้นไม้ครอบคลุมขั้นต่ำ^{[ 6 ] [ 7 ]}บทความนี้ได้รับรางวัลบทความยอดเยี่ยมในงานSymposium on Theory of Computingปี 2021 ^{[ 8 ]}

ในกรณีพิเศษของปริภูมิยุคลิดที่มีมิติ n สำหรับค่าใดๆจะมีอัลกอริทึมที่ใช้เวลาพอลินอมิอัลในการค้นหาเส้นทางที่มีความยาวไม่เกิน n เท่าของค่าที่เหมาะสมที่สุดสำหรับกรณีเรขาคณิตของปัญหา TSP ใน ${\displaystyle d}$${\displaystyle c>0}$${\displaystyle 1+{\tfrac {1}{c}}}$

${\displaystyle O\left(n(\log n)^{(O(c{\sqrt {d}}))^{d-1}}\right)}$เวลา.

สำหรับค่าคงที่แต่ละค่า ขอบเขตเวลานี้ใช้เวลาพหุนามดังนั้นจึงเรียกว่าแผนการประมาณค่าเวลาพหุนาม (PTAS) ^{[ 9 ]} Sanjeev AroraและJoseph SB Mitchellได้รับรางวัลGödel Prizeในปี 2010 จากการค้นพบ PTAS สำหรับปัญหา TSP แบบยุคลิดพร้อมกัน ${\displaystyle c}$

วิธีการที่อิงตามอัลกอริทึม Christofides–Serdyukov ยังสามารถใช้ในการประมาณปัญหา stacker craneซึ่งเป็นการขยายความของ TSP โดยที่อินพุตประกอบด้วยคู่ลำดับของจุดจากปริภูมิเมตริกที่ต้องเดินทางต่อเนื่องและตามลำดับ สำหรับปัญหานี้ วิธีนี้ให้ค่าประมาณที่ 9/5 ^{[ 10 ]}

• คำจำกัดความของอัลกอริทึม Christofides ของ NIST