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

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

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

ยกตัวอย่างเช่น ถ้าค่า $b_{i}\,$ และ $t_{i}\,$ เป็นไปตามที่กำหนดในโจทย์ และเราตัดสินใจส่งวิดิโอที่ 1, 2, และ 3 ตามลำดับแล้ว เราจะได้ว่า $B_{1}=2000\,$, $B_{2}=5000\,$, $B_{3}=8000\,$, และ $B_{4}=10000\,$

ให้ $T=\sum _{i=1}^{n}t_{i}\,$ เราได้ว่าเราสามารถส่งวิดีโอต่างๆ ผ่าน network link โดยสอดคล้องกับกฎ (*) ถ้าหาก $B_{t}\leq rt\,$ สำหรับ $t\,$ ทุกๆ ค่าที่ $1\leq t\leq T\,$ หรือกล่าวอีกอย่างหนึ่งคือ $B_{t}/t\leq r\,$ สำหรับ $t\,$ ทุกค่า

ดังนั้นเราสามารถแก้ปัญหาในโจทย์ได้อีกแบบหนึ่งดังต่อไปนี้: เราหาลำดับการส่งวิดีโอที่ทำให้ค่า $B_{t}/t\,$ ที่มากที่สุด (กล่าวคือ $\max _{1\leq t\leq T}B_{t}/t\,$) มีค่าน้อยที่สุดเท่าที่เป็นไปได้ ถ้าค่านี้มีค่ามากกว่า $r\,$ แสดงว่าเราไม่สามารถส่งวิดีโอตามกฎ (*) ได้เลย

ลำดับการส่งที่ทำให้ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ มีค่าน้อยที่สุด

เราจะพิสูจน์ว่าลำดับการส่งที่ทำการส่งวิดีโอที่มีค่า $b_{i}/t_{i}\,$ น้อยกว่าก่อน (กล่าวคือนำวิดีโอมาเรียงตามค่า $b_{i}/t_{i}\,$ จากน้อยไปหามากแล้วส่งตามลำดับนั้น) จะทำให้ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้

เราจะทำการพิสูจน์นี้ด้วย exchange argument ซึ่งเราจะแสดงว่าเราสามารถแปลงวิธีการส่งที่ทำให้ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ (ตั้งแต่บัดนี้เราจะเรียกมันว่า "วิธีการส่งที่ดีที่สุด") ไปเป็นการส่งที่ส่งตามลำดับค่า $b_{i}/t_{i}\,$ จากน้อยไปมาก โดยไม่ทำให้ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ มีค่ามากขึ้น

สมมติว่าวิธีการส่งที่ดีที่สุดไม่เหมือนกับวิธีการส่งตามลำดับ $b_{i}/t_{i}\,$ แสดงว่าจะต้องมีวิดีโอ $i\,$ และ $j\,$ ที่ $i\,$ ถูกส่งก่อน $j\,$ แต่ $b_{i}/t_{i}>b_{j}/t_{j}\,$ นอกจากนี้เรายังสามารถสมมติเพิ่มเติมได้อีกว่าวิดีโอ $j\,$ เป็นวิดีโอที่ถูกส่งถัดจากวิดีโอ $i\,$ ด้วย เนื่องจากเรารู้ว่าถ้ามี inversion แล้วจะต้องมี inversion ที่ติดกันเสมอ

เราจะแสดงว่าเมื่อเราสลับเอาวิดีโอ $j\,$ ไปส่งก่อนวิดีโอ $i\,$ แล้ว ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ จะไม่เพิ่มขึ้นแต่อย่างใด

สมมติว่าเราเริ่มส่งวิดีโอ $i\,$ ณ เวลา $s\,$ เราจะได้ว่าเราจะส่งมันเสร็จที่เวลา $s+t_{i}\,$ ซึ่งเราจะเริ่มส่งวิดีโอ $j\,$ และเราจะส่งวิดีโอ $j\,$ ที่เวลา $s+t_{i}+t_{j}\,$ ดังนั้นในช่วงเวลาตั้งแต่ $t=s\,$ ถึง $t=s+t_{i}\,$ ค่า $B_{t}\,$ จะมีค่าเพิ่มขึ้นวินาทีละ $b_{i}/t_{i}\,$ และในช่วงเวลาตั้งแต่ $t=s+t_{i}\,$ จนถึง $t=s+t_{i}+t_{j}\,$ ค่า $B_{t}\,$ จะมีค่าเพิ่มขึ้นวินาทีละ $b_{j}/t_{j}\,$ ซึ่งเราสามารถเขียนสรุปเป็นสัญลักษณ์ได้ดังต่อไปนี้

