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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 3: แถว 3:
  
 
โจทย์ต้องการให้ความไม่พอใจรวมของลูกค้ามีค่าน้อยที่สุด เขียนเป็นสมการทางคณิตศาสตร์คือต้องการให้ค่า <math> C_1w_1+C_2w_2+...+C_nw_n \,</math> มีค่าน้อยที่สุดนั่นเอง
 
โจทย์ต้องการให้ความไม่พอใจรวมของลูกค้ามีค่าน้อยที่สุด เขียนเป็นสมการทางคณิตศาสตร์คือต้องการให้ค่า <math> C_1w_1+C_2w_2+...+C_nw_n \,</math> มีค่าน้อยที่สุดนั่นเอง
 +
 +
==''การพิสูจน์ความถูกต้องของอัลกอริทึม''==
 +
เราจะพิสูจน์ความถูกต้องของอัลกอริทึมโดยใช้เทคนิค exchange argument
 +
ให้ <math> OPT \, </math> แทนวิธีการจัดลำดับการถ่ายเอกสารที่มีความไม่พอใจรวมของลูกค้าน้อยที่สุด เราจะแสดงว่าเราสามารถเปลี่ยนวิธีการจัดลำดับการถ่ายเอกสารแบบ <math> OPT \, </math> ไปเป็นวิธีการจัดลำดับการถ่ายเอกสารเรียงตามค่า <math> w_i/t_i \, </math> จากมากไปน้อยได้ โดยที่ค่าความไม่พอใจรวมไม่เพิ่มขึ้น
 +
 +
สมมติว่า <math> OPT \, </math> ไม่ใช่การจัดลำดับตามวิธีการในอัลกอริทึมข้างต้น แสดงว่ามี inversion ที่อยู่ติดกัน กล่าวคือจะต้องมีงานของลูกค้าคนที่ <math> i \,</math> และ <math> j \, </math> ที่ <math> w_i/t_i < w_j/t_j \,</math แต่ งานของลูกค้าคนที่ <math> i \, </math> ได้ถ่ายเอกสารก่อนของลูกค้าคนที่ <math> j \, </math>
 +
 +
จากในห้องเรียนเราได้ทำการพิสูจน์ไปแล้วว่า เมื่อมี inversion แล้วจะต้องมีคู่ของ inversion ที่ติดกัน กล่าวคือจะต้องมีงานของลูกค้าคนที่ <math> i \, </mathL และ <math> j \, </math> ที่ <math> w_i/t_i < w_j/t_j \, </math> และงานของลูกค้าคนที่ <math> j \, </math> ถูกถ่ายเอกสารต่อจากงานของลูกค้าคนที่ <math> i \, </math> ทันที ถ้าหากเราสลับให้งานของลูกค้าคนที่ <math> j \, </math> มาถ่ายเอกสารก่อนงานของลูกค้าคนที่ <math> i \,</math> เราก็สามารถลดจำนวนของ inversion ไปได้อีกหนึ่งตัว และเราสามารถทำแบบนี้ไปได้เรื่อย ๆ จนกระทั่งไม่เหลือ inversion ดังนั้นเราจะสามารถเปลี่ยนลำดับการถ่ายเอกสารแบบ <math> OPT \, </math> ให้เป็นลำดับการถ่ายเอกสารเหมือนใน greedy algorithm ที่เรานำเสนอได้เสมอ
 +
 +
ต่อไปเราต้องทำการพิสูจน์ให้ได้ว่า การสลับลำดับการถ่ายเอกสารข้างต้นจะไม่ทำให้ความไม่พอใจรวมของลูกค้าเพิ่มขึ้น
 +
 +
สมมติให้ก่อนการสลับ งานของลูกค้าคนที่ <math> i \, </math> ได้เริ่มทำที่เวลา <math> S \, </math> เราจะได้ว่าเวลา <math> C_i=S + t_i \, </math> ส่วนเวลา <math> C_j=S + t_i + t_j \, </math> ดังนั้นความไม่พอใจรวมจะเป็น <math> w_i(S+t_i)+w_j(S+t_i+t_j)=w_iS+w_it_i+w_jS+w_jt_i+w_jt_j</math>
 +
 +
และจะได้ว่าหลังการสลับ เวลา<math> C_j=S + t_j \, </math> ส่วนเวลา <math> C_i=S + t_j + t_i \, </math> ดังนั้นความไม่พอใจรวมจะเป็น <math> w_j(S+t_j)+w_i(S+t_j+t_i)=w_jS+w_jt_j+w_iS+w_it_j+w_it_i</math>

รุ่นแก้ไขเมื่อ 17:34, 18 กันยายน 2552

อัลกอริทึม

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

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

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

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

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

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

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

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

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