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

อัลกอริทึม

เรียงงานของผู้ใช้ตาม $t(i)\,$ จากน้อยไปหามาก แล้วส่งให้เครื่องจักรทำงานตามลำดับนั้น จะได้ว่า อัลกอริทึมทำงานได้ในเวลา $O(n\log n)\,$ ซึ่งใช้ในการเรียงลำดับนั่นเอง

โจทย์ต้องการให้เวลาคอยรวมของผู้ใช้ทุกคนมีค่าน้อยที่สุด เขียนเป็นสมการทางคณิตศาสตร์คือต้องการให้ค่า $T=\sum _{k=1}^{n}\sum _{j=1}^{k}t(i_{j})\,$ มีค่าน้อยที่สุดนั่นเอง

ข้อสังเกต

ให้ $l,m\,$ เป็นผู้ใช้สองคนจากผู้ใช้ทั้งหมด $n\,$ คน และให้การจัดลำดับการทำงานสองลำดับคือ $S_{1},S_{2}\,$ ที่มีการจัดลำดับของผู้ใช้คนอื่น ๆ เหมือนกันหมด แต่ว่าต่างกันที่ลำดับการทำงานของผู้ใช้ คนที่ $l\,$ กับ $m\,$ เท่านั้น สมมติให้ลำดับที่หนึ่ง $S_{1}\,$ ให้งานของผู้ใช้คนที่ $l\,$ ทำก่อนงานของผู้ใช้คนที่ $m\,$ นั่นคือลำดับเป็นดังนี้ $i_{1},i_{2},...,i_{l},i_{m},...,i_{n}\,$ ส่วนการจัดลำดับแบบที่สอง $S_{2}\,$ คือให้งานของผู้ใช้คนที่ $m\,$ ทำก่อนงานของผู้ใช้คนที่ $l\,$ นั่นคือลำดับเป็นดังนี้ $i_{1},i_{2},...,i_{m},i_{l},...,i_{n}\,$ ดังนั้นเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ $S_{1}\,$ คือ $\sum _{k=1}^{l-1}\sum _{j=1}^{k}t(i_{j})+\sum _{j=1}^{l}t(i_{j})+\sum _{j=1}^{m}t(i_{j})+\sum _{k=m+1}^{n}\sum _{j=1}^{k}t(i_{j})\,$ ส่วนเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ $S_{2}\,$ คือ $\sum _{k=1}^{m-1}\sum _{j=1}^{k}t(i_{j})+\sum _{j=1}^{m}t(i_{j})+\sum _{j=1}^{l}t(i_{j})+\sum _{k=l+1}^{n}\sum _{j=1}^{k}t(i_{j})\,$ โดยที่ $\sum _{k=1}^{l-1}\sum _{j=1}^{k}t(i_{j})=\sum _{k=1}^{m-1}\sum _{j=1}^{k}t(i_{j})\,$ และ $\sum _{k=m+1}^{n}\sum _{j=1}^{k}t(i_{j})=\sum _{k=l+1}^{n}\sum _{j=1}^{k}t(i_{j})\,$ แต่ $\sum _{j=1}^{l}t(i_{j})\,$ และ $\sum _{j=1}^{m}t(i_{j})\,$ ใน $S_{1}\,$ และ $S_{2}\,$ ไม่เท่ากัน

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

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

สมมติว่า $OPT\,$ ไม่ใช่การจัดลำดับตามวิธีการในอัลกอริทึมข้างต้น แสดงว่ามี inversion ที่อยู่ติดกัน กล่าวคือจะต้องมีงานของผู้ใช้คนที่ $l\,$ และ $m\,$ ที่ $t(l)>t(m)\,$ แต่ งานของผู้ใช้คนที่ $l\,$ ได้ทำก่อนของผู้ใช้คนที่ $m\,$

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

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

จากข้อสังเกตข้างต้น เพื่อความง่ายในการแทนค่าในสมการเวลาคอย จะกำหนดให้ $\sum _{k=1}^{l-1}\sum _{j=1}^{k}t(i_{j})=\sum _{k=1}^{m-1}\sum _{j=1}^{k}t(i_{j})=U\,$ และ $\sum _{k=m+1}^{n}\sum _{j=1}^{k}t(i_{j})=\sum _{k=l+1}^{n}\sum _{j=1}^{k}t(i_{j})=V\,$

ก่อนการสลับจะได้ว่า $\sum _{j=1}^{l}t(i_{j})=U+t(l)\,$ และ $\sum _{j=1}^{m}t(i_{j})=U+t(l)+t(m)\,$ ทำให้เวลาคอยรวมของผู้ใช่ก่อนการสลับจะเท่ากับ $U+U+t(l)+U+t(l)+t(m)+V\,$

และจะได้ว่าหลังการสลับ $\sum _{j=1}^{m}t(i_{j})=U+t(m)\,$ และ $\sum _{j=1}^{l}t(i_{j})=U+t(m)+t(l)\,$ ทำให้เวลาคอยรวมของผู้ใช่ก่อนการสลับจะเท่ากับ $U+U+t(m)+U+t(m)+t(l)+V\,$

เมื่อพิจารณาสมการเวลาคอยรวมก่อนและหลังสลับข้างต้น และเนื่องจาก $t(l)>t(m)\,$ เราจะได้ว่าหลังการสลับไม่ได้ทำให้เวลาคอยรวมของผู้ใช้เพิ่มขึ้น

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