418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 10

อินพุต: จุด $n\,$ จุดในระนาบสองมิติ

เอาพุต: Hamiltonian Cycle ที่มีระยะทางสั้นที่สุด

แนวคิด วัตถุที่เราสนใจคือ Hamiltonian Cycle ทั้งหมด พิจาณา Hamiltonian Cycle หนึ่งที่อาจเป็นไปได้ เช่น $(x_{1},y_{1})\rightarrow (x_{2},y_{2})\rightarrow ...\rightarrow (x_{n},y_{n})\rightarrow (x_{1},y_{1})\,$ สังเกตว่าถ้าไม่พิจารณาจุดแรกกับจุดสุดท้าย นั่นคือ $(x_{1},y_{1})$ จุดที่อยู่ระหว่างจุดแรกกับจุดสุดท้ายนี้ เมื่อนำมาเรียงสับเปลี่ยนกันก็จะเกิด Hamiltonian Cycle ใหม่ขึ้นอีก ดังนั้นการหยิบวัตถุที่สนใจขึ้นมาดู ก็คือการสร้าง permutation นั่นเอง ซึ่ง ถ้าไม่นับจุดแรกและจุดสุดท้าย จะมีจุดตรงกลางให้เรียงสับเปลี่ยนทั้งหมด $n-1\,$ จุด ก็จะได้การเรียงสับเปลี่ยนทั้งหมด $(n-1)!\,$และเราสามารถเลือกจุดแรก (เลือกจุดสุดท้ายด้วยในขณะเดียวกัน) ได้อีกทั้งหมด $n\,$ จุด ดังนั้นจำนวน Hamiltonian Cycle ทั้งหมด จะได้ $n!\,$ ตรงตามเวลาการทำงานที่โจทย์ต้องการ ส่วนเงื่อนไขในข้อนี้คือ Hamiltonian Cycle ที่มี cost ต่ำที่สุด ฉะนั้นเมื่อหยิบ Hamiltonian Cycle ขึ้นมาพิจารณาแล้วก็ดูว่า cost ของมันต่ำกว่า Cycle ที่เคยจำไว้หรือไม่ ถ้าต่ำกว่าก็เปลี่ยนมาจำ Hamiltonian Cycle ใหม่นี้แทน

จากแนวคิดข้างต้น สามารถนำมาเขียนเป็น pseudocode ได้ดังนี้