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

Cardcaptor: /* ข้อย่อย 2 */

2009-08-28T17:54:39Z

ข้อย่อย 2

Cardcaptor: /* อัลกอริทึม */

2009-08-28T17:54:09Z

อัลกอริทึม

Cardcaptor: /* ค่าของวัตถุ */

2009-08-28T17:16:56Z

ค่าของวัตถุ

Cardcaptor: /* อัลกอริทึม */

2009-08-28T17:16:18Z

อัลกอริทึม

Cardcaptor: /* อัลกอริทึม */

2009-08-28T17:15:43Z

อัลกอริทึม

Cardcaptor: /* ค่าของวัตถุ */

2009-08-28T17:15:27Z

ค่าของวัตถุ

Cardcaptor: หน้าที่ถูกสร้างด้วย '== ข้อย่อย 1 == === วัตถุ === เราสามารถมองว่าวัตถุที่เราต้…'

2009-08-28T17:03:31Z

หน้าที่ถูกสร้างด้วย '== ข้อย่อย 1 == === วัตถุ === เราสามารถมองว่าวัตถุที่เราต้…'

หน้าใหม่

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

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

ฉะนั้น สี่เหลี่ยมสามรูปสามารถแทนได้ด้วยคู่ลำดับสามคู่ลำดับ <math>(r_1, c_1), (r_2, c_2), (r_3, c_3) \,</math> แต่คู่ลำดับเหล่านี้สามารถแทนสี่เหลี่ยมที่ซ้อนทับกันได้ (ยกตัวอย่างเช่น ถ้า <math>r_1 = r_2 \,</math> และ <math>c_1 = c_2 \,</math> เป็นต้น) ดังนั้นเราต้องการวิธีการเซ็คว่ามีสี่เหลี่ยมสองอันใดๆ ในสี่เหลี่ยมสามอันนี้ซ้อนทับกันหรือไม่ เนื่องจากเราสนใจเฉพาะกลุ่มของสี่เหลี่ยมที่ไม่ซ้อนทับกันเท่านั้น

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

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

<blockquote>
สี่เหลี่ยมสองสี่เหลี่ยมจะทับกันก็ต่อเมื่อ
* ขอบเขตของมันบนแกนนอนซ้อนทับกัน และ
* ขอบเขตของมันบนแกนตั้งซ้อนทับกัน
</blockquote>

ดังนั้นถ้าผู้ใช้กำหนดสี่เหลี่ยม <math>(r_1, c_1) \,</math> และ <math>(r_2, c_2) \,</math> เราจะได้ว่า

* ขอบเขตตามแนวแกนนอนของสี่เหลี่ยมแรกคือคอลัมน์ <math>c_1, c_1+1, c_1+2, \ldots, c_1+K-1</math>
* ขอบเขตตามแนวแกนนอนของสี่เหลี่ยมที่สองคือคอลัมน์ <math>c_2, c_2+1, c_2+2, \ldots, c_2+K-1</math>
* ขอบเขตตามแนวแกนตั้งของสี่เหลี่ยมแรกคือแถว <math>r_1, r_1+1, r_1+2, \ldots, r_1+K-1</math>
* ขอบเขตตามแนวแกนตั้งของสี่เหลี่ยมที่สองคือแถว <math>r_2, r_2+1, r_2+2, \ldots, r_2+K-1</math>

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

* ขอบเขตตามแกนนอนจะซ้อนทับกันเมื่อ <math>(c_2 \leq c_1+K-1) \wedge (c_1 \leq c_2+K-1)</math>
* ขอบเขตตามแกนตั้งจะซ้อนทับกันเมื่อ <math>(r_2 \leq r_1+K-1) \wedge (r_1 \leq r_2+K-1)</math>

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

<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>

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

<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>

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

== ค่าของวัตถุ ==
เราสามารถเขียนฟังก์ชัน <code>value</code> เพื่อหาปริมาณนำ้มันสะสมภายในพื้นที่สี่เหลี่ยมหนึ่งผืนได้ดังต่อไปนี้
<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>
โดยที่ <code>T[,]</code> เป็นอะเรย์สองมิติที่เก็บตารางขนาด M คูณ N ที่โจทย์กำหนดให้

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

<geshi lang="c">
value_3(r1, c1, r2, c2, r3, c3)
{
return value(r1, c1) + value(r2, c2) + value(r2, c3)
}
</geshi>

@@ แถว 110: / แถว 110: @@
 ในข้อย่อยนี้เราจะใช้เทคนิคการทำ precomputation คล้ายๆ กับที่เราเคยใช้ในปัญหาการหาช่วงที่มีผลบวกมากที่สุด ซึ่งเป็นปัญหาที่เราเรียนกันในชั้นเรียน
