418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 6
การแปลงปัญหา
สมมติว่าเราได้ทำการเลือกลำดับการส่งวิดีโอแล้ว นิยาม เป็นจำนวนบิตที่เราส่งโดยใช้ network link ตั้งแต่เวลา ถึงเวลา
ยกตัวอย่างเช่น ถ้าค่า และ เป็นไปตามที่กำหนดในโจทย์ และเราตัดสินใจส่งวิดิโอที่ 1, 2, และ 3 ตามลำดับแล้ว เราจะได้ว่า , , , และ
ให้ เราได้ว่าเราสามารถส่งวิดีโอต่างๆ ผ่าน network link โดยสอดคล้องกับกฎ (*) ถ้าหาก สำหรับ ทุกๆ ค่าที่ หรือกล่าวอีกอย่างหนึ่งคือ สำหรับ ทุกค่า
ดังนั้นเราสามารถแก้ปัญหาในโจทย์ได้อีกแบบหนึ่งดังต่อไปนี้: เราหาลำดับการส่งวิดีโอที่ทำให้ค่า ที่มากที่สุด (กล่าวคือ ) มีค่าน้อยที่สุดเท่าที่เป็นไปได้ ถ้าค่านี้มีค่ามากกว่า แสดงว่าเราไม่สามารถส่งวิดีโอตามกฎ (*) ได้เลย
ลำดับการส่งที่ทำให้ค่า มีค่าน้อยที่สุด
เราจะพิสูจน์ว่าลำดับการส่งที่ทำการส่งวิดีโอที่มีค่า น้อยกว่าก่อน (กล่าวคือนำวิดีโอมาเรียงตามค่า จากน้อยไปหามากแล้วส่งตามลำดับนั้น) จะทำให้ค่า มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้
เราจะทำการพิสูจน์นี้ด้วย exchange argument ซึ่งเราจะแสดงว่าเราสามารถแปลงวิธีการส่งที่ทำให้ค่า มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ (ตั้งแต่บัดนี้เราจะเรียกมันว่า "วิธีการส่งที่ดีที่สุด") ไปเป็นการส่งที่ส่งตามลำดับค่า จากน้อยไปมาก โดยไม่ทำให้ค่า มีค่ามากขึ้น
สมมติว่าวิธีการส่งที่ดีที่สุดไม่เหมือนกับวิธีการส่งตามลำดับ แสดงว่าจะต้องมีวิดีโอ และ ที่ ถูกส่งก่อน แต่ นอกจากนี้เรายังสามารถสมมติเพิ่มเติมได้อีกว่าวิดีโอ เป็นวิดีโอที่ถูกส่งถัดจากวิดีโอ ด้วย เนื่องจากเรารู้ว่าถ้ามี inversion แล้วจะต้องมี inversion ที่ติดกันเสมอ
เราจะแสดงว่าเมื่อเราสลับเอาวิดีโอ ไปส่งก่อนวิดีโอ แล้ว ค่า จะไม่เพิ่มขึ้นแต่อย่างใด
สมมติว่าเราเริ่มส่งวิดีโอ ณ เวลา เราจะได้ว่าเราจะส่งมันเสร็จที่เวลา ซึ่งเราจะเริ่มส่งวิดีโอ และเราจะส่งวิดีโอ ที่เวลา ดังนั้นในช่วงเวลาตั้งแต่ ถึง ค่า จะมีค่าเพิ่มขึ้นวินาทีละ และในช่วงเวลาตั้งแต่ จนถึง ค่า จะมีค่าเพิ่มขึ้นวินาทีละ ซึ่งเราสามารถเขียนสรุปเป็นสัญลักษณ์ได้ดังต่อไปนี้
หลังจากสลับแล้วเราจะเริ่มส่งวิดีโอ ณ เวลา และจะส่งเสร็จที่เวลา ซึ่งในเวลาเดียวกันเราจะเริ่มส่งวิดีโอ และจะส่งมันเสร็จที่เวลา ให้ แทนจำนวนบิตที่ส่งผ่าน network link ตั้งแต่เวลา 0 ถึง หลังจากการสลับ เราจะได้ว่าตั้งแต่เวลา ถึง ค่า จะมีค่าเพิ่มขึ้นวินาทีละ ส่วนในเวลาตั้งแต่ ถึง ค่า จะเพิ่มขึ้นวินาทีละ ซึ่งเราสามารถเขียนสรุปเป็นสัญลักษณ์ได้ดังต่อไปนี้
เป้าหมายต่อไปของเราคือการพิสูจน์ lemma ต่อไปนี้
- lemma 1: สำหรับจำนวนเต็ม ทุกตัวที่ เราได้ว่า
โดยที่หาก lemma นี้เป็นจริง เราจะได้ว่า เนื่องจาก สมมติให้ โดยที่ เป็นจำนวนเต็มตัวหนึ่งที่อยู่ในช่วง แล้ว เราจะได้ว่า ฉะนั้นเราจึงสามารถสรุปได้ว่าหลังจากสลับแล้ว จะมีค่าไม่เพิ่มขึ้น และการส่งวิดีโอตามลำดับ จากมากไปน้อยทำให้ค่า ต่ำที่สุดเท่าที่จะเป็นไปได้
![{\displaystyle [s,s+t_{i}+t_{j}]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b10818c2b484701164854d36b46c12a17f6b8aa)
การพิสูจน์ 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 เราได้ว่า
ฉะนั้นการหาว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่สามารถทำได้โดยการหาผลรวม และ แล้วตรวจสอบว่า มากกว่า หรือไม่ เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้ทำงานในเวลา
