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

การแปลงปัญหา

สมมติว่าเราได้ทำการเลือกลำดับการส่งวิดีโอแล้ว นิยาม เป็นจำนวนบิตที่เราส่งโดยใช้ network link ตั้งแต่เวลา ถึงเวลา

ยกตัวอย่างเช่น ถ้าค่า และ เป็นไปตามที่กำหนดในโจทย์ และเราตัดสินใจส่งวิดิโอที่ 1, 2, และ 3 ตามลำดับแล้ว เราจะได้ว่า , , , และ

ให้ เราได้ว่าเราสามารถส่งวิดีโอต่างๆ ผ่าน network link โดยสอดคล้องกับกฎ (*) ถ้าหาก สำหรับ ทุกๆ ค่าที่ หรือกล่าวอีกอย่างหนึ่งคือ สำหรับ ทุกค่า

ดังนั้นเราสามารถแก้ปัญหาในโจทย์ได้อีกแบบหนึ่งดังต่อไปนี้: เราหาลำดับการส่งวิดีโอที่ทำให้ค่า ที่มากที่สุด (กล่าวคือ ) มีค่าน้อยที่สุดเท่าที่เป็นไปได้ ถ้าค่านี้มีค่ามากกว่า แสดงว่าเราไม่สามารถส่งวิดีโอตามกฎ (*) ได้เลย

ลำดับการส่งที่ทำให้ค่า มีค่าน้อยที่สุด

เราจะพิสูจน์ว่าลำดับการส่งที่ทำการส่งวิดีโอที่มีค่า น้อยกว่าก่อน (กล่าวคือนำวิดีโอมาเรียงตามค่า จากน้อยไปหามากแล้วส่งตามลำดับนั้น) จะทำให้ค่า มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้

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

สมมติว่าวิธีการส่งที่ดีที่สุดไม่เหมือนกับวิธีการส่งตามลำดับ แสดงว่าจะต้องมีวิดีโอ และ ที่ ถูกส่งก่อน แต่ นอกจากนี้เรายังสามารถสมมติเพิ่มเติมได้อีกว่าวิดีโอ เป็นวิดีโอที่ถูกส่งถัดจากวิดีโอ ด้วย เนื่องจากเรารู้ว่าถ้ามี inversion แล้วจะต้องมี inversion ที่ติดกันเสมอ

เราจะแสดงว่าเมื่อเราสลับเอาวิดีโอ ไปส่งก่อนวิดีโอ แล้ว ค่า จะไม่เพิ่มขึ้นแต่อย่างใด

สมมติว่าเราเริ่มส่งวิดีโอ ณ เวลา เราจะได้ว่าเราจะส่งมันเสร็จที่เวลา ซึ่งเราจะเริ่มส่งวิดีโอ และเราจะส่งวิดีโอ ที่เวลา ดังนั้นในช่วงเวลาตั้งแต่ ถึง ค่า จะมีค่าเพิ่มขึ้นวินาทีละ และในช่วงเวลาตั้งแต่ จนถึง ค่า จะมีค่าเพิ่มขึ้นวินาทีละ ซึ่งเราสามารถเขียนสรุปเป็นสัญลักษณ์ได้ดังต่อไปนี้

หลังจากสลับแล้วเราจะเริ่มส่งวิดีโอ ณ เวลา และจะส่งเสร็จที่เวลา ซึ่งในเวลาเดียวกันเราจะเริ่มส่งวิดีโอ และจะส่งมันเสร็จที่เวลา ให้ แทนจำนวนบิตที่ส่งผ่าน network link ตั้งแต่เวลา 0 ถึง หลังจากการสลับ เราจะได้ว่าตั้งแต่เวลา ถึง ค่า จะมีค่าเพิ่มขึ้นวินาทีละ ส่วนในเวลาตั้งแต่ ถึง ค่า จะเพิ่มขึ้นวินาทีละ ซึ่งเราสามารถเขียนสรุปเป็นสัญลักษณ์ได้ดังต่อไปนี้

เป้าหมายต่อไปของเราคือการพิสูจน์ lemma ต่อไปนี้

lemma 1: สำหรับจำนวนเต็ม ทุกตัวที่ เราได้ว่า

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

การพิสูจน์ Lemma 1

พิสูจน์: สำหรับจำนวนเต็ม ที่ นิยามค่า

