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 ได้ดังนี้

<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 // จุด $(x_{i},y_{i})\,$ เป็นจุดเริ่มต้นของ 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>