ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 6"
Cardcaptor (คุย | มีส่วนร่วม) |
|||
| แถว 95: | แถว 95: | ||
== การหาค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> == | == การหาค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> == | ||
| + | เราทราบว่าการส่งวิดีโอโดยเรียงลำดับตาม <math>b_i/t_i \,</math> จะทำให้่ีค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ แต่ด้วยความรู้เพียงแค่นี้เราไม่สามารถตัดสินได้ว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่ เนื่องจากเราไม่ร้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> เราจึงจำเป็นต้องออกแบบอัลกอริทึมเพื่อหาค่าดังกล่าว | ||
| + | |||
| + | อย่างไรก็ดีค่า เราสามารถหาค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> เมื่อเราเรียงวิดีโอตาม <math>b_i/t_i \,</math> ได้ง่ายมาก เราจะพิสูจน์ว่าค่านั้นคือ <math>B_T / T \,</math> ซึ่งมีค่าเท่ากับจำนวนบิตที่ส่งทั้งหมดหารด้วยเวลาส่งทั้งหมด | ||
| + | |||
| + | '''lemma 3''': ถ้าเราเรียงวิดีโอให้ <math>\frac{b_1}{t_1} \leq \frac{b_2}{t_2} \leq \dotsb \leq \frac{b_n}{t_n} \,</math> แล้ว สำหรับค่า <math>t \,</math> ทุกค่าที่ <math>1 \leq t \leq T \,</math> เราจะได้ว่า <math>\frac{B_1}{1} \leq \frac{B_2}{2} \leq \frac{B_3}{3} \leq \dotsb \leq \frac{B_t}{t} \,</math> นอกจากนี้ ถ้าในช่วงเวลาตั้งแต่ <math>t-1 \,</math> ถึงเวลา <math>t \,</math> เราทำการส่งวิีดีโด <math>i \,</math> แล้วเราจะได้ว่า <math>\frac{B_t}{t} \leq \frac{b_i}{t_i} \,</math> | ||
| + | |||
| + | '''พิสูจน์:''' เราจะทำการพิสูจน์โดยใช้ induction บนตัวแปร <math>t \,</math> | ||
| + | |||
| + | (Base Case) ในกรณีนี้ <math>t = 1 \,</math> เราได้ว่าในวินาทีแรกเราจะส่งข้อมูล <math>b_1/t_1 \,</math> บิตในเวลา 1 วินาที ดังนั้น <math>\frac{B_1}{1} \leq \frac{b_1}{t_1} \,</math> ตามต้องการ | ||
| + | |||
| + | (Induction Case) สมมติให้ lemma เป็นจริงสำหรับ <math>t \geq 1 \,</math> บางค่า พิจารณาเหตุการณ์ที่เกิดขึ้น ณ ช่วงเลาตั้งแต่ <math>t \,</math> ถึง <math>t+1 \,</math> และสมมติว่าในช่วงเวลานี้เราทำการส่งวิดีโอ <math>i \,</math> ผ่าน network link กล่าวคือในวินาทีนั้นเราส่งข้อมูลจำนวน <math>\frac{b_i}{t_i} \,</math> บิต ในกรณีนี้มีความเป็นไปได้อยู่สองกรณี | ||
| + | |||
| + | กรณีแรกคือ เราเริ่มส่งวิดีโอ <math>i \,</math> ตั้งแต่ก่อนเวลา <math>t \,</math> อยู่แล้ว ในกรณีนี้สมมติฐานของ induction บอกเราว่า <math>\frac{B_t}{t} \leq \frac{b_i}{t_i} = \frac{b_i/t_i}{1} \,</math> ฉะนั้นจาำก lemma 2 เราได้ว่า <math>\frac{B_t}{t} \leq \frac{B_t + b_i/t_i}{t+1} \leq \frac{b_i/t_i}{1} = \frac{b_i}{t_i} \,</math> เนื่องจาก <math>\frac{B_{t+1}}{t+1} = \frac{B_t + b_i/t_i}{t+1} \,</math> เราจึงได้ว่า <math>\frac{B_t}{t} \leq \frac{B_{t+1}}{t+1} \,</math> ด้วย | ||
| + | |||
| + | กรณีที่สองคือ เราเริ่มส่งวิดีโอ <math>i \,</math> ณ เวลา <math>t \,</math> พอดี กล่าวคือในช่วงเวลาตั้งแต่ <math>t-1 \,</math> ถึง <math>t \,</math> เราำกำลังส่งวิดีโอ <math>i-1 \,</math> อยู่ ในกรณีนี้สมมติฐานของ indunction บอกเราว่า <math>\frac{B_t}{t} \leq \frac{b_{i-1}}{t_{i-1}} \leq \frac{b_i}{t_i} \,</math> และเราสามารถใช้เหตุผลในกรณีที่แล้วพิสูจน์ว่า lemma เป็นจริงสำหรับ <math>t+1 \,</math> ด้วยเช่นกัน | ||
| + | |||
| + | |||
| + | จาก lemma 3 เราได้ว่า <math>\max_{1 \leq t \leq T} B_t/t = B_T/T \,</math> | ||
| + | |||
| + | ฉะนั้นการหาว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่สามารถทำได้โดยการหาผลรวม <math>B_T = \sum_{i=1}^n b_i \,</math> และ <math>T = \sum_{i=1}^n t_i \,</math> แล้วตรวจสอบว่า <math>B_T/T \,</math> มากกว่า <math>r \,</math> หรือไม่ เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้ทำงานในเวลา <math>O(n) \,</math> | ||
รุ่นแก้ไขปัจจุบันเมื่อ 15:06, 18 กันยายน 2552
การแปลงปัญหา
สมมติว่าเราได้ทำการเลือกลำดับการส่งวิดีโอแล้ว นิยาม เป็นจำนวนบิตที่เราส่งโดยใช้ 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 เราได้ว่า
ฉะนั้นการหาว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่สามารถทำได้โดยการหาผลรวม และ แล้วตรวจสอบว่า มากกว่า หรือไม่ เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้ทำงานในเวลา