$B_{t}={\begin{cases}B_{s}+(t-s){\frac {b_{i}}{t_{i}}},&s\leq t=<s+t_{i}\\B_{s}+b_{i}+(t-s-t_{i}){\frac {b_{j}}{t_{j}}}&s+t_{i}\leq t\leq s+t_{i}+t_{j}\end{cases}}\,$

หลังจากสลับแล้วเราจะเริ่มส่งวิดีโอ $j\,$ ณ เวลา $t=s\,$ และจะส่งเสร็จที่เวลา $t=s+t_{j}\,$ ซึ่งในเวลาเดียวกันเราจะเริ่มส่งวิดีโอ $i\,$ และจะส่งมันเสร็จที่เวลา $t=s+t_{j}+t_{i}=s+t_{i}+t_{j}\,$ ให้ $B'_{t}\,$ แทนจำนวนบิตที่ส่งผ่าน network link ตั้งแต่เวลา 0 ถึง $t\,$ หลังจากการสลับ เราจะได้ว่าตั้งแต่เวลา $t=s\,$ ถึง $t=t_{j}\,$ ค่า $B'_{t}\,$ จะมีค่าเพิ่มขึ้นวินาทีละ $b_{j}/t_{j}\,$ ส่วนในเวลาตั้งแต่ $t=s+t_{j}\,$ ถึง $t=s+t_{i}+t_{j}\,$ ค่า $B'_{t}\,$ จะเพิ่มขึ้นวินาทีละ $b_{i}/t_{i}\,$ ซึ่งเราสามารถเขียนสรุปเป็นสัญลักษณ์ได้ดังต่อไปนี้

$B'_{t}={\begin{cases}B_{s}+(t-s){\frac {b_{j}}{t_{j}}},&s\leq t<s+t_{j}\\B_{s}+b_{j}+(t-s-t_{j}){\frac {b_{i}}{t_{i}}}&s+t_{j}\leq t\leq s+t_{i}+t_{j}\end{cases}}\,$

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

lemma 1: สำหรับจำนวนเต็ม $t\,$ ทุกตัวที่ $s\leq t\leq s+t_{i}+t_{j}\,$ เราได้ว่า $B_{t}\geq B'_{t}\,$

โดยที่หาก lemma นี้เป็นจริง เราจะได้ว่า $\max _{s\leq t\leq s+t_{i}+t_{j}}B_{t}/t\geq \max _{s\leq t\leq s+t_{i}+t_{j}}B'_{t}/t\,$ เนื่องจาก สมมติให้ $\max _{s\leq t\leq s+t_{i}+t_{j}}B'_{t}/t=B'_{u}/u\,$ โดยที่ $u\,$ เป็นจำนวนเต็มตัวหนึ่งที่อยู่ในช่วง $[s,s+t_{i}+t_{j}]\,$ แล้ว เราจะได้ว่า $B'_{u}/u\leq B_{u}/u\leq \max _{s\leq t\leq s+t_{i}+t_{j}}B_{t}/t\,$ ฉะนั้นเราจึงสามารถสรุปได้ว่าหลังจากสลับแล้ว $\max _{1\leq t\leq T}B_{t}/t\,$ จะมีค่าไม่เพิ่มขึ้น และการส่งวิดีโอตามลำดับ $b_{i}/t_{i}\,$ จากมากไปน้อยทำให้ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ ต่ำที่สุดเท่าที่จะเป็นไปได้

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

พิสูจน์: สำหรับจำนวนเต็ม $t\,$ ที่ $s\leq t\leq s+t_{i}+t_{j}\,$นิยามค่า $B''_{t}=B_{s}+(t-s){\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}\,$

เราจะแสดงว่า สำหรับ $t\,$ ทุกค่าที่ $s\leq t\leq s+t_{i}+t_{j}\,$

