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

Cardcaptor เมื่อ 16:01, 18 กันยายน 2552

2009-09-18T16:01:38Z

Cardcaptor เมื่อ 09:37, 18 กันยายน 2552

2009-09-18T09:37:28Z

Cardcaptor เมื่อ 09:35, 18 กันยายน 2552

2009-09-18T09:35:01Z

Cardcaptor เมื่อ 09:12, 18 กันยายน 2552

2009-09-18T09:12:53Z

Cardcaptor เมื่อ 09:07, 18 กันยายน 2552

2009-09-18T09:07:42Z

Cardcaptor: หน้าที่ถูกสร้างด้วย 'เราให้หมายเลขรถโดยให้รถคันแรกที่ออกจากกรุงเทพฯ…'

2009-09-18T08:49:16Z

หน้าที่ถูกสร้างด้วย 'เราให้หมายเลขรถโดยให้รถคันแรกที่ออกจากกรุงเทพฯ…'

หน้าใหม่

เราให้หมายเลขรถโดยให้รถคันแรกที่ออกจากกรุงเทพฯ เป็นรถหมายเลข 1 รถคันที่สองที่ออกจากกรุงเทพฯ เป็นรถหมายเลข 2 เช่นนี้ไปเรื่อยๆ

ให้ S เป็นวิธีการจัดของลงรถสักวิธีหนึ่ง สำหรับของชิ้นที่ <math>i \,</math> เราให้ <math>c_i^S \,</math> แทนหมายเลขของรถคันที่ของชิ้นที่ <math>i \,</math> ถูกบรรจุ สังเกตว่า <math>c_n^S \,</math> คือจำนวนรถที่ใช้ในการขนส่งของทั้งหมด

ให้ <math>G \,</math> เป็นวิธีการจัดของลงรถแบบ greedy ในโจทย์ และให้ <math>\mathrm{OPT} \,</math> เป็นวิธีการจัดของลงรถที่ใช้รถจำนวนน้อยคันที่สุดเท่าที่จะเป็นไปได้ ดังนั้นเราทราบว่า <math>c_n^{\mathrm{OPT}} \leq c_n^G \,</math>

เราจะพิสูจน์ว่า <math>c_i^G \leq c_i^{\mathrm{OPT}} \,</math> สำหรับ <math>i \,</math> ทุกค่าที่ <math>1 \leq i \leq n \,</math> ซึ่งถ้าเราพิสูจน์ข้อความนี้ได้แล้ว เราจะได้ว่า <math>c_n^G = c_n^{\mathrm{OPT}} \,</math> และนั่นหมายความว่า greedy algorithm ใช้รถน้อยค้นที่สุดเท่าที่จะเป็นไปได้แล้ว

การพิสูจน์ทำโดย strong induction บนตัวแปร i

(Base Case) ในกรณีนี้ <math>i = 1 \,</math> เราได้ว่า <math>c_1^G = 1 \leq c_1^{\mathrm{OPT}} \,</math> ดังนั้น base case เป็นความจริง

(Induction Case) สมมติว่ามีจำนวนเต็ม <math>i \geq 1 \,</math> ที่ทำให้ <math>c_k^G \leq c_k^{\mathrm{OPT}} \,</math> สำหรับค่า <math>k \,</math> ทุกค่าที่ <math>1 \leq k \leq i \,</math>

พิจารณาการบรรจุของชิ้นที่ <math>i+1 \,</math> ลงรถบรรทุก กรณีนี้มีความเป็นไปได้สองกรณี

'''กรณีที่ 1:''' ถ้า <math>c_i^G < c_i^{\mathrm{OPT}} \,</math> แล้วเราจะได้ว่า

@@ แถว 3: / แถว 3: @@
 ให้ S เป็นวิธีการจัดของลงรถสักวิธีหนึ่ง สำหรับของชิ้นที่ <math>i \,</math> เราให้ <math>c_i^S \,</math> แทนหมายเลขของรถคันที่ของชิ้นที่ <math>i \,</math> ถูกบรรจุ สังเกตว่า <math>c_i^S \,</math> คือจำนวนรถที่ใช้ในการขนส่งของ <math>i \,</math> ชิ้นแรก
