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

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

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

ตัวอย่าง สมมติว่ารถแต่ละคันสามารถบรรทุกน้ำหนักได้ 10 หน่วย และให้ ของชื้นที่ 1 มีน้ำหนัก 5 หน่วย ของชิ้นที่สองมีน้ำหนัก 2 หน่วย ของชิ้นที่ 3 มีน้ำหนัก 1 หน่วย และของชิ้นที่ 4 มีน้ำหนัก 9 หน่วย

วิธีการบรรจุของลงรถของมีได้หลายวิธี เช่น สมมติให้ $S\,$ เป็นวิธีการบรรจุของลงรถให้แต่ละคันมีของเพียงแค่ชิ้นเดียว เราจะได้ว่าของชิ้นที่ 1 ลงรถหมายเลข 1 ของชิ้นที่สองลงรถหมายเลข 2 เช่นนี้ไปเรื่อยๆ ดังนั้นเราจะได้ว่า $c_{1}^{S}=1\,$, $c_{2}^{S}=2\,$, $c_{3}^{S}=3\,$, และ $c_{4}^{S}=4\,$ เป็นค้น ถ้า $S\,$ เป็นวิธีการส่งของลงรถโดยที่รถหมายเลข 1 มีของชิ้นที่ 1 และ 2 ส่วนรถหมายเลข 2 มีของชิ้นที่ 3 และ 4 เราจะได้ว่า $c_{1}^{S}=c_{2}^{S}=1\,$ และ $c_{3}^{S}=c_{4}^{S}=2\,$

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

ตัวอย่าง ในกรณีตัวอย่างข้างบน เราจะได้ว่า greedy algorithm จะบรรจุของชิ้นที่ 1, 2, และ 3 ลงในรถหมายเลข 1 และของชิ้นที่ 4 ลงในรถหมายเลข 2 ดังนั้น $c_{1}^{G}=c_{2}^{G}=c_{3}^{G}=1\,$ และ $c_{4}^{G}=2\,$ สำหรับตัวอย่างนี้ เราเห็นได้อย่างชัดเจนว่าต้องใช้รถอย่างน้อยสองคัน ดังนั้น greedy algorithm จึงใช้รถเป็นจำนวนน้อยที่สุดในกรณีนี้ แต่วิธีการจัดของลงรถบรรทุกให้ใช้รถเพียงแค่สองคันมีอยู่ได้หลายวิธี และ $\mathrm {OPT} \,$ จะเป็นวิธีไหนในวิธีการจัดแบบนั้นก็ได้ เช่น เราจะบอกว่า $\mathrm {OPT} \,$ คือ การจัดของทีใส่ของชิ้นที่ 1 และชิ้นที่ 2 ลงไปในรถคันที่ 1 และของชิ้นที่ 3 และ 4 ลงในรถคันที่ 2 ก็ได้ ดังนั้น $c_{1}^{\mathrm {OPT} }=c_{2}^{\mathrm {OPT} }=1\,$ และ $c_{3}^{\mathrm {OPT} }=c_{4}^{\mathrm {OPT} }=2\,$

---

lemma 1: $c_{i}^{G}\leq c_{i}^{\mathrm {OPT} }\,$ สำหรับ $i\,$ ทุกค่าที่ $1\leq i\leq n\,$

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

(Base Case) ในกรณีนี้ $i=1\,$ เราได้ว่า $c_{1}^{G}=1\leq c_{1}^{\mathrm {OPT} }\,$ (เนื่องจาก greedy algorithm จะจัดของชิ้นแรกใส่รถหมายเลข 1 เลย) ดังนั้น base case เป็นความจริง

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

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

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

กรณีที่ 2: ถ้า $c_{i}^{G}=c_{i}^{\mathrm {OPT} }\,$ แล้วเราจะได้ว่าทั้ง greedy algorithm และ $\mathrm {OPT} \,$ ใส่ของชิ้นที่ $i\,$ ลงไปในรถหมายเลข $c_{i}^{G}\,$ เหมือนกัน เราจะพิสูจน์ว่าวิธีการจัดของของ greedy algorithm จะทำให้รถหมายเลข $c_{i}^{G}\,$ มีที่ว่างเหลือมากกว่า $\mathrm {OPT} \,$

พิจารณาของที่ถูกจัดให้อยู่ในรถหมายเลข $c_{i}^{G}\,$ ในกรณีของ greedy algorithm เราจะได้ว่ามันคือของชิ้นที่ $k\,$ ทุกชิ้นซึ่ง $c_{k}^{G}=c_{i}^{G}\,$ และในกรณีของ $\mathrm {OPT} \,$ มันคือของชิ้นที่ $k\,$ ทุกชิ้นที่ $c_{k}^{\mathrm {OPT} }=c_{i}^{\mathrm {OPT} }=c_{i}^{G}\,$

จากสมมติฐานของ induction เราทราบว่า $c_{k}^{G}\leq c_{k}^{\mathrm {OPT} }\,$ สำหรับค่า $k\,$ ทุกค่าที่ $1\leq k\leq i\,$ ดังนั้นถ้า $c_{k}^{G}=c_{i}^{G}\,$ และเราจะได้ว่า $c_{k}^{\mathrm {OPT} }\,$ จะต้องมีค่าเท่ากับ $c_{i}^{G}\,$ ด้วยเสมอ เนื่องจาก $c_{i}^{G}=c_{k}^{G}\leq c_{k}^{\mathrm {OPT} }\leq c_{i}^{\mathrm {OPT} }\leq c_{i}^{G}\,$

เราจึงสามารถสรุปได้ว่า สำหรับของทุกชิ้นที่ greedy algorithm ใส่ลงในรถหมายเลข $c_{i}^{G}\,$ เราจะได้ว่า $\mathrm {OPT} \,$ ก็จะใส่มันลงในรถหมายเลข $c_{i}^{G}\,$ ด้วย เพราะฉะนั้น greedy algorithm จะทำให้รถคันที่ $c_{i}^{G}\,$ มีที่ว่างเหลือไม่น้อยกว่าที่ว่างที่เกิดจากวิธีการจัดของของ $\mathrm {OPT} \,$ เสมอ

ด้วยเหตุนี้ในการจัดของชิ้นที่ $i+1\,$ ลงรถ จึงไม่มีทางเป็นไปได้ที่ greedy algorithm จะใช้จำนวนรถมากกว่า $\mathrm {OPT} \,$ เพราะ greedy algorithm จะจัดของชิ้นที่ $i+1\,$ ลวรถหมายเลข $c_{i}^{G}\,$ ทันทีถ้ามีที่ว่างพอ กล่าวคือ $c_{i+1}^{G}\leq c_{i+1}^{\mathrm {OPT} }\,$

ดังนั้นเราสามารถสรุปได้ว่า $c_{i}^{G}\leq c_{i}^{\mathrm {OPT} }\,$ สำหรับ $i\,$ ทุกค่าที่ $1\leq i\leq n\,$ (จบการพิสูจน์ lemma 1)

---

จาก lemma 1 เราจะได้ว่า $c_{n}^{G}=c_{n}^{\mathrm {OPT} }\,$ ซึ่งหมายความว่า greedy algorithm ใช้รถน้อยค้นที่สุดเท่าที่จะเป็นไปได้แล้ว