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

ข้อย่อย 1

วัตถุ

เราสามารถมองว่าวัตถุที่เราต้องการค้นหา คือ "สี่เหลี่ยมขนาด K คูณ K สามอันที่ไม่ซ้อนทับกัน" และเราต้องการสี่เหลี่ยมสามกลุ่มนี้ที่มีผลรวมมากที่สุด

เราสามารถแทนสี่เหลี่ยมแต่ละอันได้ด้วยพิกัดของช่องมุมบนซ้ายของมัน กล่าวคือในตารางขนาด M คูณ N ที่ให้มานี้ เราจะให้หมายเลขของแถวของตารางจากบนลงล่างด้วยหมายเลย 1 ถึง M และหมายเลขคอลัมน์จากซ้ายไปขวาด้วยหมายเลข 1 ถึง N แล้วเราจะสามารถแทนช่องในตารางได้ด้วยคู่ลำดับ $(r,c)\,$ โดยที่ $1\leq r\leq M$ และ $1\leq c\leq N$

ฉะนั้น สี่เหลี่ยมสามรูปสามารถแทนได้ด้วยคู่ลำดับสามคู่ลำดับ $(r_{1},c_{1}),(r_{2},c_{2}),(r_{3},c_{3})\,$ แต่คู่ลำดับเหล่านี้สามารถแทนสี่เหลี่ยมที่ซ้อนทับกันได้ (ยกตัวอย่างเช่น ถ้า $r_{1}=r_{2}\,$ และ ​$c_{1}=c_{2}\,$ เป็นต้น) ดังนั้นเราต้องการวิธีการเซ็คว่ามีสี่เหลี่ยมสองอันใดๆ ในสี่เหลี่ยมสามอันนี้ซ้อนทับกันหรือไม่ เนื่องจากเราสนใจเฉพาะกลุ่มของสี่เหลี่ยมที่ไม่ซ้อนทับกันเท่านั้น

การเซ็คที่ว่านี้สามารถทำได้โดยเซ็คสี่เหลี่ยมมีละคู่ สำหรับทุกคู่ที่เป็นไปได้ กล่าวคือเราเซ็คว่าสี่เหลี่ยมที่หนึ่งซ้อนทับกับสี่เหลี่ยมที่สองหรือไม่ สองซ้อนทับกับสามหรือไม่ และสามซ้อนทับกับหนึ่งหรือไม่ ถ้ามีคู่ใดคู่หนึ่งทับกันเราก็จะไม่ประมวลผลกลุ่มสี่เหลี่ยมสามอันนั้น

เมื่อกำหนดสี่เหลี่ยมสองอันมาให้ เราสามารถเช็คว่ามันซ้อนทับกันหรือไม่โดยใช้ความจริงดังต่อไปนี้

สี่เหลี่ยมสองสี่เหลี่ยมจะทับกันก็ต่อเมื่อ

• ขอบเขตของมันบนแกนนอนซ้อนทับกัน และ
• ขอบเขตของมันบนแกนตั้งซ้อนทับกัน

ดังนั้นถ้าผู้ใช้กำหนดสี่เหลี่ยม $(r_{1},c_{1})\,$ และ $(r_{2},c_{2})\,$ เราจะได้ว่า

• ขอบเขตตามแนวแกนนอนของสี่เหลี่ยมแรกคือคอลัมน์ $c_{1},c_{1}+1,c_{1}+2,\ldots ,c_{1}+K-1$
• ขอบเขตตามแนวแกนนอนของสี่เหลี่ยมที่สองคือคอลัมน์ $c_{2},c_{2}+1,c_{2}+2,\ldots ,c_{2}+K-1$
• ขอบเขตตามแนวแกนตั้งของสี่เหลี่ยมแรกคือแถว $r_{1},r_{1}+1,r_{1}+2,\ldots ,r_{1}+K-1$
• ขอบเขตตามแนวแกนตั้งของสี่เหลี่ยมที่สองคือแถว $r_{2},r_{2}+1,r_{2}+2,\ldots ,r_{2}+K-1$

ขอบเขตสองขอบเขตใดๆ จะซ้อนทับกันถ้ามีช่องบางช่องที่อยู่ในทั้่งสองขอบเขต กล่าวคือ ​

• ขอบเขตตามแกนนอนจะซ้อนทับกันเมื่อ $(c_{2}\leq c_{1}+K-1)\wedge (c_{1}\leq c_{2}+K-1)$
• ขอบเขตตามแกนตั้งจะซ้อนทับกันเมื่อ $(r_{2}\leq r_{1}+K-1)\wedge (r_{1}\leq r_{2}+K-1)$

