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(n-1)!=n!\,$ ตรงตามเวลาการทำงานที่โจทย์ต้องการ ส่วนเงื่อนไขในข้อนี้คือ Hamiltonian Cycle ที่มี cost ต่ำที่สุด ฉะนั้นเมื่อหยิบ Hamiltonian Cycle ขึ้นมาพิจารณาแล้วก็ดูว่า cost ของมันต่ำกว่า Cycle ที่เคยจำไว้หรือไม่ ถ้าต่ำกว่าก็เปลี่ยนมาจำ Hamiltonian Cycle ใหม่นี้แทน

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

GENERATE(k)

if k=0

c=COST(p,n)

if c < min

min <-- c

for i= 0 to i< n

p_min[i] <-- p[i]

else

for i=1 to i<= n

for j=1 to j<=n

if i != j

if used[i] != 1

used[i] <-- 1

p[k-1] <-- i

GENERATE(k-1)

used[i]<-- 0