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

ขั้นตอนวิธีของคริสโตไฟด์  ตั้งชื่อตาม นิคอส คริสโตฟิลด์ เป็นขั้นตอนวิธีในการแก้ปัญหาบางกลุ่มของปัญหาการเดินทางของพนักงานขาย ที่มีเส้นเชื่อมถ่วงน้ำหนักเป็นไปตามความไม่เสมอภาคของสามเหลี่ยม ซึ่งได้คำตอบที่มีอัตราส่วนการประมาณ เป็น 1.5 เท่าของคำตอบดีที่สุด
 ให้ <math>G=(V,w)</math> เป็นตัวแทนของปัญหาการเดินทางของพนักงานขาย, <math>G</math> เป็น กราฟบริบูรณ์ บนเซตของจุดยอด <math>V</math> ซึ่งมี <math>w</math> เป็นฟังก์ชันของน้ำหนักที่ไม่มีน้ำหนักติดลบในทุกๆเส้นเชื่อมบน <math>G</math>
รหัสเทียม.
ขั้นตอนที่ 1: สร้าง ต้นไม้ทอดข้ามที่น้อยที่สุด <math>T</math> จาก <math>G</math>
ขั้นตอนที่ 2: ให้ <math>O</math> เป็นเซตของจุดยอดที่มี ระดับขั้น เป็นจำนวนคี่ ใน <math>T</math> และหา การจับคู่สมบูรณ์ <math>M</math> ซึ่งมีน้ำหนักน้อยที่สุดใน กราฟบริบูรณ์ บนจุดยอดใน <math>O</math>
ขั้นตอนที่ 3: รวมเส้นเชื่อมของ <math>M</math> และ <math>T</math> เป็น มัลติกราฟ <math>H</math>
ขั้นตอนที่ 4: สร้างวงจรออยเลอร์ ใน <math>H</math>
ขั้นตอนที่ 5: สร้างวงจรแฮมิลตัน จากขึั้นตอนที่แล้วโดยข้ามจุดยอดที่เยี่ยมชมแล้วออกไป ("shortcutting")
อัตราส่วนการประมาณ.
ผลลัพธ์ของขั้นตอนวิธีนี้มีค่าเป็น 1.5 เท่าของของคำตอบดีที่สุด
พิสูจน์ได้ดังนี้:
ให้ <math>A</math> แทนเซตของเส้นเชื่อมของคำตอบดีสุดของปัญหาการเดินทางของพนักงานขาย สำหรับ<math>G</math>, เนื่องจาก<math>(V,A)</math> เชื่อมต่อกันบริบูรณ์ จึงมีต้นไม้ทอดข้ามแน่ๆ ดังนั้น <math>w(A)\ge w(T)</math>
ให้ <math>B</math> แทนเซตของเส้นเชื่อมของคำตอบดีสุดของปัญหาการเดินทางของพนักงานขาย สำหรับกราฟบริบูรณ์ที่ใช้จุดยอดจาก <math>O</math>, เนื่องจากน้ำหนักของเส้นเชื่อมเป็นรูปสามเหลี่ยม ไม่ว่าจะเยี่ยมชมจุดยอดเพิ่มก็ไม่ทำให้น้ำหนักลดลง (ตามสมบัติความไม่เสมอภาคของสามเหลี่ยม) ทำให้เรารู้ว่า <math>w(A)\ge w(B)</math>
เราแสดงให้เห็นว่ามีการจับคู่ที่สมบูรณ์แบบของจุดยอดจาก<math>O</math> ที่มีน้ำหนักต่ำกว่า <math>w(B)/2\le w(A)/2</math> ซึ่งมีขอบบนเหมือนกันกับ <math>M</math> (<math>M</math> เป็นการจับคู่สมบูรณ์ที่มีน้ำหนักน้อยที่สุด), เนื่องจาก <math>O</math> จะมีจำนวนจุดยอดเป็นเลขคู่ จึงมีการจับคู่สมบูรณ์แน่ๆ
ให้ <math>e_1,\ldots,e_{2k}</math> เป็นวิถีออยเลอร์ใน <math>(O,B)</math> แน่นอนว่า <math>\{e_1,e_3,\ldots,e_{2k-1}\}</math> และ <math>\{e_2,e_4,\ldots,e_{2k}\}</math> เป็นการจับคู่สมบูรณ์ และ มีเส้นเชื่อมในการจับคู่สมบูรณ์นี้ อย่างน้อยหนึ่งอันที่น้ำหนักน้อยกว่าหรือเท่ากับ <math>w(B)/2</math>
ดังนั้น จาก <math>w(M)+w(T)\le w(A)+w(A)/2</math> และคุณสมบัติความไม่เสมอภาคของสามเหลี่ยม ทำให้ทราบว่าขั้นตอนวิธีนี้มีอัตราส่วนการประมาณ เป็น 1.5
สรุป.
เนื่องจากปัญหาการเดินทางของพนักงานขายอยู่ในกลุ่มปัญหาเอ็นพีบริบูรณ์ ซึ่งการจะหาคำตอบนั้นทำได้ยาก เราจึงมักใช้ขั้นตอนวิธีการประมาณในการประมาณคำตอบแทน และขั้นตอนวิธีของคริสโตไฟด์ ก็เป็นแนวทางหนึ่ง โดยมีเงื่อนไขว่าเส้นเชื่อมในกราฟนั้นจะเป็นไปตามความไม่เสมอภาคของสามเหลี่ยม ซึ่งเปรียบได้กับเมืองบนโลกจริงที่ถ้าหากมีเส้นทางจาก <math>A</math> ไป <math>B</math> และจาก <math>B</math> ไป <math>C</math> แล้ว จะมีเส้นทางจาก <math>A</math> ไป <math>C</math> ซึ่งไม่ยาวกว่าเส้นทางจาก <math>A</math> ไป <math>B</math> บวกกับเส้นทางจาก <math>B</math> ไป <math>C</math> แน่ๆ (ทางจาก <math>A</math> ไป <math>C</math> เปรียบได้กับทางลัด) ด้วยข้อกำหนดนี้ในการทำขั้นตอนที่ 2 และ 3 จะเป็นการเพิ่มเส้นเชื่อมที่จำเป็นในการหาวงจรออยเลอร์เข้าไปในกราฟ และขึ้นตอนที่ 5 ก็คือการเลือกเดินทางลัดนั่นเอง ซึ่งผลของขั้นตอนวิธีนี้ รับประกันได้ว่า ไม่แย่ไปกว่า 1.5 เท่าของคำตอบที่ดีที่สุด