ดังนั้นเราสามารถเขียนฟังก์ชัน check_overlap_2 ซึ่งคืนค่า true เมื่อสี่เหลี่ยมที่ให้สองสี่เหลี่ยมซ้อนทับกัน และคืนค่า false ถ้าไม่เป็นเช่นนั้นได้ดังต่อไปนี้

<geshi lang="c"> check_overlap_2(r1, c1, r2, r2) {

   if (c2 <= c1 + K - 1) and (c1 <= c2 + K - 1) and (r2 <= r1 + K - 1) and (r1 <= r2 + K - 1) then
       return true
   else
       return false

} </geshi>

จากนั้นเราสามารถใช้ check_overlap_2 ในการสร้างฟังก์ชัน ​check_overlap_3 เพื่อเช็คว่าสี่เหลี่ยมสามอันที่ให้มาซ้อนทับกันหรือไม่ ได้ดังต่อไปนี้

<geshi lang="c"> check_overlap_3(r1, c1, r2, c2, r3, c3) {

   if (check_overlap_2(r1, c1, r2, c2) or 
       check_overlap_2(r2, c2, r3, c3) or
       check_overlap_2(r3, c3, r1, r1)) then
       return true
   else
       return false

} </geshi>

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

ค่าของวัตถุ

เราสามารถเขียนฟังก์ชัน value เพื่อหาปริมาณนำ้มันสะสมภายในพื้นที่สี่เหลี่ยมหนึ่งผืนได้ดังต่อไปนี้ <geshi lang="c"> value(r, c) {

   result = 0
   for i = r to r + K - 1 do
       for j = c to c + K - 1 do
           result = result + T[i,j]
   return result

} </geshi> โดยที่ T[,] เป็นอะเรย์สองมิติที่เก็บตารางขนาด M คูณ N ที่โจทย์กำหนดให้

ต่อไปเราจึงสามารถใช้ value สร้่างฟังก์ชัน value_3 เพื่อหาปริมาณนำ้มันสะสมในพื้นที่สี่เหลี่ยมสามผืนได้ดังต่อไปนี้

<geshi lang="c"> value_3(r1, c1, r2, c2, r3, c3) {

   return value(r1, c1) + value(r2, c2) + value(r2, c3)

} </geshi>

เราเห็นได้อย่างชัดเจนว่าเวลาการทำงานของ value คือ $O(K^{2})\,$ ฉะนั้นเวลาการทำงานของ value_3 จึงเท่ากับ $O(K^{2})\,$ ด้วย

อัลกอริทึม

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

<geshi lang="c"> max = 0 for r1 = 1 to M-K+1 do

 for c1 = 1 to N-K+1 do
   for r2 = 1 to M-K+1 do
     for c2 = 1 to N-K+1 do
       for r3 = 1 to M-K+1 do
         for c3 = 1 to N-K+1 do
         {
           if not check_overlap3(r1, c1, r2, c2, r3, c3) then
           {
             v = value_3(r1, c1, r2, c2, r3, c3)
             if v > max then
               max = v
           }
         }

</geshi>

เมื่อพิจารณาโครงสร้างของ loop ข้างบนแล้วก็จะเห็นได้ว่าอัลกอริทึมนี้ใช้เวลาทำงานเท่ากับ $O(M^{3}N^{3}K^{2})\,$

ข้อย่อย 2

เราจะเห็นได้ว่าคอขวดของอัลกอริทึมในข้อย่อย 1 คือฟังก์ชัน value ซึ่งใช้เวลาทำงาน $O(K^{2})\,$ ฉะนั้นหากเราลดเวลาการทำงานของมันให้เหลือ $O(1)\,$ ได้เราก็จะได้อัลกอริทึมสำหรับแก้ปัญหานี้ที่ทำงานในเวลา $O(M^{3}N^{3})\,$

ในข้อย่อยนี้เราจะใช้เทคนิคการทำ precomputation คล้ายๆ กับที่เราเคยใช้ในปัญหาการหาช่วงที่มีผลบวกมากที่สุด ซึ่งเป็นปัญหาที่เราเรียนกันในชั้นเรียน

เพื่อการณ์นี้ เราจะสร้างอะเรย์ $S[0\ldots M,0\ldots N]\,$ โดยที่

