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

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

2009-09-18T17:41:49Z

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

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

2009-09-18T17:41:09Z

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

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

2009-09-18T17:38:16Z

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

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

2009-09-18T17:35:04Z

Aoy: /* อัลกอริทึม */

2009-09-18T17:34:31Z

อัลกอริทึม

Aoy: /* อัลกอริทึม */

2009-09-18T17:14:27Z

อัลกอริทึม

Aoy: หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''=='

2009-09-18T17:07:42Z

หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''=='

หน้าใหม่

==''อัลกอริทึม''==

@@ แถว 18: / แถว 18: @@
 และจะได้ว่าหลังการสลับ เวลา<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>
-จากสมการความไม่พอใจรวมข้างต้น และเนื่องจาก <math> w_j/t_j > w_i/t_i \,</math> เราจะได้ว่าหลังการสลับไม่ได้ทำให้ความไม่พอใจรวมเพิ่มขึ้น
+เมื่อพิจารณาสมการความไม่พอใจรวมก่อนและหลังสลับข้างต้น และเนื่องจาก <math> w_j/t_j > w_i/t_i \,</math> เราจะได้ว่าหลังการสลับไม่ได้ทำให้ความไม่พอใจรวมเพิ่มขึ้น
 ดังนั้นเราจึงสรุปได้ว่าการจัดลำดับการถ่ายเอกสารตามวิธี greedy algorithm ข้างต้น ทำให้ความไม่พอใจรวมของลูกค้าน้อยที่สุดเท่าที่จะเป็นไปได้แล้ว

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:41, 18 กันยายน 2552
แถว 17:		แถว 17:

	และจะได้ว่าหลังการสลับ เวลา<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>		และจะได้ว่าหลังการสลับ เวลา<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>
		+
		+	จากสมการความไม่พอใจรวมข้างต้น และเนื่องจาก <math> w_j/t_j > w_i/t_i \,</math> เราจะได้ว่าหลังการสลับไม่ได้ทำให้ความไม่พอใจรวมเพิ่มขึ้น
		+
		+	ดังนั้นเราจึงสรุปได้ว่าการจัดลำดับการถ่ายเอกสารตามวิธี greedy algorithm ข้างต้น ทำให้ความไม่พอใจรวมของลูกค้าน้อยที่สุดเท่าที่จะเป็นไปได้แล้ว

@@ แถว 8: / แถว 8: @@
 ให้ <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>
+สมมติว่า <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 ที่เรานำเสนอได้เสมอ
+จากในห้องเรียนเราได้ทำการพิสูจน์ไปแล้วว่า เมื่อมี inversion แล้วจะต้องมีคู่ของ inversion ที่ติดกัน กล่าวคือจะต้องมีงานของลูกค้าคนที่ <math> i \, </math> และ <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 ที่เรานำเสนอได้เสมอ
 ต่อไปเราต้องทำการพิสูจน์ให้ได้ว่า การสลับลำดับการถ่ายเอกสารข้างต้นจะไม่ทำให้ความไม่พอใจรวมของลูกค้าเพิ่มขึ้น

@@ แถว 14: / แถว 14: @@
 ต่อไปเราต้องทำการพิสูจน์ให้ได้ว่า การสลับลำดับการถ่ายเอกสารข้างต้นจะไม่ทำให้ความไม่พอใจรวมของลูกค้าเพิ่มขึ้น
-สมมติให้ก่อนการสลับ งานของลูกค้าคนที่ <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> 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>
+และจะได้ว่าหลังการสลับ เวลา<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
แถว 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:14, 18 กันยายน 2552
แถว 1:		แถว 1:
	==''อัลกอริทึม''==		==''อัลกอริทึม''==
		+	เรียงงานของลูกค้าตาม <math> w_i/t_i \, </math> จากมากไปหาน้อย แล้วถ่ายเอกสารตามลำดับนั้น จะได้ว่า อัลกอริทึมทำงานได้ในเวลา <math> O(n \log n) \,</math> ซึ่งใช้ในการเรียงลำดับนั่นเอง
		+
		+	โจทย์ต้องการให้ความไม่พอใจรวมของลูกค้ามีค่าน้อยที่สุด เขียนเป็นสมการทางคณิตศาสตร์คือต้องการให้ค่า <math> C_1w_1+C_2w_2+...+C_nw_n \,</math> มีค่าน้อยที่สุดนั่นเอง