1. $B_{t}\geq B''_{t}\,$
2. $B''_{t}\geq B'_{t}\,$

หากสามารถทำเช่นนี้ได้ เราก็จะสามารถสรุปได้ว่า $B_{t}\geq B'_{t}\,$ สำหรับ $t\,$ ทุกค่า

การพิสูจน์ข้อวามทั้งสองข้อข้างบนนี้จะใช้ความจริงที่ว่า ${\frac {b_{i}}{t_{i}}}>{\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}>{\frac {b_{j}}{t_{j}}}\,$ หลายครั้ง เราจะพิสูจน์ข้อความนี้เป็น lemma 2 หลังจากพิสูจน์ lemma 1

(ข้อความที่ 1) เราจะได้ว่า ถ้า $s\leq t<s+t_{i}\,$ แล้ว

$B_{t}=B_{s}+(t-s){\frac {b_{i}}{t_{i}}}>B_{s}+(t-s){\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}=B''_{t}\,$

ถ้า $s+t_{i}\leq t\leq s+t_{i}+t_{j}\,$ แล้ว

$B_{t}-B''_{t}\,$	$=\,$	$b_{i}+(t-s-t_{i}){\frac {b_{j}}{t_{j}}}-(t-s){\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}=t_{i}{\frac {b_{i}}{t_{i}}}+(t-t_{i}){\frac {b_{j}}{t_{j}}}-(t-s){\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}\,$
$\,$	$=\,$	$b_{i}-t_{i}{\frac {b_{j}}{t_{j}}}-(t-s){\bigg (}{\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}-{\frac {b_{j}}{t_{j}}}{\bigg )}\,$
$\,$	$\geq \,$	$b_{i}-t_{i}{\frac {b_{j}}{t_{j}}}-(t_{i}+t_{j}){\bigg (}{\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}-{\frac {b_{j}}{t_{j}}}{\bigg )}\,$
$\,$	$=\,$	$b_{i}-t_{i}{\frac {b_{j}}{t_{j}}}-b_{i}-b_{j}+t_{i}{\frac {b_{j}}{t_{j}}}+b_{j}\,$
$\,$	$=\,$	$0\,$

ดังนั้น $B_{t}\geq B''_{t}\,$ ในกรณีนี้เช่นกัน

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

lemma 2: ถ้า $a,b,c,d\,$ เป็นจำนวนที่มีค่าไม่เป็นลบโดยที่ ${\frac {a}{b}}>{\frac {c}{d}}\,$ แล้ว ${\frac {a}{b}}>{\frac {a+c}{b+d}}>{\frac {c}{d}}\,$

พิสูจน์: เนื่องจาก ${\frac {a}{c}}>{\frac {b}{d}}\,$ เราจะได้ว่า $ad>bc\,$ ฉะนั้น $ab+ad>ab+bc\,$ ซึ่งหมายความว่า $a(b+d)>b(a+c)\,$ ฉะนั้น ${\frac {a}{b}}>{\frac {a+c}{b+d}}\,$

การพิสูจน์ว่า ${\frac {a+c}{b+d}}>{\frac {c}{d}}\,$ ก็สามารถทำได้โดยการใช้เหตุผลแบบเดียวกันกับย่อหน้าที่แล้ว เราจึงละให้นิสิตทำเป็นแบบฝึกหัดไว้อีกโอกาสหนึ่ง (จบการพิสูจน์ lemma 2)

การหาค่า $\max _{1\leq t\leq T}B_{t}/t\,$

เราทราบว่าการส่งวิดีโอโดยเรียงลำดับตาม $b_{i}/t_{i}\,$ จะทำให้่ีค่า $\max _{1\leq t\leq T}B_{t}/t\,$ มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ แต่ด้วยความรู้เพียงแค่นี้เราไม่สามารถตัดสินได้ว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่ เนื่องจากเราไม่ร้ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ เราจึงจำเป็นต้องออกแบบอัลกอริทึมเพื่อหาค่าดังกล่าว