• $S[r,c]=0\,$ ถ้า $r=0\,$ หรือ $c=0\,$
• $S[r,c]=\sum _{i=1}^{r}\sum _{j=1}^{c}T[i,j]\,$ ถ้า $r\,$ และ $c\,$ มากกว่า 0 ทั้งคู่

เราจะได้ว่า

$\mathrm {value} (r,c)\,$	$=\,$	$\sum _{i=r}^{r+K-1}\sum _{j=c}^{c+K-1}T[i,j]\,$
$\,$	$=\,$	$\sum _{i=1}^{r+K-1}\sum _{j=c}^{c+K-1}T[i,j]-\sum _{i=1}^{r-1}\sum _{j=c}^{c+K-1}T[i,j]\,$
$\,$	$=\,$	${\bigg (}\sum _{i=1}^{r+K-1}\sum _{j=1}^{c+K-1}T[i,j]-\sum _{i=1}^{r+K-1}\sum _{j=1}^{c-1}T[i,j]{\bigg )}-{\bigg (}\sum _{i=1}^{r-1}\sum _{j=1}^{c+K-1}T[i,j]-\sum _{i=1}^{r-1}\sum _{j=1}^{c-1}T[i,j]{\bigg )}\,$
$\,$	$=\,$	$(S[r+K-1,c+K-1]-S[r+K-1,c-1])-(S[r-1,C+K-1]-S[r-1,c-1])\,$
$\,$	$=\,$	$S[r+K-1,c+K-1]-S[r+K-1,c-1]-S[r-1,C+K-1]+S[r-1,c-1]\,$

ดังนั้น หากเราคำนวณอะเรย์ $v\,$ เก็บเอาไว้แล้ว เราสามารถเขียนฟังก์ชัน value ใหม่ซึ่งทำงานภายในเวลา $O(1)\,$ เท่านั้นได้ดังต่อไปนี้

<geshi lang="c"> value(r,c) {

   return S[r+K-1,c+K-1] - S[r+K-1,c-1] - S[r-1,C+K-1] + S[r-1,c-1]

} </geshi>

ปัญหาที่เหลืออยู่คือเราจะสามารถคำนวณค่าในอะเรย์ $S\,$ ได้อย่างรวดเร็วได้อย่างไร?

สังเกตว่า

$T[r,c]\,$	$=\,$	$\sum _{i=r}^{r}\sum _{j=c}^{c}T[i,j]\,$
$\,$	$=\,$	$\sum _{i=1}^{r}\sum _{j=c}^{c}T[i,j]-\sum _{i=1}^{r-1}\sum _{j=c}^{c}T[i,j]\,$
$\,$	$=\,$	${\bigg (}\sum _{i=1}^{r}\sum _{j=1}^{c}T[i,j]-\sum _{i=1}^{r}\sum _{j=1}^{c}T[i,j]{\bigg )}-{\bigg (}\sum _{i=1}^{r-1}\sum _{j=1}^{c}T[i,j]-\sum _{i=1}^{r-1}\sum _{j=1}^{c-1}T[i,j]{\bigg )}\,$
$\,$	$=\,$	$S[r,c]-S[r,c-1]-S[r-1,c]-S[r-1,c-1]\,$

ดังนั้นหากเราทราบค่า ​$S[r,c-1]\,$, $S[r-1,c]\,$, และ $S[r-1,c-1]\,$ แล้ว เราสามารถหาค่า $S[r,c]\,$ ได่้ตามสมการ

$S[r,c]=T[r,c]+S[r-1,c]+S[r,c-1]-S[r-1,c-1]\,$

การคำนวณข้างต้นนี้สามารถทำให้เกิดขั้นได้โดยการคำนวณ $S[r,c]\,$ โดยไล่ค่า $r\,$ และ $c\,$ จากน้อยไปหามากดัง pseudocode ข้างล่างนี้ <geshi lang="c"> for r = 0 to M do

   for c = 0 to N do
   {
       if r = 0 or c = 0 then
           S[r,c] = 0
       else
           S[r,c] = T[r,c] + S[r-1,c] + S[r,c-1] - S[r-1,c-1]
   }

</geshi>

การคำนวณข้างต้นใช้เวลา $O(MN)\,$ ฉะนั้นอัลกอริทึมสำหรับแก้โจทย์จะใช้เวลาทั้งหมด $O(MN+M^{3}N^{3})=O(M^{3}N^{3})\,$ ตามต้องการ