-ยกตัวอย่างเช่น สมมติว่ารถแต่ละคันสามารถบรรทุกน้ำหนักได้ 10 หน่วย และให้ ของชื้นที่ 1 มีน้ำหนัก 5 หน่วย ของชิ้นที่สองมีน้ำหนัก 2 หน่วย ของชิ้นที่ 3 มีน้ำหนัก 1 หน่วย และของชิ้นที่ 4 มีน้ำหนัก 9 หน่วย
+<blockquote>
 วิธีการบรรจุของลงรถของมีได้หลายวิธี เช่น สมมติให้ <math>S \,</math> เป็นวิธีการบรรจุของลงรถให้แต่ละคันมีของเพียงแค่ชิ้นเดียว เราจะได้ว่าของชิ้นที่ 1 ลงรถหมายเลข 1 ของชิ้นที่สองลงรถหมายเลข 2 เช่นนี้ไปเรื่อยๆ ดังนั้นเราจะได้ว่า <math>c_1^S = 1 \,</math>, <math>c_2^S = 2 \,</math>, <math>c_3^S = 3 \,</math>, และ <math>c_4^S = 4 \,</math> เป็นค้น ถ้า <math>S \,</math>  เป็นวิธีการส่งของลงรถโดยที่รถหมายเลข 1 มีของชิ้นที่ 1 และ 2 ส่วนรถหมายเลข 2 มีของชิ้นที่ 3 และ 4 เราจะได้ว่า <math>c_1^S = c_2^S = 1 \,</math> และ <math>c_3^S = c_4^S = 2 \,</math>
 ให้ <math>G \,</math> เป็นวิธีการจัดของลงรถแบบ greedy ในโจทย์ และให้ <math>\mathrm{OPT} \,</math> เป็นวิธีการจัดของลงรถที่ใช้รถจำนวนน้อยคันที่สุดเท่าที่จะเป็นไปได้ ดังนั้นเราทราบว่า <math>c_n^{\mathrm{OPT}} \leq c_n^G \,</math>
-ในกรณีตัวอย่างข้างบน เราจะได้ว่า greedy algorithm จะบรรจุของชิ้นที่ 1, 2, และ 3 ลงในรถหมายเลข 1 และของชิ้นที่ 4 ลงในรถหมายเลข 2 ดังนั้น <math>c_1^G = c_2^G = c_3^G = 1 \,</math> และ <math>c_4^G = 2 \,</math> สำหรับตัวอย่างนี้ เราเห็นได้อย่างชัดเจนว่าต้องใช้รถอย่างน้อยสองคัน ดังนั้น greedy algorithm จึงใช้รถเป็นจำนวนน้อยที่สุดในกรณีนี้ แต่วิธีการจัดของลงรถบรรทุกให้ใช้รถเพียงแค่สองคันมีอยู่ได้หลายวิธี และ <math>\mathrm{OPT} \,</math> จะเป็นวิธีไหนในวิธีการจัดแบบนั้นก็ได้ เช่น เราจะบอกว่า <math>\mathrm{OPT} \,</math> คือ การจัดของทีใส่ของชิ้นที่ 1 และชิ้นที่ 2 ลงไปในรถคันที่ 1 และของชิ้นที่ 3 และ 4 ลงในรถคันที่ 2 ก็ได้ ดังนั้น <math>c_1^{\mathrm{OPT}} = c_2^{\mathrm{OPT}} = 1 \,</math> และ <math>c_3^{\mathrm{OPT}} = c_4^{\mathrm{OPT}} = 2 \,</math>
+<blockquote>
-การพิสูจน์ทำโดย strong induction บนตัวแปร i
+<hr />
 (Base Case) ในกรณีนี้ <math>i = 1 \,</math> เราได้ว่า <math>c_1^G = 1 \leq c_1^{\mathrm{OPT}} \,</math> (เนื่องจาก greedy algorithm จะจัดของชิ้นแรกใส่รถหมายเลข 1 เลย) ดังนั้น base case เป็นความจริง
@@ แถว 33: / แถว 39: @@
 ด้วยเหตุนี้ในการจัดของชิ้นที่ <math>i+1 \,</math> ลงรถ จึงไม่มีทางเป็นไปได้ที่ greedy algorithm จะใช้จำนวนรถมากกว่า <math>\mathrm{OPT} \,</math> เพราะ greedy algorithm จะจัดของชิ้นที่ <math>i+1 \,</math> ลวรถหมายเลข <math>c_i^G \,</math> ทันทีถ้ามีที่ว่างพอ กล่าวคือ <math>c_{i+1}^G \leq c_{i+1}^{\mathrm{OPT}} \,</math>
