เพื่อให้สัญลักษณ์ดูง่าย เราให้ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

a(i)=b(i)+r(i)\,

สำหรับ

1\leq i\leq n\,

ทุกตัว

อัลกอริทึม

เรียงผู้เข้าแข่งขันตาม $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

a(i)\,

จากมากไปหาน้อย แล้วจัดลำดับการเริ่มต้นแข่งตามนั้น

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

ข้อสังเกต

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

ให้ $f(i)\,$ แทนเวลาที่ผู้เข้าแข่งขันหมายเลข $i\,$ วายน้ำเสร็จ แล้วเราจะได้ว่าเวลาที่ผู้เข้าแข่งขันคนที่ช้าที่สุดจบการแข่งขันคือเวลา $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

\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} \,$ ไปเป็นวิธีการจัดลำดับการแข่งขันที่ผู้เข้าแข่งขันถูกเรียงตามเวลา $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

a(i)\,

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

สมมติว่า $\mathrm {OPT} \,$ ไม่ใช่การจัดลำดับตามอัลกอริทึมข้างบน แสดงว่า $\mathrm {OPT} \,$ จะต้องมี inversion กล่าวคือจะต้องมีผู้เข้าแข่งขัน $i\,$ และ $j\,$ ที่ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

a(i)<a(j)\,

แต่

i\,

ได้เริ่มทำการแข่งขันก่อน

j\,

จากในขั้นเรียน เราได้ว่าเมื่อมี inversion แล้วจะต้องมี inversion ที่อยู่ติดกัน กล่าวคือจะต้องมีผู้เข้าแข่งัน $i\,$ และ $j\,$ ที่ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

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 จะทำให้ผู้เข้าแข่งขันที่จบการแข่งขันเป็นคนสุดท้าย จบการแข่งขันเร็วที่สุดเท่าที่จะทำได้

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

Error

อัลกอริทึม

Error

ข้อสังเกต

Error

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

Error

Error

Error

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