418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 3 - ประวัติรุ่นแก้ไข

Aoy: /* ความถูกต้องของอัลกอริทึม */

2009-09-20T16:50:12Z

ความถูกต้องของอัลกอริทึม

Cardcaptor: /* ความถูกต้องของอัลกอริทึม */

2009-09-18T10:23:21Z

ความถูกต้องของอัลกอริทึม

Cardcaptor: /* ความถูกต้องของอัลกอริทึม */

2009-09-18T10:23:02Z

ความถูกต้องของอัลกอริทึม

Cardcaptor: /* ความถูกต้องของอัลกอริทึม */

2009-09-18T10:22:39Z

ความถูกต้องของอัลกอริทึม

Cardcaptor: หน้าที่ถูกสร้างด้วย '== อัลกอริทึม == เราจะพิจารณาบ้านไปทีละบ้านตามตำแห…'

2009-09-18T10:04:46Z

หน้าที่ถูกสร้างด้วย '== อัลกอริทึม == เราจะพิจารณาบ้านไปทีละบ้านตามตำแห…'

หน้าใหม่

== อัลกอริทึม ==
เราจะพิจารณาบ้านไปทีละบ้านตามตำแหน่งจากน้อยไปหามาก (กล่าวคือ พิจารณา <math>x_1 \,</math>, <math>x_2 \,</math>, <math>\ldots \,</math>, จนถึง <math>x_n \,</math> ตามลำดับ)

ถ้าเราพบบ้าน <math>x_i \,</math> ที่ยังไม่อยู่ในเขตของเสาโทรศัพท์ใดเลย เราจะตั้งเสาโทรศัพท์เพิ่มขึ้นหนึ่งต้นที่ตำแหน่ง <math>x_i + 4 \,</math> (ซึ่งเป็นตำแหน่งที่ไกลที่สุดที่ทำให้บ้านนั้นยังได้รับสัญญาณโทรศัพท์อยู่)

ยกตัวอย่างเช่น ถ้าสมมติว่ามีบ้านตั้งอยู่ที่ตำแหน่ง 2, 3, 5, 10, 11, 15, 20 แล้วเราจะทำการตั้งเสาหนึ่งต้นที่ตำแหน่ง 6 = 2+4 และ 15 = 11+4 และ 24 = 20+4 เป็นต้น

เวลาเขียนโปรแกรม เราจะเขียน for loop วนโดยให้ตัวแปร <math>i \,</math> มีค่าตั้งแต่ 1 ถึง <math>n \,</math> และเราจะจำตำแหน่ง <math>y \,</math> ของเสาต้นสุดท้ายที่เราตั้งเอาไว้ สำหรับบ้าน <math>x_i \,</math> แต่ละหลัง เราสามารถเช็คได้ว่ามันได้รับสัญญาณโทรศัพท์หรือไม่โดยการเช็คว่า <math>x_i > y+4 \,</math> หรือไม่ ถ้าใช่เราก็ตั้งเสาใหม่ที่ตำแหน่ง <math>x_i+4 \,</math> และเปลี่ยนค่า <math>y \,</math> เป็นค่าใหม่นี้ ตาม pseudocode ข้างล่าง

<geshi lang="c">
y = -INFINITY // หรืออาจจะให้ y เป็นค่าใดก็ได้ที่ทำให้ y+4 < x[1]
for i = 1 to n do
{
if x[i] > y then
{
ตั้งเสาใหม่ที่ x[i]+4
y = x[i] + 4
}
}
</geshi>

เห็นได้อย่างชัดเจนว่าอัลกอริทึมข้างบนทำงานในเวลา <math>O(n) \,</math>

== ความถูกต้องของอัลกอริทึม ==
สมมติว่า greedy algorithm ข้างบนตั้งเสาที่ตำแหน่ง <math>y_1, y_2, \ldots, y_k \,</math> โดยที่ <math>y_1 < y_2 < \dotsb < y_k \,</math> และสมมติให้วิธีการตั้งเสาที่ใช้จำนวนเสาน้อยที่สุดตั้งเสาอยู่ที่ตำแหน่ง <math>y'_1, y'_2, \ldots, y'_\ell \,</math> โดยที่ <math>y'_1 < y'_2 < \dotsb < y'_\ell \,</math> เช่นกัน สังเกตว่า <math>\ell \leq k \,</math>

'''lemma:''' สำหรับจำนวนเต็ม <math>i \,</math> ทุกตัวที่ <math>1 \leq i \leq \ell \,</math> เราได้ว่า <math>y_i \geq y'_i \,</math> เสมอ

@@ แถว 32: / แถว 32: @@
 (Base Case) ในกรณีนี้ <math>i = 1 \,</math> และเราจะได้ว่าเสาที่อยู่ด้านซ้ายสุดจะต้องมีบ้าน <math>x_1 \,</math> อยู่ในพื้นที่ ดังนั้นเราจะได้ว่า <math>x_1 + 4 \geq y'_1 \,</math> แต่ greedy algorithm ปักเสาที่ตำแหน่ง <math>x_1+4 \,</math> พอดี ดังนั้น <math>y_1 \geq y'_1 \,</math>
