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

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

2009-09-18T19:09:46Z

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

Aoy: /* ข้อสังเกต */

2009-09-18T19:02:16Z

ข้อสังเกต

Aoy เมื่อ 19:01, 18 กันยายน 2552

2009-09-18T19:01:34Z

Aoy เมื่อ 18:57, 18 กันยายน 2552

2009-09-18T18:57:56Z

125.25.13.255: หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''== เรียงงานของผู้ใช้ตาม $t(i) \,$ จากน้…'

2009-09-18T18:35:30Z

หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''== เรียงงานของผู้ใช้ตาม <math> t(i) \, </math> จากน้…'

หน้าใหม่

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

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

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

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

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

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

สมมติให้ก่อนการสลับ งานของผู้ใช้คนที่ <math> l \, </math> ได้เริ่มทำที่เวลา <math> S \, </math>

และจะได้ว่าหลังการสลับ

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

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

@@ แถว 5: / แถว 5: @@
 ==''ข้อสังเกต''==
-ให้ <math> l,m \, </math> เป็นผู้ใช้สองคนจากผู้ใช้ทั้งหมด <math> n \, </math> คน และให้การจัดลำดับการทำงานสองลำดับคือ <math> S_1,S_2 \, </math> ที่มีการจัดลำดับของผู้ใช้คนอื่น ๆ เหมือนกันหมด แต่ว่าต่างกันที่ลำดับการทำงานของผู้ใช้ คนที่ <math> l \,</math> กับ <math> m \, </math> เท่านั้น สมมติให้ลำดับที่หนึ่ง <math> S_1 \, </math> ให้งานของผู้ใช้คนที่ <math> l \, </math> ทำก่อนงานของผู้ใช้คนที่ <math> m \, </math> นั่นคือลำดับเป็นดังนี้ <math> i_1,i_2,...,i_l,i_m,...,i_n \,</math> ส่วนการจัดลำดับแบบที่สอง <math> S_2 \,</math> คือให้งานของผู้ใช้คนที่ <math> m \, </math> ทำก่อนงานของผู้ใช้คนที่ <math> l \, </math> นั่นคือลำดับเป็นดังนี้ <math> i_1,i_2,...,i_m,i_l,...,i_n \,</math> ดังนั้นเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ <math> S_1 \, </math> คือ <math> \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) \,</math> ส่วนเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ <math> S_2 \, </math> คือ <math> \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) \,</math> โดยที่ <math> \sum_{k=1}^{l-1}\sum_{j=1}^k t(i_j)=\sum_{k=1}^{m-1}\sum_{j=1}^k t(i_j) \,</math> และ <math> \sum_{k=m+1}^n \sum_{j=1}^k t(i_j)=\sum_{k=l+1}^n \sum_{j=1}^k t(i_j)\,</math>แต่ <math> \sum_{j=1}^l t(i_j) \,</math> และ <math> \sum_{j=1}^m t(i_j)\,</math> ใน <math> S_1 \, </math> และ <math> S_2 \, </math> ไม่เท่ากัน
+ให้ <math> l,m \, </math> เป็นผู้ใช้สองคนจากผู้ใช้ทั้งหมด <math> n \, </math> คน และให้การจัดลำดับการทำงานสองลำดับคือ <math> S_1,S_2 \, </math> ที่มีการจัดลำดับของผู้ใช้คนอื่น ๆ เหมือนกันหมด แต่ว่าต่างกันที่ลำดับการทำงานของผู้ใช้ คนที่ <math> l \,</math> กับ <math> m \, </math> เท่านั้น สมมติให้ลำดับที่หนึ่ง <math> S_1 \, </math> ให้งานของผู้ใช้คนที่ <math> l \, </math> ทำก่อนงานของผู้ใช้คนที่ <math> m \, </math> นั่นคือลำดับเป็นดังนี้ <math> i_1,i_2,...,i_l,i_m,...,i_n \,</math> ส่วนการจัดลำดับแบบที่สอง <math> S_2 \,</math> คือให้งานของผู้ใช้คนที่ <math> m \, </math> ทำก่อนงานของผู้ใช้คนที่ <math> l \, </math> นั่นคือลำดับเป็นดังนี้ <math> i_1,i_2,...,i_m,i_l,...,i_n \,</math> ดังนั้นเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ <math> S_1 \, </math> คือ <math> \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) \,</math> ส่วนเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ <math> S_2 \, </math> คือ <math> \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) \,</math> โดยที่ <math> \sum_{k=1}^{l-1}\sum_{j=1}^k t(i_j)=\sum_{k=1}^{m-1}\sum_{j=1}^k t(i_j) \,</math> และ <math> \sum_{k=m+1}^n \sum_{j=1}^k t(i_j)=\sum_{k=l+1}^n \sum_{j=1}^k t(i_j)\,</math> แต่ <math> \sum_{j=1}^l t(i_j) \,</math> และ <math> \sum_{j=1}^m t(i_j)\,</math> ใน <math> S_1 \, </math> และ <math> S_2 \, </math> ไม่เท่ากัน
 ==''การพิสูจน์ความถูกต้องของอัลกอริทึม''==

