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

อัลกอริทึม

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

โจทย์ต้องการให้ความไม่พอใจรวมของลูกค้ามีค่าน้อยที่สุด เขียนเป็นสมการทางคณิตศาสตร์คือต้องการให้ค่า มีค่าน้อยที่สุดนั่นเอง

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

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

สมมติว่า ไม่ใช่การจัดลำดับตามวิธีการในอัลกอริทึมข้างต้น แสดงว่ามี inversion ที่อยู่ติดกัน กล่าวคือจะต้องมีงานของลูกค้าคนที่ และ ที่ แต่ งานของลูกค้าคนที่ ได้ถ่ายเอกสารก่อนของลูกค้าคนที่

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

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

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

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

เมื่อพิจารณาสมการความไม่พอใจรวมก่อนและหลังสลับข้างต้น และเนื่องจาก เราจะได้ว่าหลังการสลับไม่ได้ทำให้ความไม่พอใจรวมเพิ่มขึ้น

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