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

Cardcaptor เมื่อ 21:03, 17 กันยายน 2552

2009-09-17T21:03:49Z

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

2009-09-17T20:58:50Z

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

Cardcaptor: /* ข้อสังเกต */

2009-09-17T20:48:45Z

ข้อสังเกต

Cardcaptor: หน้าที่ถูกสร้างด้วย 'เพื่อให้สัญลักษณ์ดูง่าย เราให้ $a(i) = b(i) + r(i) \,$ สำหร…'

2009-09-17T20:47:57Z

หน้าที่ถูกสร้างด้วย 'เพื่อให้สัญลักษณ์ดูง่าย เราให้ <math>a(i) = b(i) + r(i) \,</math> สำหร…'

หน้าใหม่

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

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

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

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

ให้ <math>f(i) \,</math> แทนเวลาที่ผู้เข้าแข่งขันหมายเลข <math>i \,</math> วายน้ำเสร็จ แล้วเราจะได้ว่าเวลาที่ผู้เข้าแข่งขันคนที่ช้าที่สุดจบการแข่งขันคือเวลา <math>\max_{1 \leq i \leq n} \{ f(i) + a(i) \} \,</math>
== การพิสูจน์ความถูกต้องของอัลกอริทึม ==
เราจะพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้องโดยใช้ exchange argument

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

@@ แถว 2: / แถว 2: @@
 == อัลกอริทึม ==
-เรียงผู้เข้าแข่งขันตาม <math>a(i) \,</math> จากน้อยไปหามาก แล้วจัดลำดับการเริ่มต้นแข่งตามนั้น
+เรียงผู้เข้าแข่งขันตาม <math>a(i) \,</math> จากมากไปหาน้อย แล้วจัดลำดับการเริ่มต้นแข่งตามนั้น
 เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้สามารถทำงานได้ในเวลา <math>O(n \log n) \,</math>
@@ แถว 18: / แถว 18: @@
 ให้ <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>
+สมมติว่า <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 ให้ได้เสมอ
+จากในขั้นเรียน เราได้ว่าเมื่อมี 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>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>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> ทั้งสิ้น ดังนั้นการสลับจึงไม่ทำให้เวลาของผู้เข้าแข่งขันที่จบการแข่งขันช้าที่สุด แย่ลงไปกว่าเดิมอีก

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 20:58, 17 กันยายน 2552
แถว 17:		แถว 17:

	ให้ <math>\mathrm{OPT} \,</math> แทนวิธีการจัดลำดับการเริ่มแข่งขันที่ดีที่สุด (กล่าวคือผู้เข้าแข่งขันที่จบการแข่งขันช้าที่สุดนั้นจบการแข่งขันเร็วที่สุดเท่าที่จะทำได้) เราจะแสดงว่าเราสามารถเปลี่ยน <math>\mathrm{OPT} \,</math> ไปเป็นวิธีการจัดลำดับการแข่งขันที่ผู้เข้าแข่งขันถูกเรียงตามเวลา <math>a(i) \,</math> โดยไม่ทำให้เวลาจบการแข่งขันของผู้เข้าแข่งขันที่จบเป็นคนสุดท้ายช้าลงได้ดังต่อไปนี้		ให้ <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>j \,</math> จะแข่งเสร็จเวลา <math>S + s(j) + a(j) \,</math> และ <math>i \,</math> จะแข่งเสร็จเวลา <math>S + s(j) + s(i) + a(i) \,</math>

@@ แถว 9: / แถว 9: @@
 ก่อนที่เราจะไปพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้อง เราจะตั้งข้อสังเกตดังต่อไปนี้
 ให้ <math>f(i) \,</math> แทนเวลาที่ผู้เข้าแข่งขันหมายเลข <math>i \,</math> วายน้ำเสร็จ แล้วเราจะได้ว่าเวลาที่ผู้เข้าแข่งขันคนที่ช้าที่สุดจบการแข่งขันคือเวลา <math>\max_{1 \leq i \leq n} \{ f(i) + a(i) \} \,</math>
 == การพิสูจน์ความถูกต้องของอัลกอริทึม ==
 เราจะพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้องโดยใช้ exchange argument
 ให้ <math>\mathrm{OPT} \,</math> แทนวิธีการจัดลำดับการเริ่มแข่งขันที่ดีที่สุด (กล่าวคือผู้เข้าแข่งขันที่จบการแข่งขันช้าที่สุดนั้นจบการแข่งขันเร็วที่สุดเท่าที่จะทำได้) เราจะแสดงว่าเราสามารถเปลี่ยน <math>\mathrm{OPT} \,</math> ไปเป็นวิธีการจัดลำดับการแข่งขันที่ผู้เข้าแข่งขันถูกเรียงตามเวลา <math>a(i) \,</math> โดยไม่ทำให้เวลาจบการแข่งขันของผู้เข้าแข่งขันที่จบเป็นคนสุดท้ายช้าลงได้ดังต่อไปนี้

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

Cardcaptor เมื่อ 21:03, 17 กันยายน 2552

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

Cardcaptor: /* ข้อสังเกต */

Cardcaptor: หน้าที่ถูกสร้างด้วย 'เพื่อให้สัญลักษณ์ดูง่าย เราให้ a(i) = b(i) + r(i) \, สำหร…'

Cardcaptor: หน้าที่ถูกสร้างด้วย 'เพื่อให้สัญลักษณ์ดูง่าย เราให้ $a(i) = b(i) + r(i) \,$ สำหร…'