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

Cardcaptor: หน้าที่ถูกสร้างด้วย 'พิจารณาตารางข้างล่างนี้

$a_{11} \,$
2009-08-28T18:35:14Z

หน้าที่ถูกสร้างด้วย 'พิจารณาตารางข้างล่างนี้ <table cellpadding="5"> <tr> <td align="center"><math>a_{11} \,</mat…'

หน้าใหม่
พิจารณาตารางข้างล่างนี้
<table cellpadding="5">
<tr>
<td align="center"><math>a_{11} \,</math></td>
<td align="center"><math>a_{12} \,</math></td>
<td align="center"><math>a_{13} \,</math></td>
</tr>
<tr>
<td align="center"><math>a_{21} \,</math></td>
<td align="center"><math>a_{22} \,</math></td>
<td align="center"><math>a_{23} \,</math></td>
</tr>
<tr>
<td align="center"><math>a_{31} \,</math></td>
<td align="center"><math>a_{32} \,</math></td>
<td align="center"><math>a_{33} \,</math></td>
</tr>
</table>
คะแนนของตารางนี้คือ <math>\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 </math>

เราเห็นได้ว่าคะแนนของตารางแบ่งออกเป็นสองส่วน คือ
* คะแนนตามแนวนอน: <math>\sum_{i=1}^3 \sum_{j=1}^2 (a_{ij} - a_{i(j+1)})^2</math> และ
* คะแนนตามแนวตั้ง: <math>\sum_{i=1}^2 \sum_{j=1}^3 (a_{ij} - a_{(i+1)j})^2</math>
และนอกจากนี้เรายังสังเกตเพิ่มเติมได้อีกว่า
* การสลับแถวจะไม่ทำให้คะแนนแนวนอนเปลี่ยน
* การสลับคอลัมน์จะไม่ทำให้คะแนนแนวตั้งเปลี่ยน

ฉะนั้น เราจึงสามารถแก้ปัญหาในโจทย์ได้โดยการแบ่งอัลกอริทึมออกเป็นสองขั้นตอนดังนี้
* หาวิธีการสลับคอลัมน์ ให้ได้คะแนนแนวนอนมากที่สุด (โดยไม่ต้องสนใจคะแนนแนวตั้ง)
* หาวิธีการสลับแถว ให้ได้คะแนนแนวตั้งมากที่สุด (โดยไม่่ต้องสนใจคะแนนแนวนอน)
เมื่อเรานำเอาคะแนนแต่ละแนวที่มากที่สุดมาบวกกัน เราจะได้คะแนนของตารางที่มากที่สุดเท่าที่จะเป็นไปได้

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

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

=== ค่าของวัตถุ ===
สมมติให้ตารางต้นฉบับเก็บอยู่ในอะเรย์ <math>T[1 \ldots n, 1 \ldots n] \,</math> เราสามารถเขียนฟังก์ชัน 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>

เราได้ว่าฟังก์ชัน <code>points</code> ทำงานในเวลา <math>O(n(n-1)) = O(n^2) \,</math>

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

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