ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 4"
Cardcaptor (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'เพื่อให้สัญลักษณ์ดูง่าย เราให้ <math>a(i) = b(i) + r(i) \,</math> สำหร…') |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| แถว 9: | แถว 9: | ||
ก่อนที่เราจะไปพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้อง เราจะตั้งข้อสังเกตดังต่อไปนี้ | ก่อนที่เราจะไปพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้อง เราจะตั้งข้อสังเกตดังต่อไปนี้ | ||
| − | ให้ <math>f(i) \,</math> แทนเวลาที่ผู้เข้าแข่งขันหมายเลข <math>i \,</math> วายน้ำเสร็จ แล้วเราจะได้ว่าเวลาที่ผู้เข้าแข่งขันคนที่ช้าที่สุดจบการแข่งขันคือเวลา <math>\max_{1 \leq i \leq n} \{ f(i) + a(i) \} \,</math> | + | ให้ <math>f(i) \,</math> แทนเวลาที่ผู้เข้าแข่งขันหมายเลข <math>i \,</math> วายน้ำเสร็จ แล้วเราจะได้ว่าเวลาที่ผู้เข้าแข่งขันคนที่ช้าที่สุดจบการแข่งขันคือเวลา <math>\max_{1 \leq i \leq n} \{ f(i) + a(i) \} \,</math> |
| + | |||
| + | ดังนั้นอัลกอริทึมข้างบนจึงเป็นอัลกอริทึมทีทำให้ <math>\max_{1 \leq i \leq n} \{ f(i) + a(i) \} \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ | ||
| + | |||
== การพิสูจน์ความถูกต้องของอัลกอริทึม == | == การพิสูจน์ความถูกต้องของอัลกอริทึม == | ||
เราจะพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้องโดยใช้ exchange argument | เราจะพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้องโดยใช้ exchange argument | ||
ให้ <math>\mathrm{OPT} \,</math> แทนวิธีการจัดลำดับการเริ่มแข่งขันที่ดีที่สุด (กล่าวคือผู้เข้าแข่งขันที่จบการแข่งขันช้าที่สุดนั้นจบการแข่งขันเร็วที่สุดเท่าที่จะทำได้) เราจะแสดงว่าเราสามารถเปลี่ยน <math>\mathrm{OPT} \,</math> ไปเป็นวิธีการจัดลำดับการแข่งขันที่ผู้เข้าแข่งขันถูกเรียงตามเวลา <math>a(i) \,</math> โดยไม่ทำให้เวลาจบการแข่งขันของผู้เข้าแข่งขันที่จบเป็นคนสุดท้ายช้าลงได้ดังต่อไปนี้ | ให้ <math>\mathrm{OPT} \,</math> แทนวิธีการจัดลำดับการเริ่มแข่งขันที่ดีที่สุด (กล่าวคือผู้เข้าแข่งขันที่จบการแข่งขันช้าที่สุดนั้นจบการแข่งขันเร็วที่สุดเท่าที่จะทำได้) เราจะแสดงว่าเราสามารถเปลี่ยน <math>\mathrm{OPT} \,</math> ไปเป็นวิธีการจัดลำดับการแข่งขันที่ผู้เข้าแข่งขันถูกเรียงตามเวลา <math>a(i) \,</math> โดยไม่ทำให้เวลาจบการแข่งขันของผู้เข้าแข่งขันที่จบเป็นคนสุดท้ายช้าลงได้ดังต่อไปนี้ | ||
รุ่นแก้ไขเมื่อ 20:48, 17 กันยายน 2552
เพื่อให้สัญลักษณ์ดูง่าย เราให้ สำหรับ ทุกตัว
อัลกอริทึม
เรียงผู้เข้าแข่งขันตาม จากน้อยไปหามาก แล้วจัดลำดับการเริ่มต้นแข่งตามนั้น
เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้สามารถทำงานได้ในเวลา
ข้อสังเกต
ก่อนที่เราจะไปพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้อง เราจะตั้งข้อสังเกตดังต่อไปนี้
ให้ แทนเวลาที่ผู้เข้าแข่งขันหมายเลข วายน้ำเสร็จ แล้วเราจะได้ว่าเวลาที่ผู้เข้าแข่งขันคนที่ช้าที่สุดจบการแข่งขันคือเวลา
ดังนั้นอัลกอริทึมข้างบนจึงเป็นอัลกอริทึมทีทำให้ มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้
การพิสูจน์ความถูกต้องของอัลกอริทึม
เราจะพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้องโดยใช้ exchange argument
ให้ แทนวิธีการจัดลำดับการเริ่มแข่งขันที่ดีที่สุด (กล่าวคือผู้เข้าแข่งขันที่จบการแข่งขันช้าที่สุดนั้นจบการแข่งขันเร็วที่สุดเท่าที่จะทำได้) เราจะแสดงว่าเราสามารถเปลี่ยน ไปเป็นวิธีการจัดลำดับการแข่งขันที่ผู้เข้าแข่งขันถูกเรียงตามเวลา โดยไม่ทำให้เวลาจบการแข่งขันของผู้เข้าแข่งขันที่จบเป็นคนสุดท้ายช้าลงได้ดังต่อไปนี้
