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

พิจารณาตารางข้างล่างนี้

$a_{11}\,$	$a_{12}\,$	$a_{13}\,$
$a_{21}\,$	$a_{22}\,$	$a_{23}\,$
$a_{31}\,$	$a_{32}\,$	$a_{33}\,$

คะแนนของตารางนี้คือ $\sum _{i=1}^{3}\sum _{j=1}^{2}(a_{ij}-a_{i(j+1)})^{2}+\sum _{i=1}^{2}\sum _{j=1}^{3}(a_{ij}-a_{(i+1)j})^{2}$

เราเห็นได้ว่าคะแนนของตารางแบ่งออกเป็นสองส่วน คือ

• คะแนนตามแนวนอน: $\sum _{i=1}^{3}\sum _{j=1}^{2}(a_{ij}-a_{i(j+1)})^{2}$ และ
• คะแนนตามแนวตั้ง: $\sum _{i=1}^{2}\sum _{j=1}^{3}(a_{ij}-a_{(i+1)j})^{2}$

และนอกจากนี้เรายังสังเกตเพิ่มเติมได้อีกว่า

• การสลับแถวจะไม่ทำให้คะแนนแนวนอนเปลี่ยน
• การสลับคอลัมน์จะไม่ทำให้คะแนนแนวตั้งเปลี่ยน

ฉะนั้น เราจึงสามารถแก้ปัญหาในโจทย์ได้โดยการแบ่งอัลกอริทึมออกเป็นสองขั้นตอนดังนี้

• หาวิธีการสลับคอลัมน์ ให้ได้คะแนนแนวนอนมากที่สุด (โดยไม่ต้องสนใจคะแนนแนวตั้ง)
• หาวิธีการสลับแถว ให้ได้คะแนนแนวตั้งมากที่สุด (โดยไม่่ต้องสนใจคะแนนแนวนอน)

เมื่อเรานำเอาคะแนนแต่ละแนวที่มากที่สุดมาบวกกัน เราจะได้คะแนนของตารางที่มากที่สุดเท่าที่จะเป็นไปได้

ฉะนั้น ต่อไปนี้เราจะพูดถึงอัลกอริทึมสำหรับหาวิธีการสลับคอลัมน์ให้ได้คะแนนแนวนอนมากที่สุดเท่านั้น อัลกอริทึมสำหรับหาคะแนนแนวตั้งที่มากที่สุดก็มีลักษณะเช่นเดียวกัน

วัตถุ

เราสามารถแทนวิธีการสลับคอลัมน์ด้วย permutation บนเซต $\{1,2,\ldots ,n\}\,$ ซึ่งในชั้นเรียนเราเก็บ permutation ในอะเรย์ $p[1\ldots n]$ ขนาด $n\,$ ช่อง สำหรับปัญหานี้เราจะตีความหมายของ permutation ที่เก็บในอะเรย์ $p\,$ ดังต่อไปนี้:

ถ้า $p[i]=j\,$ แล้ว คอลัมน์ที่ $i\,$ ของตารางที่สลับคอลัมน์แล้ว คือคอลัมน์ที่ $j\,$ ของตารางต้นฉบับ

ค่าของวัตถุ

สมมติให้ตารางต้นฉบับเก็บอยู่ในอะเรย์ $T[1\ldots n,1\ldots n]\,$ เราสามารถเขียนฟังก์ชัน points เพื่อคำนวณคะแนนของตารางที่สลับแล้วได้ดังต่อไปนี้

<geshi lang="c"> points(T, p, n) {

   result = 0
   for i = 1 to n do
       for j = 1 to n-1 do
       {
           d = T[ i, p[j] ] - T[ i, p[j+1] ]
           result = result + d*d
       }
   return result

} </geshi>

เราได้ว่าฟังก์ชัน points ทำงานในเวลา $O(n(n-1))=O(n^{2})\,$

อัลกอริทึม

เราจะสร้าง permutation ขึ้นมาทีละตัว แล้วสำหรับ permutation แต่ละตัวเราจะเรียกฟังก์ชัน points เพื่อคำนวณคะแนนแนวนอนของตารางหลังจากสลับคอลัมน์ตาม permutation นั้น แล้วจึงนำค่าที่ได้ไปเปรียบเทียบกับค่าที่ต่ำที่สุดที่เคยเจอมา

เนื่องจากมี permutation อยู่ทั้งหมด $n!\,$ ตัว และสำหรับแต่ละตัวเราใช้เวลาในการหาค่าของมันเท่ากับ $O(n^{2})\,$ อัลกอริทึมของเราจึงทำงานในเวลา $O(n^{2}n!)\,$ ตามต้องการ