ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 3"
Cardcaptor (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '== อัลกอริทึม == เราจะพิจารณาบ้านไปทีละบ้านตามตำแห…') |
Aoy (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 3 รุ่นระหว่างกลางโดยผู้ใช้ 1 คน) | |||
| แถว 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> | สมมติว่า 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> เสมอ | '''lemma:''' สำหรับจำนวนเต็ม <math>i \,</math> ทุกตัวที่ <math>1 \leq i \leq \ell \,</math> เราได้ว่า <math>y_i \geq y'_i \,</math> เสมอ | ||
| + | |||
| + | '''พิสูจน์:''' เราจะพิสูจน์โดยใช้ induction บนตัวแปร <math>i \,</math> | ||
| + | |||
| + | (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+1} \,</math> ด้วย | ||
| + | |||
| + | สมมติเพื่อให้เกิดข้อขัดแย้งว่า <math>y_{i+1} < y'_{i+1} \,</math> ฉะนั้นแสดงว่าจะต้องมีบ้าน <math>x_j \,</math> ที่อยู่ ณ ตำแหน่ง <math>y_{i+1} - 4 \,</math> พอดี | ||
| + | |||
| + | เรารู้ว่าบ้าน <math>x_j \,</math> ไม่อยู่ในเขตของเสา <math>y_i \,</math> (มิฉะนั้น greedy algorithm จะไม่ตั้งเสาใหม่) และเนื่องจาก <math>y_i \geq y'_i \,</math> มันจึงไม่อยู่ในขอบเขตของเสา <math>y'_i \,</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> | ||
| + | |||
| + | |||
| + | '''ทฤษฎีบท:''' Greedy algorithm ใช้เสาเป็นจำนวนน้อยที่สุดเท่าที่จะเป็นไปได้ กล่าวคือ <math>\ell = k \,</math> | ||
| + | |||
| + | '''พิสูจน์:''' สมมติเพื่อให้เกิดข้อขัดแย้งว่า <math>\ell < k \,</math> | ||
| + | |||
| + | จาก lemma เราได้ว่า <math>y_\ell \geq y'_\ell \,</math> เนื่องจากการปักเสาที่ <math>y'_1, y'_2, \ldots, y'_\ell \,</math> ครอบคลุมบ้านทุกบ้าน ดังนั้นจะไม่มีบ้านใดอยู่ ณ ตำแหน่งเกิน <math>y'_\ell + 4 \,</math> ด้วยเหตุนี้จึงไม่มีบ้านใดอยู่เกินตำแหน่ง <math>y_\ell + 4 \,</math> ด้วย | ||
| + | |||
| + | พิจารณาเวลาที่ greedy algorithm เพิ่งจะปักเสาต้นที่ <math>k \,</math> ไป เราพบว่าบ้านทุกบ้านจะต้องถูกครอบคลุมด้วยเสา <math>\ell \,</math> ต้นที่ปักไปแล้วตามการให้เหตุผลข้างต้น แต่การที่ <math>k > \ell \,</math> แสดงว่า greedy algorithm ยังทำงานต่อไปทั้งทที่มันควรจะหยุดการทำงานตั้งแต่ตอนที่ปักเสาต้นที่ <math>\ell \,</math> ไปแล้ว เกิดข้อขัดแย้ง | ||
| + | |||
| + | ดังนั้น <math>\ell = k \,</math> และ greedy algorithm ใช้จำนวนเสาน้อยที่สุดเท่าที่จะเป็นไปได้ | ||
รุ่นแก้ไขปัจจุบันเมื่อ 16:50, 20 กันยายน 2552
อัลกอริทึม
เราจะพิจารณาบ้านไปทีละบ้านตามตำแหน่งจากน้อยไปหามาก (กล่าวคือ พิจารณา , , , จนถึง ตามลำดับ)
ถ้าเราพบบ้าน ที่ยังไม่อยู่ในเขตของเสาโทรศัพท์ใดเลย เราจะตั้งเสาโทรศัพท์เพิ่มขึ้นหนึ่งต้นที่ตำแหน่ง (ซึ่งเป็นตำแหน่งที่ไกลที่สุดที่ทำให้บ้านนั้นยังได้รับสัญญาณโทรศัพท์อยู่)
ยกตัวอย่างเช่น ถ้าสมมติว่ามีบ้านตั้งอยู่ที่ตำแหน่ง 2, 3, 5, 10, 11, 15, 20 แล้วเราจะทำการตั้งเสาหนึ่งต้นที่ตำแหน่ง 6 = 2+4 และ 15 = 11+4 และ 24 = 20+4 เป็นต้น
เวลาเขียนโปรแกรม เราจะเขียน for loop วนโดยให้ตัวแปร มีค่าตั้งแต่ 1 ถึง และเราจะจำตำแหน่ง ของเสาต้นสุดท้ายที่เราตั้งเอาไว้ สำหรับบ้าน แต่ละหลัง เราสามารถเช็คได้ว่ามันได้รับสัญญาณโทรศัพท์หรือไม่โดยการเช็คว่า หรือไม่ ถ้าใช่เราก็ตั้งเสาใหม่ที่ตำแหน่ง และเปลี่ยนค่า เป็นค่าใหม่นี้ ตาม 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>
เห็นได้อย่างชัดเจนว่าอัลกอริทึมข้างบนทำงานในเวลา
ความถูกต้องของอัลกอริทึม
สมมติว่า greedy algorithm ข้างบนตั้งเสาที่ตำแหน่ง โดยที่ และสมมติให้วิธีการตั้งเสาที่ใช้จำนวนเสาน้อยที่สุดตั้งเสาอยู่ที่ตำแหน่ง โดยที่ เช่นกัน สังเกตว่า
lemma: สำหรับจำนวนเต็ม ทุกตัวที่ เราได้ว่า เสมอ
พิสูจน์: เราจะพิสูจน์โดยใช้ induction บนตัวแปร
(Base Case) ในกรณีนี้ และเราจะได้ว่าเสาที่อยู่ด้านซ้ายสุดจะต้องมีบ้าน อยู่ในพื้นที่ ดังนั้นเราจะได้ว่า แต่ greedy algorithm ปักเสาที่ตำแหน่ง พอดี ดังนั้น
(Induction Case) สมมติให้ สำหรับจำนวนเต็ม บางค่าที่ เราต้องการแสดงว่า ด้วย
สมมติเพื่อให้เกิดข้อขัดแย้งว่า ฉะนั้นแสดงว่าจะต้องมีบ้าน ที่อยู่ ณ ตำแหน่ง พอดี
เรารู้ว่าบ้าน ไม่อยู่ในเขตของเสา (มิฉะนั้น greedy algorithm จะไม่ตั้งเสาใหม่) และเนื่องจาก มันจึงไม่อยู่ในขอบเขตของเสา ด้วย
นอกจากนี้ เนื่องจาก เราจะได้ว่าบ้าน ไม่อยู่ในขอบเขตของเสา ด้วย กล่าวคือหากเราวางเสาโทรศัพท์ตามวิธีที่ใช้จำนวนเสาน้อยที่สุดเท่าที่จะทำได้แล้ว บ้าน จะไม่อยู่ในขอบเขตของเสาต้นใดเลย เกิดข้อขัดแย้งกับข้อกำหนดที่ว่าวิธีการวางเสาที่ใช้เสาน้อยที่สุดจะต้องครอบคลุมบ้านทุกบ้าน
ฉะนั้นเราจึงสามารถสรุปได้ว่า สำหรับทุกๆ ที่
ทฤษฎีบท: Greedy algorithm ใช้เสาเป็นจำนวนน้อยที่สุดเท่าที่จะเป็นไปได้ กล่าวคือ
พิสูจน์: สมมติเพื่อให้เกิดข้อขัดแย้งว่า
จาก lemma เราได้ว่า เนื่องจากการปักเสาที่ ครอบคลุมบ้านทุกบ้าน ดังนั้นจะไม่มีบ้านใดอยู่ ณ ตำแหน่งเกิน ด้วยเหตุนี้จึงไม่มีบ้านใดอยู่เกินตำแหน่ง ด้วย
พิจารณาเวลาที่ greedy algorithm เพิ่งจะปักเสาต้นที่ ไป เราพบว่าบ้านทุกบ้านจะต้องถูกครอบคลุมด้วยเสา ต้นที่ปักไปแล้วตามการให้เหตุผลข้างต้น แต่การที่ แสดงว่า greedy algorithm ยังทำงานต่อไปทั้งทที่มันควรจะหยุดการทำงานตั้งแต่ตอนที่ปักเสาต้นที่ ไปแล้ว เกิดข้อขัดแย้ง
ดังนั้น และ greedy algorithm ใช้จำนวนเสาน้อยที่สุดเท่าที่จะเป็นไปได้