-ดังนั้นเราสามารถสรุปได้ว่า <math>c_i^G \leq c_i^{\mathrm{OPT}} \,</math> สำหรับ <math>i \,</math> ทุกค่าที่ <math>1 \leq i \leq n \,</math> เพราะฉะนั้น greedy algorithm ในโจทย์จึงใช้รถจำนวนน้อยคันที่สุดเท่าที่จะเป็นไปได้
+ดังนั้นเราสามารถสรุปได้ว่า <math>c_i^G \leq c_i^{\mathrm{OPT}} \,</math> สำหรับ <math>i \,</math> ทุกค่าที่ <math>1 \leq i \leq n \,</math>  (จบการพิสูจน์ lemma 1)

@@ แถว 29: / แถว 29: @@
 จากสมมติฐานของ induction เราทราบว่า <math>c_k^G \leq c_k^{\mathrm{OPT}} \,</math> สำหรับค่า <math>k \,</math> ทุกค่าที่ <math>1 \leq k \leq i \,</math> ดังนั้นถ้า <math>c_k^G = c_i^G \,</math> และเราจะได้ว่า <math>c_k^{\mathrm{OPT}} \,</math> จะต้องมีค่าเท่ากับ <math>c_i^G \,</math> ด้วยเสมอ เนื่องจาก <math>c_i^G = c_k^G \leq c_k^{\mathrm{OPT}} \leq c_i^{\mathrm{OPT}} \leq c_i^G \,</math>
-เราจึงสามารถสรุปได้ว่า สำหรับของทุกชิ้นที่ greedy algorithm ใส่ลงในรถหมายเลข <math>c_i^G \,</math> เราจะได้ว่า <math>\mathrm{OPT} \,</math> ก็จะใส่มันลงในรถหมายเลข <math>c_i^G \,</math> ด้วย เพราะฉะนั้น <math>greedy algorithm \,</math> จะทำให้รถคันที่ <math>c_i^G \,</math> มีที่ว่างเหลือไม่น้อยกว่าที่ว่างที่เกิดจากวิธีการจัดของของ <math>\mathrm{OPT} \,</math> เสมอ
+เราจึงสามารถสรุปได้ว่า สำหรับของทุกชิ้นที่ greedy algorithm ใส่ลงในรถหมายเลข <math>c_i^G \,</math> เราจะได้ว่า <math>\mathrm{OPT} \,</math> ก็จะใส่มันลงในรถหมายเลข <math>c_i^G \,</math> ด้วย เพราะฉะนั้น greedy algorithm จะทำให้รถคันที่ <math>c_i^G \,</math> มีที่ว่างเหลือไม่น้อยกว่าที่ว่างที่เกิดจากวิธีการจัดของของ <math>\mathrm{OPT} \,</math> เสมอ
 ด้วยเหตุนี้ในการจัดของชิ้นที่ <math>i+1 \,</math> ลงรถ จึงไม่มีทางเป็นไปได้ที่ greedy algorithm จะใช้จำนวนรถมากกว่า <math>\mathrm{OPT} \,</math> เพราะ greedy algorithm จะจัดของชิ้นที่ <math>i+1 \,</math> ลวรถหมายเลข <math>c_i^G \,</math> ทันทีถ้ามีที่ว่างพอ กล่าวคือ <math>c_{i+1}^G \leq c_{i+1}^{\mathrm{OPT}} \,</math>
 ดังนั้นเราสามารถสรุปได้ว่า <math>c_i^G \leq c_i^{\mathrm{OPT}} \,</math> สำหรับ <math>i \,</math> ทุกค่าที่ <math>1 \leq i \leq n \,</math> เพราะฉะนั้น greedy algorithm ในโจทย์จึงใช้รถจำนวนน้อยคันที่สุดเท่าที่จะเป็นไปได้

@@ แถว 1: / แถว 1: @@
 เราให้หมายเลขรถโดยให้รถคันแรกที่ออกจากกรุงเทพฯ เป็นรถหมายเลข 1 รถคันที่สองที่ออกจากกรุงเทพฯ เป็นรถหมายเลข 2 เช่นนี้ไปเรื่อยๆ
