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

รุ่นแก้ไขปัจจุบันเมื่อ 21:03, 17 กันยายน 2552

เพื่อให้สัญลักษณ์ดูง่าย เราให้ $a(i)=b(i)+r(i)\,$ สำหรับ $1\leq i\leq n\,$ ทุกตัว

อัลกอริทึม

เรียงผู้เข้าแข่งขันตาม $a(i)\,$ จากมากไปหาน้อย แล้วจัดลำดับการเริ่มต้นแข่งตามนั้น

เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้สามารถทำงานได้ในเวลา $O(n\log n)\,$

ข้อสังเกต

ก่อนที่เราจะไปพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้อง เราจะตั้งข้อสังเกตดังต่อไปนี้

ให้ $f(i)\,$ แทนเวลาที่ผู้เข้าแข่งขันหมายเลข $i\,$ วายน้ำเสร็จ แล้วเราจะได้ว่าเวลาที่ผู้เข้าแข่งขันคนที่ช้าที่สุดจบการแข่งขันคือเวลา $\max _{1\leq i\leq n}\{f(i)+a(i)\}\,$

ดังนั้นอัลกอริทึมข้างบนจึงเป็นอัลกอริทึมทีทำให้ $\max _{1\leq i\leq n}\{f(i)+a(i)\}\,$ มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้

การพิสูจน์ความถูกต้องของอัลกอริทึม

เราจะพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้องโดยใช้ exchange argument

ให้ $\mathrm {OPT} \,$ แทนวิธีการจัดลำดับการเริ่มแข่งขันที่ดีที่สุด (กล่าวคือผู้เข้าแข่งขันที่จบการแข่งขันช้าที่สุดนั้นจบการแข่งขันเร็วที่สุดเท่าที่จะทำได้) เราจะแสดงว่าเราสามารถเปลี่ยน $\mathrm {OPT} \,$ ไปเป็นวิธีการจัดลำดับการแข่งขันที่ผู้เข้าแข่งขันถูกเรียงตามเวลา $a(i)\,$ โดยไม่ทำให้เวลาจบการแข่งขันของผู้เข้าแข่งขันที่จบเป็นคนสุดท้ายช้าลงได้ดังต่อไปนี้

สมมติว่า $\mathrm {OPT} \,$ ไม่ใช่การจัดลำดับตามอัลกอริทึมข้างบน แสดงว่า $\mathrm {OPT} \,$ จะต้องมี inversion กล่าวคือจะต้องมีผู้เข้าแข่งขัน $i\,$ และ $j\,$ ที่ $a(i)<a(j)\,$ แต่ $i\,$ ได้เริ่มทำการแข่งขันก่อน $j\,$

จากในขั้นเรียน เราได้ว่าเมื่อมี inversion แล้วจะต้องมี inversion ที่อยู่ติดกัน กล่าวคือจะต้องมีผู้เข้าแข่งัน $i\,$ และ $j\,$ ที่ $a(i)<a(j)\,$ และ $j\,$ เริ่มทำการแข่งขันต่อจาก $i\,$ พอดี ถ้าหากเราสลับให้ $j\,$ มาทำการแข่งขันก่อน $i\,$ เราก็จะลดจำนวน inversion ลงหนึ่ง และเราสามารถทำเช่นนี้ไปเรื่อยๆ ได้จนกระทั่งไม่เหลือ inversion ดังนั้นเราสามารถเปลี่ยน $\mathrm {OPT} \,$ ให้เป็นคำตอบที่ greedy algorithm ให้ได้เสมอ

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

สมมติว่าก่อนสลับให้ $i\,$ เริ่มทำการแข่งขัน ณ เวลา $S\,$ เราจะได้ว่า $i\,$ แข่งเสร็จเวลา $S+s(i)+a(i)\,$ และ $j\,$ ทำการแข่งขันเสร็จ ณเวลา $S+s(i)+s(j)+a(j)\,$ เนื่องจาก $a(j)>a(i)\,$ ดังนั้น $j\,$ จะจบการแข่งขันช้ากว่า $i\,$ เสมอ

ดังนั้นหลังสลับ เราได้ว่า $j\,$ จะแข่งเสร็จเวลา $S+s(j)+a(j)\,$ และ $i\,$ จะแข่งเสร็จเวลา $S+s(j)+s(i)+a(i)\,$ แต่เวลาการจบการแข่งขันทั้งสองนี้มีค่าไม่เกิน $S+s(i)+s(j)+a(j)\,$ ทั้งสิ้น ดังนั้นการสลับจึงไม่ทำให้เวลาของผู้เข้าแข่งขันที่จบการแข่งขันช้าที่สุด แย่ลงไปกว่าเดิมอีก

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

@@ แถว 2: / แถว 2: @@
 == อัลกอริทึม ==
