ขั้นตอนวิธีของคริสโตไฟด์

ขั้นตอนวิธีของคริสโตไฟด์ (อังกฤษ: Christofides algorithm) ตั้งชื่อตาม เป็นขั้นตอนวิธีในการแก้ปัญหาบางกลุ่มของ ที่มีเป็นไปตาม ซึ่งได้คำตอบที่มีอัตราส่วนการประมาณ เป็น 1.5 เท่าของคำตอบดีที่สุด

รหัสเทียม

ให้ ${\displaystyle G=(V,w)}$ เป็นตัวแทนของ, ${\displaystyle G}$ เป็น กราฟบริบูรณ์ บนเซตของจุดยอด ${\displaystyle V}$ ซึ่งมี ${\displaystyle w}$ เป็นฟังก์ชันของน้ำหนักที่ไม่มีน้ำหนักติดลบในทุกๆเส้นเชื่อมบน ${\displaystyle G}$

ขั้นตอนที่ 1: สร้าง ต้นไม้ทอดข้ามที่น้อยที่สุด ${\displaystyle T}$ จาก ${\displaystyle G}$

ขั้นตอนที่ 2: ให้ ${\displaystyle O}$ เป็นเซตของจุดยอดที่มี ระดับขั้น เป็นจำนวนคี่ ใน ${\displaystyle T}$ และหา ${\displaystyle M}$ ซึ่งมีน้ำหนักน้อยที่สุดใน กราฟบริบูรณ์ บนจุดยอดใน ${\displaystyle O}$

ขั้นตอนที่ 3: รวมเส้นเชื่อมของ ${\displaystyle M}$ และ ${\displaystyle T}$ เป็น ${\displaystyle H}$

ขั้นตอนที่ 4: สร้าง ใน ${\displaystyle H}$

ขั้นตอนที่ 5: สร้าง จากขึั้นตอนที่แล้วโดยข้ามจุดยอดที่เยี่ยมชมแล้วออกไป (shortcutting)

อัตราส่วนการประมาณ

ผลลัพธ์ของขั้นตอนวิธีนี้มีค่าเป็น 1.5 เท่าของของคำตอบดีที่สุด

พิสูจน์ได้ดังนี้:

ให้ ${\displaystyle A}$ แทนเซตของเส้นเชื่อมของคำตอบดีสุดของ สำหรับ${\displaystyle G}$, เนื่องจาก${\displaystyle (V,A)}$ เชื่อมต่อกันบริบูรณ์ จึงมีต้นไม้ทอดข้ามแน่ๆ ดังนั้น ${\displaystyle w(A)\geq w(T)}$

ให้ ${\displaystyle B}$ แทนเซตของเส้นเชื่อมของคำตอบดีสุดของ สำหรับกราฟบริบูรณ์ที่ใช้จุดยอดจาก ${\displaystyle O}$, เนื่องจากน้ำหนักของเส้นเชื่อมเป็นรูปสามเหลี่ยม ไม่ว่าจะเยี่ยมชมจุดยอดเพิ่มก็ไม่ทำให้น้ำหนักลดลง (ตามสมบัติ) ทำให้เรารู้ว่า ${\displaystyle w(A)\geq w(B)}$

เราแสดงให้เห็นว่ามีของจุดยอดจาก${\displaystyle O}$ ที่มีน้ำหนักต่ำกว่า ${\displaystyle w(B)/2\leq w(A)/2}$ ซึ่งมีขอบบนเหมือนกันกับ ${\displaystyle M}$ ( ${\displaystyle M}$ เป็นที่มีน้ำหนักน้อยที่สุด), เนื่องจาก ${\displaystyle O}$ จะมีจำนวนจุดยอดเป็นเลขคู่ จึงมีแน่ๆ

ให้ ${\displaystyle e_{1},\ldots ,e_{2k}}$ เป็นใน ${\displaystyle (O,B)}$ แน่นอนว่า ${\displaystyle \{e_{1},e_{3},\ldots ,e_{2k-1}\}}$ และ ${\displaystyle \{e_{2},e_{4},\ldots ,e_{2k}\}}$ เป็น และ มีเส้นเชื่อมในนี้ อย่างน้อยหนึ่งอันที่น้ำหนักน้อยกว่าหรือเท่ากับ ${\displaystyle w(B)/2}$

ดังนั้น จาก ${\displaystyle w(M)+w(T)\leq w(A)+w(A)/2}$ และคุณสมบัติ ทำให้ทราบว่าขั้นตอนวิธีนี้มีอัตราส่วนการประมาณ เป็น 1.5

ปัญหาอื่นๆที่เกี่ยวข้อง

สรุป

เนื่องจากอยู่ในกลุ่มปัญหาเอ็นพีบริบูรณ์ ซึ่งการจะหาคำตอบนั้นทำได้ยาก เราจึงมักใช้ขั้นตอนวิธีการประมาณในการประมาณคำตอบแทน และขั้นตอนวิธีของคริสโตไฟด์ ก็เป็นแนวทางหนึ่ง โดยมีเงื่อนไขว่าเส้นเชื่อมในกราฟนั้นจะเป็นไปตาม ซึ่งเปรียบได้กับเมืองบนโลกจริงที่ถ้าหากมีเส้นทางจาก ${\displaystyle A}$ ไป ${\displaystyle B}$ และจาก ${\displaystyle B}$ ไป ${\displaystyle C}$ แล้ว จะมีเส้นทางจาก ${\displaystyle A}$ ไป ${\displaystyle C}$ ซึ่งไม่ยาวกว่าเส้นทางจาก ${\displaystyle A}$ ไป ${\displaystyle B}$ บวกกับเส้นทางจาก ${\displaystyle B}$ ไป ${\displaystyle C}$ แน่ๆ (ทางจาก ${\displaystyle A}$ ไป ${\displaystyle C}$ เปรียบได้กับทางลัด) ด้วยข้อกำหนดนี้ในการทำขั้นตอนที่ 2 และ 3 จะเป็นการเพิ่มเส้นเชื่อมที่จำเป็นในการหาเข้าไปในกราฟ และขึ้นตอนที่ 5 ก็คือการเลือกเดินทางลัดนั่นเอง ซึ่งผลของขั้นตอนวิธีนี้ รับประกันได้ว่า ไม่แย่ไปกว่า 1.5 เท่าของคำตอบที่ดีที่สุด

บันทึก

• คือผลบวกของด้านสั้นสองด้านของสามเหลี่ยมใดๆ ไม่มีทางสั้นกว่าด้านยาวของสามเหลี่ยมนั้นๆ

อ้างอิง

• Approximation Algorithms
• Christofides's 3/2 Approximation for Matric TSP
• CHRISTOFIDES’ HEURISTIC
• NIST Christofides Algorithm Definition
• Nicos Christofides, Worst-case analysis of a new heuristic for the , Report 388, Graduate School of Industrial Administration, CMU, 1976.