-ให้ S เป็นวิธีการจัดของลงรถสักวิธีหนึ่ง สำหรับของชิ้นที่ <math>i \,</math> เราให้ <math>c_i^S \,</math> แทนหมายเลขของรถคันที่ของชิ้นที่ <math>i \,</math> ถูกบรรจุ สังเกตว่า <math>c_n^S \,</math> คือจำนวนรถที่ใช้ในการขนส่งของทั้งหมด
+ให้ S เป็นวิธีการจัดของลงรถสักวิธีหนึ่ง สำหรับของชิ้นที่ <math>i \,</math> เราให้ <math>c_i^S \,</math> แทนหมายเลขของรถคันที่ของชิ้นที่ <math>i \,</math> ถูกบรรจุ สังเกตว่า <math>c_i^S \,</math> คือจำนวนรถที่ใช้ในการขนส่งของ <math>i \,</math> ชิ้นแรก
 ยกตัวอย่างเช่น สมมติว่ารถแต่ละคันสามารถบรรทุกน้ำหนักได้ 10 หน่วย และให้ ของชื้นที่ 1 มีน้ำหนัก 5 หน่วย ของชิ้นที่สองมีน้ำหนัก 2 หน่วย ของชิ้นที่ 3 มีน้ำหนัก 1 หน่วย และของชิ้นที่ 4 มีน้ำหนัก 9 หน่วย
@@ แถว 21: / แถว 21: @@
 พิจารณาการบรรจุของชิ้นที่ <math>i+1 \,</math> ลงรถบรรทุก กรณีนี้มีความเป็นไปได้สองกรณี
-'''กรณีที่ 1:''' ถ้า <math>c_i^G < c_i^{\mathrm{OPT}} \,</math> ซึ่งหมายความว่า greedy algorithm ใข้รถ''น้อยกว่า'' <math>\mathrm{OPT} \,</math> ในการส่งของ <math>i \,</math> ชิ้นแรก เราจะได้ว่าในการส่งของชิ้นที่ <math>i+1 \,</math> greedy algorithm จะใช้รถไม่เกิน <math>c_{i}^G + 1 \,</math> คัน (เนื่องจาก greedy algorithm อาจจะเอาของชิ้นที่ <math>i+1 \,</math> ไปใส่ในรถคันใหม่) และ <math>\mathrm{OPT} \,</math> จะต้องนำของชิ้นที่ <math>i+1 \,</math> ไปใส่ในรถหมายเลข <math>c_i^{\mathrm{OPT}} \,</math> หรือไม่ก็ <math>c_i^{\mathrm{OPT}}+1 \,</math> ฉะนั้นเราจะได้ว่า <math>c_{i+1}^G \leq c_i^G+1 \leq c_i^{\mathrm{OPT}} \leq c_{i+1}^{\mathrm{OPT}} \,</math> ตามต้องการ
+'''กรณีที่ 1:''' ถ้า <math>c_i^G < c_i^{\mathrm{OPT}} \,</math> ซึ่งหมายความว่า greedy algorithm ใข้รถ''น้อยกว่า'' <math>\mathrm{OPT} \,</math> ในการส่งของ <math>i \,</math> ชิ้นแรก แล้วเราจะได้ว่าในการส่งของชิ้นที่ <math>i+1 \,</math> greedy algorithm จะใช้รถไม่เกิน <math>c_{i}^G + 1 \,</math> คัน (เนื่องจาก greedy algorithm อาจจะเอาของชิ้นที่ <math>i+1 \,</math> ไปใส่ในรถคันใหม่) และ <math>\mathrm{OPT} \,</math> จะต้องนำของชิ้นที่ <math>i+1 \,</math> ไปใส่ในรถหมายเลข <math>c_i^{\mathrm{OPT}} \,</math> หรือไม่ก็ <math>c_i^{\mathrm{OPT}}+1 \,</math> ฉะนั้นเราจะได้ว่า <math>c_{i+1}^G \leq c_i^G+1 \leq c_i^{\mathrm{OPT}} \leq c_{i+1}^{\mathrm{OPT}} \,</math> ตามต้องการ

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:12, 18 กันยายน 2552
แถว 21:		แถว 21:
	พิจารณาการบรรจุของชิ้นที่ <math>i+1 \,</math> ลงรถบรรทุก กรณีนี้มีความเป็นไปได้สองกรณี		พิจารณาการบรรจุของชิ้นที่ <math>i+1 \,</math> ลงรถบรรทุก กรณีนี้มีความเป็นไปได้สองกรณี