-เพื่อกาณ์นี้ เราจะสร้างอะเรย์ <math>S[0 \ldots M, 0 \ldots N] \,</math> โดยที่
+เพื่อการณ์นี้ เราจะสร้างอะเรย์ <math>S[0 \ldots M, 0 \ldots N] \,</math> โดยที่
 * <math>S[r,c] = 0 \,</math> ถ้า <math>r = 0 \,</math> หรือ <math>c = 0 \,</math>
 * <math>S[r,c] = \sum_{i=1}^r \sum_{j=1}^c T[i,j] \,</math> ถ้า <math>r \,</math> และ <math>c \,</math> มากกว่า 0 ทั้งคู่

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:54, 28 สิงหาคม 2552
แถว 104:		แถว 104:

	เมื่อพิจารณาโครงสร้างของ loop ข้างบนแล้วก็จะเห็นได้ว่าอัลกอริทึมนี้ใช้เวลาทำงานเท่ากับ <math>O(M^3 N^3 K^2) \,</math>		เมื่อพิจารณาโครงสร้างของ loop ข้างบนแล้วก็จะเห็นได้ว่าอัลกอริทึมนี้ใช้เวลาทำงานเท่ากับ <math>O(M^3 N^3 K^2) \,</math>
		+
		+	== ข้อย่อย 2 ==
		+	เราจะเห็นได้ว่าคอขวดของอัลกอริทึมในข้อย่อย 1 คือฟังก์ชัน <code>value</code> ซึ่งใช้เวลาทำงาน <math>O(K^2) \,</math> ฉะนั้นหากเราลดเวลาการทำงานของมันให้เหลือ <math>O(1) \,</math> ได้เราก็จะได้อัลกอริทึมสำหรับแก้ปัญหานี้ที่ทำงานในเวลา <math>O(M^3 N^3) \,</math>
		+
		+	ในข้อย่อยนี้เราจะใช้เทคนิคการทำ precomputation คล้ายๆ กับที่เราเคยใช้ในปัญหาการหาช่วงที่มีผลบวกมากที่สุด ซึ่งเป็นปัญหาที่เราเรียนกันในชั้นเรียน
		+
		+	เพื่อกาณ์นี้ เราจะสร้างอะเรย์ <math>S[0 \ldots M, 0 \ldots N] \,</math> โดยที่
		+	* <math>S[r,c] = 0 \,</math> ถ้า <math>r = 0 \,</math> หรือ <math>c = 0 \,</math>
		+	* <math>S[r,c] = \sum_{i=1}^r \sum_{j=1}^c T[i,j] \,</math> ถ้า <math>r \,</math> และ <math>c \,</math> มากกว่า 0 ทั้งคู่
		+
		+	เราจะได้ว่า
		+	<table cellpadding="5">
		+	<tr>
		+	<td align="right"><math>\mathrm{value}(r,c) \,</math></td>
		+	<td align="center"><math>= \,</math></td>
		+	<td align="left"><math>\sum_{i=r}^{r+K-1} \sum_{j=c}^{c+K-1} T[i,j] \,</math></td>
		+	</tr>
		+	<tr>
		+	<td align="right"><math> \,</math></td>
		+	<td align="center"><math>= \,</math></td>
		+	<td align="left"><math>\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] \,</math></td>
		+	</tr>
		+	<tr>
		+	<td align="right"><math> \,</math></td>
		+	<td align="center"><math>= \,</math></td>
		+	<td align="left"><math>\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) \,</math></td>
		+	</tr>
		+	<tr>
		+	<td align="right"><math> \,</math></td>
		+	<td align="center"><math>= \,</math></td>
		+	<td align="left"><math>( S[r+K-1, c+K-1] - S[r+K-1, c-1] ) - ( S[r-1, C+K-1] - S[r-1, c-1] ) \,</math></td>
		+	</tr>
		+	<tr>
		+	<td align="right"><math> \,</math></td>
		+	<td align="center"><math>= \,</math></td>
		+	<td align="left"><math>S[r+K-1, c+K-1] - S[r+K-1, c-1] - S[r-1, C+K-1] + S[r-1, c-1] \,</math></td>
		+	</tr>
		+	</table>
		+
		+	ดังนั้น หากเราคำนวณอะเรย์ <math>v \,</math> เก็บเอาไว้แล้ว เราสามารถเขียนฟังก์ชัน <code>value</code> ใหม่ซึ่งทำงานภายในเวลา <math>O(1) \,</math> เท่านั้นได้ดังต่อไปนี้
		+
		+	<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>
		+
		+	ปัญหาที่เหลืออยู่คือเราจะสามารถคำนวณค่าในอะเรย์ <math>S \,</math> ได้อย่างรวดเร็วได้อย่างไร?
		+
		+	สังเกตว่า
		+	<table cellpadding="5">
		+	<tr>
		+	<td align="right"><math>T[r,c] \,</math></td>
		+	<td align="center"><math>= \,</math></td>
		+	<td align="left"><math>\sum_{i=r}^{r} \sum_{j=c}^{c} T[i,j] \,</math></td>
		+	</tr>
		+	<tr>
		+	<td align="right"><math> \,</math></td>
		+	<td align="center"><math>= \,</math></td>
		+	<td align="left"><math>\sum_{i=1}^{r} \sum_{j=c}^{c} T[i,j] - \sum_{i=1}^{r-1} \sum_{j=c}^c T[i,j] \,</math></td>
		+	</tr>
		+	<tr>
		+	<td align="right"><math> \,</math></td>
		+	<td align="center"><math>= \,</math></td>
		+	<td align="left"><math>\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) \,</math></td>
		+	</tr>
		+	<tr>
		+	<td align="right"><math> \,</math></td>
		+	<td align="center"><math>= \,</math></td>
		+	<td align="left"><math>S[r,c] - S[r,c-1] - S[r-1,c] - S[r-1,c-1] \,</math></td>
		+	</tr>
		+	</table>
		+	ดังนั้นหากเราทราบค่า <math>S[r,c-1] \,</math>, <math>S[r-1,c] \,</math>, และ <math>S[r-1,c-1] \,</math> แล้ว เราสามารถหาค่า <math>S[r,c] \,</math> ได่้ตามสมการ
		+	: <math>S[r,c] = T[r,c] + S[r-1,c] + S[r,c-1] - S[r-1,c-1] \,</math>
		+
		+	การคำนวณข้างต้นนี้สามารถทำให้เกิดขั้นได้โดยการคำนวณ <math>S[r,c] \,</math> โดยไล่ค่า <math>r \,</math> และ <math>c \,</math> จากน้อยไปหามากดัง 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>
		+
		+	การคำนวณข้างต้นใช้เวลา <math>O(MN) \,</math> ฉะนั้นอัลกอริทึมสำหรับแก้โจทย์จะใช้เวลาทั้งหมด <math>O(MN + M^3N^3) = O(M^3N^3) \,</math> ตามต้องการ