เราจะแสดงว่า สำหรับ ทุกค่าที่

หากสามารถทำเช่นนี้ได้ เราก็จะสามารถสรุปได้ว่า สำหรับ ทุกค่า

การพิสูจน์ข้อวามทั้งสองข้อข้างบนนี้จะใช้ความจริงที่ว่า หลายครั้ง เราจะพิสูจน์ข้อความนี้เป็น lemma 2 หลังจากพิสูจน์ lemma 1

(ข้อความที่ 1) เราจะได้ว่า ถ้า แล้ว

ถ้า แล้ว

ดังนั้น ในกรณีนี้เช่นกัน

(ข้อความที่ 2) การพิสูจน์คล้ายๆ กับข้อความที่ 1 เราละให้นิสิตทำเป็นแบบฝึกหัด (จบการพิสูจน์ lemma 1)

lemma 2: ถ้า เป็นจำนวนที่มีค่าไม่เป็นลบโดยที่ แล้ว

พิสูจน์: เนื่องจาก เราจะได้ว่า ฉะนั้น ซึ่งหมายความว่า ฉะนั้น

การพิสูจน์ว่า ก็สามารถทำได้โดยการใช้เหตุผลแบบเดียวกันกับย่อหน้าที่แล้ว เราจึงละให้นิสิตทำเป็นแบบฝึกหัดไว้อีกโอกาสหนึ่ง (จบการพิสูจน์ lemma 2)

การหาค่า

เราทราบว่าการส่งวิดีโอโดยเรียงลำดับตาม จะทำให้่ีค่า มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ แต่ด้วยความรู้เพียงแค่นี้เราไม่สามารถตัดสินได้ว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่ เนื่องจากเราไม่ร้ค่า เราจึงจำเป็นต้องออกแบบอัลกอริทึมเพื่อหาค่าดังกล่าว

อย่างไรก็ดีค่า เราสามารถหาค่า เมื่อเราเรียงวิดีโอตาม ได้ง่ายมาก เราจะพิสูจน์ว่าค่านั้นคือ ซึ่งมีค่าเท่ากับจำนวนบิตที่ส่งทั้งหมดหารด้วยเวลาส่งทั้งหมด

lemma 3: ถ้าเราเรียงวิดีโอให้ แล้ว สำหรับค่า ทุกค่าที่ เราจะได้ว่า นอกจากนี้ ถ้าในช่วงเวลาตั้งแต่ ถึงเวลา เราทำการส่งวิีดีโด แล้วเราจะได้ว่า

พิสูจน์: เราจะทำการพิสูจน์โดยใช้ induction บนตัวแปร

(Base Case) ในกรณีนี้ เราได้ว่าในวินาทีแรกเราจะส่งข้อมูล บิตในเวลา 1 วินาที ดังนั้น ตามต้องการ

(Induction Case) สมมติให้ lemma เป็นจริงสำหรับ บางค่า พิจารณาเหตุการณ์ที่เกิดขึ้น ณ ช่วงเลาตั้งแต่ ถึง และสมมติว่าในช่วงเวลานี้เราทำการส่งวิดีโอ ผ่าน network link กล่าวคือในวินาทีนั้นเราส่งข้อมูลจำนวน บิต ในกรณีนี้มีความเป็นไปได้อยู่สองกรณี

กรณีแรกคือ เราเริ่มส่งวิดีโอ ตั้งแต่ก่อนเวลา อยู่แล้ว ในกรณีนี้สมมติฐานของ induction บอกเราว่า ฉะนั้นจาำก lemma 2 เราได้ว่า เนื่องจาก เราจึงได้ว่า ด้วย

กรณีที่สองคือ เราเริ่มส่งวิดีโอ ณ เวลา พอดี กล่าวคือในช่วงเวลาตั้งแต่ ถึง เราำกำลังส่งวิดีโอ อยู่ ในกรณีนี้สมมติฐานของ indunction บอกเราว่า และเราสามารถใช้เหตุผลในกรณีที่แล้วพิสูจน์ว่า lemma เป็นจริงสำหรับ ด้วยเช่นกัน

จาก lemma 3 เราได้ว่า

ฉะนั้นการหาว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่สามารถทำได้โดยการหาผลรวม และ แล้วตรวจสอบว่า มากกว่า หรือไม่ เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้ทำงานในเวลา