ผู้ใช้:Group doll/ทดลองเขียน

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

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

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

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

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

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

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

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

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

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

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

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

ให้   เป็นวิถีออยเลอร์ใน   แน่นอนว่า   และ   เป็นการจับคู่สมบูรณ์ และ มีเส้นเชื่อมในการจับคู่สมบูรณ์นี้ อย่างน้อยหนึ่งอันที่น้ำหนักน้อยกว่าหรือเท่ากับ  

ดังนั้น จาก   และคุณสมบัติความไม่เสมอภาคของสามเหลี่ยม ทำให้ทราบว่าอัลกอริทึมนี้มีอัตราส่วนการประมาณ เป็น 1.5

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

แก้

สรุป

แก้

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

บันทึก

แก้

อ้างอิง

แก้