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

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

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

แนวคิด วัตถุที่เราสนใจคือ Hamiltonian Cycle ทั้งหมด พิจาณา Hamiltonian Cycle หนึ่งที่อาจเป็นไปได้ เช่น <math>(x_1,y_1) \rightarrow (x_2,y_2)\rightarrow ... \rightarrow (x_n,y_n) \rightarrow (x_1,y_1) \,</math> สังเกตว่าถ้าไม่พิจารณาจุดแรกกับจุดสุดท้าย นั่นคือ <math>(x_1,y_1)</math> จุดที่อยู่ระหว่างจุดแรกกับจุดสุดท้ายนี้ เมื่อนำมาเรียงสับเปลี่ยนกันก็จะเกิด Hamiltonian Cycle ใหม่ขึ้นอีก ดังนั้นการหยิบวัตถุที่สนใจขึ้นมาดู ก็คือการสร้าง permutation นั่นเอง ซึ่ง ถ้าไม่นับจุดแรกและจุดสุดท้าย จะมีจุดตรงกลางให้เรียงสับเปลี่ยนทั้งหมด <math>n-1 \,</math> จุด ก็จะได้การเรียงสับเปลี่ยนทั้งหมด <math>(n-1)! \,</math>แบบ และเราสามารถเลือกจุดแรก (เลือกจุดสุดท้ายด้วยในขณะเดียวกัน) ได้อีกทั้งหมด <math>n \,</math> จุด ดังนั้นจำนวน Hamiltonian Cycle ทั้งหมด จะได้ <math>n(n-1)!=n! \,</math> ตรงตามเวลาการทำงานที่โจทย์ต้องการ ส่วนเงื่อนไขในข้อนี้คือ Hamiltonian Cycle ที่มี cost ต่ำที่สุด ฉะนั้นเมื่อหยิบ Hamiltonian Cycle ขึ้นมาพิจารณาแล้วก็ดูว่า cost ของมันต่ำกว่า Cycle ที่เคยจำไว้หรือไม่ ถ้าต่ำกว่าก็เปลี่ยนมาจำ Hamiltonian Cycle ใหม่นี้แทน

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

<geshi lang="c">
GENERATE(k)
{
     if k=0
     {
         c=COST(p,n) // COST เป็น subroutine ที่ใช้ในการคำนวณระยะทางของ Hamiltonian Cycle ตามสูตรในโจทย์
                  if c < min  // ถ้า ระยะทางของ Hamiltonian cycle ที่พิจารณาขณะนี้มีค่าน้อยกว่า ระยะทางของ cycle ที่เคยจำไว้
                  {
             min <-- c // ให้เปลี่ยนมาจำระยะทางที่สั้นที่สุดของ cycle นี้แทน
                          for i= 0 to i< n 
                 p_min[i] <-- p[i] // จำว่า cycle นั้นคือ cycle ไหน (วิ่งจากจุดไหน ไปจุดไหน)
         } // end if  c < min
     }else{
             for i=1 to i<= n // จุด <math>(x_i,y_i) \,</math> เป็นจุดเริ่มต้นของ cycle
             {
                 for j=1 to j<=n 
                 {
                     if j != i  // จะทำการหา permutation โดยการสลับจุดต่าง ๆ ที่ไม่ใช่จุดเริ่มต้น
                                          { 
                          if used[j] != 1
                          {
                              used[j] <-- 1
                              p[k-1] <-- j
                              GENERATE(k-1)
                              used[j]<-- 0
                          } // end if used[j] != 1
                     } // end if j!= i
                 }// end for j
              } // end for i
      } // end else (k!=0)
} // end pseudocode
</geshi>