อัลกอริทึม

เรียงงานของลูกค้าตาม $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)

w_{i}/t_{i}\,

จากมากไปหาน้อย แล้วถ่ายเอกสารตามลำดับนั้น จะได้ว่า อัลกอริทึมทำงานได้ในเวลา

O(n\log 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)

C_{1}w_{1}+C_{2}w_{2}+...+C_{n}w_{n}\,

มีค่าน้อยที่สุดนั่นเอง

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

เราจะพิสูจน์ความถูกต้องของอัลกอริทึมโดยใช้เทคนิค exchange argument ให้ $OPT\,$ แทนวิธีการจัดลำดับการถ่ายเอกสารที่มีความไม่พอใจรวมของลูกค้าน้อยที่สุด เราจะแสดงว่าเราสามารถเปลี่ยนวิธีการจัดลำดับการถ่ายเอกสารแบบ $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)

w_{i}/t_{i}\,

จากมากไปน้อยได้ โดยที่ค่าความไม่พอใจรวมไม่เพิ่มขึ้น

สมมติว่า $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)

w_{i}/t_{i}<w_{j}/t_{j}\,

แต่ งานของลูกค้าคนที่

i\,

ได้ถ่ายเอกสารก่อนของลูกค้าคนที่

j\,

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

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

สมมติให้ก่อนการสลับ งานของลูกค้าคนที่ $i\,$ ได้เริ่มทำที่เวลา $S\,$ เราจะได้ว่าเวลา $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)

C_{i}=S+t_{i}\,

ส่วนเวลา ดังนั้นความไม่พอใจรวมจะเป็น

w_{i}(S+t_{i})+w_{j}(S+t_{i}+t_{j})=w_{i}S+w_{i}t_{i}+w_{j}S+w_{j}t_{i}+w_{j}t_{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)

C_{j}=S+t_{j}\,

ส่วนเวลา

C_{i}=S+t_{j}+t_{i}\,

ดังนั้นความไม่พอใจรวมจะเป็น

เมื่อพิจารณาสมการความไม่พอใจรวมก่อนและหลังสลับข้างต้น และเนื่องจาก $w_{j}/t_{j}>w_{i}/t_{i}\,$ เราจะได้ว่าหลังการสลับไม่ได้ทำให้ความไม่พอใจรวมเพิ่มขึ้น

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

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

อัลกอริทึม

Error

Error

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

Error

Error

Error

Error

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