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

จากวิกิพีเดีย สารานุกรมเสรี

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

รหัสเทียม[แก้]

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

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

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

ขั้นตอนที่ 3: รวมเส้นเชื่อมของ M และ T เป็น มัลติกราฟ H

ขั้นตอนที่ 4: สร้างวงจรออยเลอร์ ใน H

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

อัตราส่วนการประมาณ[แก้]

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

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

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

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

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

ให้ e_1,\ldots,e_{2k} เป็นวิถีออยเลอร์ใน (O,B) แน่นอนว่า \{e_1,e_3,\ldots,e_{2k-1}\} และ \{e_2,e_4,\ldots,e_{2k}\} เป็นการจับคู่สมบูรณ์ และ มีเส้นเชื่อมในการจับคู่สมบูรณ์นี้ อย่างน้อยหนึ่งอันที่น้ำหนักน้อยกว่าหรือเท่ากับ w(B)/2

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

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

สรุป[แก้]

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

บันทึก[แก้]

อ้างอิง[แก้]