อย่างไรก็ดีค่า เราสามารถหาค่า $\max _{1\leq t\leq T}B_{t}/t\,$ เมื่อเราเรียงวิดีโอตาม $b_{i}/t_{i}\,$ ได้ง่ายมาก เราจะพิสูจน์ว่าค่านั้นคือ $B_{T}/T\,$ ซึ่งมีค่าเท่ากับจำนวนบิตที่ส่งทั้งหมดหารด้วยเวลาส่งทั้งหมด

lemma 3: ถ้าเราเรียงวิดีโอให้ ${\frac {b_{1}}{t_{1}}}\leq {\frac {b_{2}}{t_{2}}}\leq \dotsb \leq {\frac {b_{n}}{t_{n}}}\,$ แล้ว สำหรับค่า $t\,$ ทุกค่าที่ $1\leq t\leq T\,$ เราจะได้ว่า ${\frac {B_{1}}{1}}\leq {\frac {B_{2}}{2}}\leq {\frac {B_{3}}{3}}\leq \dotsb \leq {\frac {B_{t}}{t}}\,$ นอกจากนี้ ถ้าในช่วงเวลาตั้งแต่ $t-1\,$ ถึงเวลา $t\,$ เราทำการส่งวิีดีโด $i\,$ แล้วเราจะได้ว่า ${\frac {B_{t}}{t}}\leq {\frac {b_{i}}{t_{i}}}\,$

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

(Base Case) ในกรณีนี้ $t=1\,$ เราได้ว่าในวินาทีแรกเราจะส่งข้อมูล $b_{1}/t_{1}\,$ บิตในเวลา 1 วินาที ดังนั้น ${\frac {B_{1}}{1}}\leq {\frac {b_{1}}{t_{1}}}\,$ ตามต้องการ

(Induction Case) สมมติให้ lemma เป็นจริงสำหรับ $t\geq 1\,$ บางค่า พิจารณาเหตุการณ์ที่เกิดขึ้น ณ ช่วงเลาตั้งแต่ $t\,$ ถึง $t+1\,$ และสมมติว่าในช่วงเวลานี้เราทำการส่งวิดีโอ $i\,$ ผ่าน network link กล่าวคือในวินาทีนั้นเราส่งข้อมูลจำนวน ${\frac {b_{i}}{t_{i}}}\,$ บิต ในกรณีนี้มีความเป็นไปได้อยู่สองกรณี

กรณีแรกคือ เราเริ่มส่งวิดีโอ $i\,$ ตั้งแต่ก่อนเวลา $t\,$ อยู่แล้ว ในกรณีนี้สมมติฐานของ induction บอกเราว่า ${\frac {B_{t}}{t}}\leq {\frac {b_{i}}{t_{i}}}={\frac {b_{i}/t_{i}}{1}}\,$ ฉะนั้นจาำก lemma 2 เราได้ว่า ${\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}}}\,$ เนื่องจาก ${\frac {B_{t+1}}{t+1}}={\frac {B_{t}+b_{i}/t_{i}}{t+1}}\,$ เราจึงได้ว่า ${\frac {B_{t}}{t}}\leq {\frac {B_{t+1}}{t+1}}\,$ ด้วย

กรณีที่สองคือ เราเริ่มส่งวิดีโอ $i\,$ ณ เวลา $t\,$ พอดี กล่าวคือในช่วงเวลาตั้งแต่ $t-1\,$ ถึง $t\,$ เราำกำลังส่งวิดีโอ $i-1\,$ อยู่ ในกรณีนี้สมมติฐานของ indunction บอกเราว่า ${\frac {B_{t}}{t}}\leq {\frac {b_{i-1}}{t_{i-1}}}\leq {\frac {b_{i}}{t_{i}}}\,$ และเราสามารถใช้เหตุผลในกรณีที่แล้วพิสูจน์ว่า lemma เป็นจริงสำหรับ $t+1\,$ ด้วยเช่นกัน

จาก lemma 3 เราได้ว่า $\max _{1\leq t\leq T}B_{t}/t=B_{T}/T\,$

ฉะนั้นการหาว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่สามารถทำได้โดยการหาผลรวม $B_{T}=\sum _{i=1}^{n}b_{i}\,$ และ $T=\sum _{i=1}^{n}t_{i}\,$ แล้วตรวจสอบว่า $B_{T}/T\,$ มากกว่า $r\,$ หรือไม่ เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้ทำงานในเวลา $O(n)\,$