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

อัลกอริทึม

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

โจทย์ต้องการให้ความไม่พอใจรวมของลูกค้ามีค่าน้อยที่สุด เขียนเป็นสมการทางคณิตศาสตร์คือต้องการให้ค่า $C_{1}w_{1}+C_{2}w_{2}+...+C_{n}w_{n}\,$ มีค่าน้อยที่สุดนั่นเอง

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

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

สมมติว่า $OPT\,$ ไม่ใช่การจัดลำดับตามวิธีการในอัลกอริทึมข้างต้น แสดงว่ามี inversion ที่อยู่ติดกัน กล่าวคือจะต้องมีงานของลูกค้าคนที่ $i\,$ และ $j\,$ ที่ $w_{i}/t_{i}<w_{j}/t_{j}\,$ แต่ งานของลูกค้าคนที่ $i\,$ ได้ถ่ายเอกสารก่อนของลูกค้าคนที่ $j\,$

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

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

สมมติให้ก่อนการสลับ งานของลูกค้าคนที่ $i\,$ ได้เริ่มทำที่เวลา $S\,$ เราจะได้ว่าเวลา $C_{i}=S+t_{i}\,$ ส่วนเวลา $C_{j}=S+t_{i}+t_{j}\,$ ดังนั้นความไม่พอใจรวมจะเป็น $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}\,$

และจะได้ว่าหลังการสลับ เวลา$C_{j}=S+t_{j}\,$ ส่วนเวลา $C_{i}=S+t_{j}+t_{i}\,$ ดังนั้นความไม่พอใจรวมจะเป็น $w_{j}(S+t_{j})+w_{i}(S+t_{j}+t_{i})=w_{j}S+w_{j}t_{j}+w_{i}S+w_{i}t_{j}+w_{i}t_{i}\,$

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

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