-เรียงผู้เข้าแข่งขันตาม <math>a(i) \,</math> จากน้อยไปหามาก แล้วจัดลำดับการเริ่มต้นแข่งตามนั้น
+เรียงผู้เข้าแข่งขันตาม <math>a(i) \,</math> จากมากไปหาน้อย แล้วจัดลำดับการเริ่มต้นแข่งตามนั้น
 เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้สามารถทำงานได้ในเวลา <math>O(n \log n) \,</math>
@@ แถว 17: / แถว 17: @@
 ให้ <math>\mathrm{OPT} \,</math> แทนวิธีการจัดลำดับการเริ่มแข่งขันที่ดีที่สุด (กล่าวคือผู้เข้าแข่งขันที่จบการแข่งขันช้าที่สุดนั้นจบการแข่งขันเร็วที่สุดเท่าที่จะทำได้) เราจะแสดงว่าเราสามารถเปลี่ยน <math>\mathrm{OPT} \,</math> ไปเป็นวิธีการจัดลำดับการแข่งขันที่ผู้เข้าแข่งขันถูกเรียงตามเวลา <math>a(i) \,</math> โดยไม่ทำให้เวลาจบการแข่งขันของผู้เข้าแข่งขันที่จบเป็นคนสุดท้ายช้าลงได้ดังต่อไปนี้
+สมมติว่า <math>\mathrm{OPT} \,</math> ไม่ใช่การจัดลำดับตามอัลกอริทึมข้างบน แสดงว่า <math>\mathrm{OPT} \,</math> จะต้องมี inversion กล่าวคือจะต้องมีผู้เข้าแข่งขัน <math>i \,</math> และ <math>j \,</math> ที่ <math>a(i) < a(j) \,</math> แต่ <math>i \,</math> ได้เริ่มทำการแข่งขันก่อน <math>j \,</math>
+จากในขั้นเรียน เราได้ว่าเมื่อมี inversion แล้วจะต้องมี inversion ที่อยู่ติดกัน กล่าวคือจะต้องมีผู้เข้าแข่งัน <math>i \,</math> และ <math>j \,</math> ที่ <math>a(i) < a(j) \,</math> และ <math>j \,</math> เริ่มทำการแข่งขันต่อจาก <math>i \,</math> พอดี ถ้าหากเราสลับให้ <math>j \,</math> มาทำการแข่งขันก่อน <math>i \,</math> เราก็จะลดจำนวน inversion ลงหนึ่ง และเราสามารถทำเช่นนี้ไปเรื่อยๆ ได้จนกระทั่งไม่เหลือ inversion ดังนั้นเราสามารถเปลี่ยน <math>\mathrm{OPT} \,</math> ให้เป็นคำตอบที่ greedy algorithm ให้ได้เสมอ
+สิ่งเหลืออยู่คือเราต้องทำการพิสูจน์ว่าการสลับข้างต้นจะไม่ทำให้เวลาของผู้เข้าแข่งขันที่แข่งเสร็จคนสุดท้ายมากขึ้น
+สมมติว่าก่อนสลับให้ <math>i \,</math> เริ่มทำการแข่งขัน ณ เวลา <math>S \,</math> เราจะได้ว่า <math>i \,</math> แข่งเสร็จเวลา <math>S + s(i) + a(i) \,</math> และ <math>j \,</math> ทำการแข่งขันเสร็จ ณเวลา <math>S + s(i) + s(j) + a(j) \,</math> เนื่องจาก <math>a(j) > a(i) \,</math> ดังนั้น <math>j \,</math> จะจบการแข่งขันช้ากว่า <math>i \,</math> เสมอ
+ดังนั้นหลังสลับ เราได้ว่า <math>j \,</math> จะแข่งเสร็จเวลา <math>S + s(j) + a(j) \,</math> และ <math>i \,</math> จะแข่งเสร็จเวลา <math>S + s(j) + s(i) + a(i) \,</math> แต่เวลาการจบการแข่งขันทั้งสองนี้มีค่าไม่เกิน <math>S + s(i) + s(j) + a(j) \,</math> ทั้งสิ้น ดังนั้นการสลับจึงไม่ทำให้เวลาของผู้เข้าแข่งขันที่จบการแข่งขันช้าที่สุด แย่ลงไปกว่าเดิมอีก
+เราจึงสามารถสรุปได้ว่าการจัดลำดับการแข่งขันตาม greedy algorithm จะทำให้ผู้เข้าแข่งขันที่จบการแข่งขันเป็นคนสุดท้าย จบการแข่งขันเร็วที่สุดเท่าที่จะทำได้

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

รุ่นแก้ไขปัจจุบันเมื่อ 21:03, 17 กันยายน 2552

อัลกอริทึม

ข้อสังเกต

การพิสูจน์ความถูกต้องของอัลกอริทึม

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