@@ แถว 5: / แถว 5: @@
 ==''ข้อสังเกต''==
-ให้ <math> l,m \, </math> เป็นผู้ใช้สองคนจากผู้ใช้ทั้งหมด <math> n \, </math> คน และให้การจัดลำดับการทำงานสองลำดับคือ <math> S_1,S_2 \, </math> ที่มีการจัดลำดับของผู้ใช้คนอื่น ๆ เหมือนกันหมด แต่ว่าต่างกันที่ลำดับการทำงานของผู้ใช้ คนที่ <math> l \,</math> กับ <math> m \, </math> เท่านั้น สมมติให้ลำดับที่หนึ่ง <math> S_1 \, </math> ให้งานของผู้ใช้คนที่ <math> l \, </math> ทำก่อนงานของผู้ใช้คนที่ <math> m \, </math> นั่นคือลำดับเป็นดังนี้ <math> i_1,i_2,...,i_l,i_m,...,i_n \,</math> ส่วนการจัดลำดับแบบที่สอง <math> S_2 \,</math> คือให้งานของผู้ใช้คนที่ <math> m \, </math> ทำก่อนงานของผู้ใช้คนที่ <math> l \, </math> นั่นคือลำดับเป็นดังนี้ <math> i_1,i_2,...,i_m,i_l,...,i_n \,</math> ดังนั้นเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ <math> S_1 \, </math> คือ <math> \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) \,</math> ส่วนเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ <math> S_2 \, </math> คือ <math> \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) \,</math> โดยที่ <math> \sum_{k=1}^{l-1}\sum_{j=1}^k t(i_j)=\sum_{k=1}^{m-1}\sum_{j=1}^k t(i_j) \,</math> และ <math> \sum_{k=m+1}^n \sum_{j=1}^k t(i_j)=\sum_{k=l+1}^n \sum_{j=1}^k t(i_j)\,</math>
+ให้ <math> l,m \, </math> เป็นผู้ใช้สองคนจากผู้ใช้ทั้งหมด <math> n \, </math> คน และให้การจัดลำดับการทำงานสองลำดับคือ <math> S_1,S_2 \, </math> ที่มีการจัดลำดับของผู้ใช้คนอื่น ๆ เหมือนกันหมด แต่ว่าต่างกันที่ลำดับการทำงานของผู้ใช้ คนที่ <math> l \,</math> กับ <math> m \, </math> เท่านั้น สมมติให้ลำดับที่หนึ่ง <math> S_1 \, </math> ให้งานของผู้ใช้คนที่ <math> l \, </math> ทำก่อนงานของผู้ใช้คนที่ <math> m \, </math> นั่นคือลำดับเป็นดังนี้ <math> i_1,i_2,...,i_l,i_m,...,i_n \,</math> ส่วนการจัดลำดับแบบที่สอง <math> S_2 \,</math> คือให้งานของผู้ใช้คนที่ <math> m \, </math> ทำก่อนงานของผู้ใช้คนที่ <math> l \, </math> นั่นคือลำดับเป็นดังนี้ <math> i_1,i_2,...,i_m,i_l,...,i_n \,</math> ดังนั้นเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ <math> S_1 \, </math> คือ <math> \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) \,</math> ส่วนเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ <math> S_2 \, </math> คือ <math> \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) \,</math> โดยที่ <math> \sum_{k=1}^{l-1}\sum_{j=1}^k t(i_j)=\sum_{k=1}^{m-1}\sum_{j=1}^k t(i_j) \,</math> และ <math> \sum_{k=m+1}^n \sum_{j=1}^k t(i_j)=\sum_{k=l+1}^n \sum_{j=1}^k t(i_j)\,</math>แต่ <math> \sum_{j=1}^l t(i_j) \,</math> และ <math> \sum_{j=1}^m t(i_j)\,</math> ใน <math> S_1 \, </math> และ <math> S_2 \, </math> ไม่เท่ากัน
 ==''การพิสูจน์ความถูกต้องของอัลกอริทึม''==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 18:57, 18 กันยายน 2552