-(Induction Case) สมมติให้ <math>y_i \geq y'_i \,</math> สำหรับจำนวนเต็ม <math>i \,</math> บางค่าที่  <math>i \geq 1 \,</math> เราต้องการแสดงว่า <math>y_{i+1} \geq y'_{i} \,</math> ด้วย
+(Induction Case) สมมติให้ <math>y_i \geq y'_i \,</math> สำหรับจำนวนเต็ม <math>i \,</math> บางค่าที่  <math>i \geq 1 \,</math> เราต้องการแสดงว่า <math>y_{i+1} \geq y'_{i+1} \,</math> ด้วย
 สมมติเพื่อให้เกิดข้อขัดแย้งว่า <math>y_{i+1} < y'_{i+1} \,</math> ฉะนั้นแสดงว่าจะต้องมีบ้าน <math>x_j \,</math> ที่อยู่ ณ ตำแหน่ง <math>y_{i+1} - 4 \,</math> พอดี

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:23, 18 กันยายน 2552
แถว 40:		แถว 40:
	นอกจากนี้ เนื่องจาก <math>y'_{i+1} > y_{i+1} \,</math> เราจะได้ว่าบ้าน <math>x_j \,</math> ไม่อยู่ในขอบเขตของเสา <math>y'_{i+1} \,</math> ด้วย กล่าวคือหากเราวางเสาโทรศัพท์ตามวิธีที่ใช้จำนวนเสาน้อยที่สุดเท่าที่จะทำได้แล้ว บ้าน <math>x_j \,</math> จะไม่อยู่ในขอบเขตของเสาต้นใดเลย เกิดข้อขัดแย้งกับข้อกำหนดที่ว่าวิธีการวางเสาที่ใช้เสาน้อยที่สุดจะต้องครอบคลุมบ้านทุกบ้าน		นอกจากนี้ เนื่องจาก <math>y'_{i+1} > y_{i+1} \,</math> เราจะได้ว่าบ้าน <math>x_j \,</math> ไม่อยู่ในขอบเขตของเสา <math>y'_{i+1} \,</math> ด้วย กล่าวคือหากเราวางเสาโทรศัพท์ตามวิธีที่ใช้จำนวนเสาน้อยที่สุดเท่าที่จะทำได้แล้ว บ้าน <math>x_j \,</math> จะไม่อยู่ในขอบเขตของเสาต้นใดเลย เกิดข้อขัดแย้งกับข้อกำหนดที่ว่าวิธีการวางเสาที่ใช้เสาน้อยที่สุดจะต้องครอบคลุมบ้านทุกบ้าน

−	ฉะนั้นเราจึงสามารถสรุปได้ว่า <math>y_i \geq y'_i \,</math> สำหรับทุกๆ <math>i \,</math> ที่ <math>1 \leq i \leq ell \,</math>	+	ฉะนั้นเราจึงสามารถสรุปได้ว่า <math>y_i \geq y'_i \,</math> สำหรับทุกๆ <math>i \,</math> ที่ <math>1 \leq i \leq \ell \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:23, 18 กันยายน 2552
แถว 51:		แถว 51:
	พิจารณาเวลาที่ greedy algorithm เพิ่งจะปักเสาต้นที่ <math>k \,</math> ไป เราพบว่าบ้านทุกบ้านจะต้องถูกครอบคลุมด้วยเสา <math>\ell \,</math> ต้นที่ปักไปแล้วตามการให้เหตุผลข้างต้น แต่การที่ <math>k > \ell \,</math> แสดงว่า greedy algorithm ยังทำงานต่อไปทั้งทที่มันควรจะหยุดการทำงานตั้งแต่ตอนที่ปักเสาต้นที่ <math>\ell \,</math> ไปแล้ว เกิดข้อขัดแย้ง		พิจารณาเวลาที่ greedy algorithm เพิ่งจะปักเสาต้นที่ <math>k \,</math> ไป เราพบว่าบ้านทุกบ้านจะต้องถูกครอบคลุมด้วยเสา <math>\ell \,</math> ต้นที่ปักไปแล้วตามการให้เหตุผลข้างต้น แต่การที่ <math>k > \ell \,</math> แสดงว่า greedy algorithm ยังทำงานต่อไปทั้งทที่มันควรจะหยุดการทำงานตั้งแต่ตอนที่ปักเสาต้นที่ <math>\ell \,</math> ไปแล้ว เกิดข้อขัดแย้ง

−	ดังนั้น <math>\ell = k \,</math> และ greedy algorithm ~~จึงใช้จำนวนเสาน้อยที่สุดเท่าที่จะเป็นไปได้~~	+	ดังนั้น <math>\ell = k \,</math> และ greedy algorithm ใช้จำนวนเสาน้อยที่สุดเท่าที่จะเป็นไปได้

@@ แถว 24: / แถว 24: @@
 == ความถูกต้องของอัลกอริทึม ==
 สมมติว่า greedy algorithm ข้างบนตั้งเสาที่ตำแหน่ง <math>y_1, y_2, \ldots, y_k \,</math> โดยที่ <math>y_1 < y_2 < \dotsb < y_k \,</math> และสมมติให้วิธีการตั้งเสาที่ใช้จำนวนเสาน้อยที่สุดตั้งเสาอยู่ที่ตำแหน่ง <math>y'_1, y'_2, \ldots, y'_\ell \,</math> โดยที่ <math>y'_1 < y'_2 < \dotsb < y'_\ell \,</math> เช่นกัน สังเกตว่า <math>\ell \leq k \,</math>
 '''lemma:''' สำหรับจำนวนเต็ม <math>i \,</math> ทุกตัวที่ <math>1 \leq i \leq \ell \,</math> เราได้ว่า <math>y_i \geq y'_i \,</math> เสมอ