@@ แถว 80: / แถว 80: @@
 </geshi>
-เราเห็นได้อย่างชัดเจนว่าเวลาการทำงานของ <code>value</code> คือ <math>O(K^2) \,</math> ฉะนั้นเวลาการทำงานของ <code>value_3</code> จึงเท่ากับ <math>O(K^3) \,</math> ด้วย
+เราเห็นได้อย่างชัดเจนว่าเวลาการทำงานของ <code>value</code> คือ <math>O(K^2) \,</math> ฉะนั้นเวลาการทำงานของ <code>value_3</code> จึงเท่ากับ <math>O(K^2) \,</math> ด้วย
 === อัลกอริทึม ===

@@ แถว 87: / แถว 87: @@
 <geshi lang="c">
 max = 0
 for r1 = 1 to M-K+1 do
    for c1 = 1 to N-K+1 do
@@ แถว 94: / แถว 93: @@
          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 ข้างบนแล้วก็จะเห็นได้ว่าอัลกอริทึมนี้ใช้เวลาทำงานเท่ากับ <math>O(M^3 N^3 K^2) \,</math>

@@ แถว 93: / แถว 93: @@
        for c2 = 1 to N-K+1 do
          for r3 = 1 to M-K+1 do
-           for c3 = 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)

@@ แถว 57: / แถว 57: @@
 ฉะนั้นในอัลกอริทึมสำหรับแก้โจทย์ปัญหาข้อนี้ เราจึีงสามารถสร้างสี่เหลี่ยมสามอันทั้งหมดที่เป็นไปได้มาก่อน แล้วใช้ <code>check_overlap_3</code> เพื่อเช็คว่าสี่เหลี่ยมสามอันแต่ละกลุ่มซ้อนทับกันหรือไม่ แล้วเราจึงเลือกประมวลผลเฉพาะกลุ่มของสี่เหลี่ยมที่ไม่ซ้อนทับกันเท่านั้น
-== ค่าของวัตถุ ==
+=== ค่าของวัตถุ ===
 เราสามารถเขียนฟังก์ชัน <code>value</code> เพื่อหาปริมาณนำ้มันสะสมภายในพื้นที่สี่เหลี่ยมหนึ่งผืนได้ดังต่อไปนี้
 <geshi lang="c">
@@ แถว 79: / แถว 79: @@
+}
 </geshi>