แถว 4:		แถว 4:
	โจทย์ต้องการให้เวลาคอยรวมของผู้ใช้ทุกคนมีค่าน้อยที่สุด เขียนเป็นสมการทางคณิตศาสตร์คือต้องการให้ค่า <math>T = \sum_{k=1}^n \sum_{j=1}^k t(i_j) \,</math> มีค่าน้อยที่สุดนั่นเอง		โจทย์ต้องการให้เวลาคอยรวมของผู้ใช้ทุกคนมีค่าน้อยที่สุด เขียนเป็นสมการทางคณิตศาสตร์คือต้องการให้ค่า <math>T = \sum_{k=1}^n \sum_{j=1}^k t(i_j) \,</math> มีค่าน้อยที่สุดนั่นเอง

		+	==''ข้อสังเกต''==
		+	ให้ <math> l,m \, </math> เป็นผู้ใช้สองคนจากผู้ใช้ทั้งหมด <math> n \, </math> คน และให้การจัดลำดับการทำงานสองลำดับคือ <math> S_1,S_2 \, </math> ที่มีการจัดลำดับของผู้ใช้คนอื่น ๆ เหมือนกันหมด แต่ว่าต่างกันที่ลำดับการทำงานของผู้ใช้ คนที่ <math> l \,</math> กับ <math> m \, </math> เท่านั้น สมมติให้ลำดับที่หนึ่ง <math> S_1 \, </math> ให้งานของผู้ใช้คนที่ <math> l \, </math> ทำก่อนงานของผู้ใช้คนที่ <math> m \, </math> นั่นคือลำดับเป็นดังนี้ <math> i_1,i_2,...,i_l,i_m,...,i_n \,</math> ส่วนการจัดลำดับแบบที่สอง <math> S_2 \,</math> คือให้งานของผู้ใช้คนที่ <math> m \, </math> ทำก่อนงานของผู้ใช้คนที่ <math> l \, </math> นั่นคือลำดับเป็นดังนี้ <math> i_1,i_2,...,i_m,i_l,...,i_n \,</math> ดังนั้นเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ <math> S_1 \, </math> คือ <math> \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) \,</math> ส่วนเวลาคอยรวมของผู้ใช้จากการจัดลำดับแบบ <math> S_2 \, </math> คือ <math> \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) \,</math> โดยที่ <math> \sum_{k=1}^{l-1}\sum_{j=1}^k t(i_j)=\sum_{k=1}^{m-1}\sum_{j=1}^k t(i_j) \,</math> และ <math> \sum_{k=m+1}^n \sum_{j=1}^k t(i_j)=\sum_{k=l+1}^n \sum_{j=1}^k t(i_j)\,</math>

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