−	'''กรณีที่ 1:''' ถ้า <math>c_i^G < c_i^{\mathrm{OPT}} \,</math> ~~แล้วเราจะได้ว่า~~	+	'''กรณีที่ 1:''' ถ้า <math>c_i^G < c_i^{\mathrm{OPT}} \,</math> ซึ่งหมายความว่า greedy algorithm ใข้รถ''น้อยกว่า'' <math>\mathrm{OPT} \,</math> ในการส่งของ <math>i \,</math> ชิ้นแรก เราจะได้ว่าในการส่งของชิ้นที่ <math>i+1 \,</math> greedy algorithm จะใช้รถไม่เกิน <math>c_{i}^G + 1 \,</math> คัน (เนื่องจาก greedy algorithm อาจจะเอาของชิ้นที่ <math>i+1 \,</math> ไปใส่ในรถคันใหม่) และ <math>\mathrm{OPT} \,</math> จะต้องนำของชิ้นที่ <math>i+1 \,</math> ไปใส่ในรถหมายเลข <math>c_i^{\mathrm{OPT}} \,</math> หรือไม่ก็ <math>c_i^{\mathrm{OPT}}+1 \,</math> ฉะนั้นเราจะได้ว่า <math>c_{i+1}^G \leq c_i^G+1 \leq c_i^{\mathrm{OPT}} \leq c_{i+1}^{\mathrm{OPT}} \,</math> ตามต้องการ

@@ แถว 2: / แถว 2: @@
 ให้ S เป็นวิธีการจัดของลงรถสักวิธีหนึ่ง สำหรับของชิ้นที่ <math>i \,</math> เราให้ <math>c_i^S \,</math> แทนหมายเลขของรถคันที่ของชิ้นที่ <math>i \,</math> ถูกบรรจุ สังเกตว่า <math>c_n^S \,</math> คือจำนวนรถที่ใช้ในการขนส่งของทั้งหมด
 ให้ <math>G \,</math> เป็นวิธีการจัดของลงรถแบบ greedy ในโจทย์ และให้ <math>\mathrm{OPT} \,</math> เป็นวิธีการจัดของลงรถที่ใช้รถจำนวนน้อยคันที่สุดเท่าที่จะเป็นไปได้ ดังนั้นเราทราบว่า <math>c_n^{\mathrm{OPT}} \leq c_n^G \,</math>
 เราจะพิสูจน์ว่า <math>c_i^G \leq c_i^{\mathrm{OPT}} \,</math> สำหรับ <math>i \,</math> ทุกค่าที่ <math>1 \leq i \leq n \,</math> ซึ่งถ้าเราพิสูจน์ข้อความนี้ได้แล้ว เราจะได้ว่า <math>c_n^G = c_n^{\mathrm{OPT}} \,</math> และนั่นหมายความว่า greedy algorithm ใช้รถน้อยค้นที่สุดเท่าที่จะเป็นไปได้แล้ว
@@ แถว 9: / แถว 15: @@
 การพิสูจน์ทำโดย strong induction บนตัวแปร i
-(Base Case) ในกรณีนี้ <math>i = 1 \,</math> เราได้ว่า <math>c_1^G = 1 \leq c_1^{\mathrm{OPT}} \,</math> ดังนั้น base case เป็นความจริง
+(Base Case) ในกรณีนี้ <math>i = 1 \,</math> เราได้ว่า <math>c_1^G = 1 \leq c_1^{\mathrm{OPT}} \,</math> (เนื่องจาก greedy algorithm จะจัดของชิ้นแรกใส่รถหมายเลข 1 เลย) ดังนั้น base case เป็นความจริง
 (Induction Case) สมมติว่ามีจำนวนเต็ม <math>i \geq 1 \,</math> ที่ทำให้ <math>c_k^G \leq c_k^{\mathrm{OPT}} \,</math> สำหรับค่า <math>k \,</math> ทุกค่าที่ <math>1 \leq k \leq i \,</math>