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

รุ่นแก้ไขปัจจุบันเมื่อ 13:09, 21 กันยายน 2552

อัลกอริทึม

เรียงเวลาการเข้างานของคนงานตามเวลาเลิกจากน้อยไปหามาก เมื่อพิจารณาเวลาการทำงานของคนงานที่มีเวลาเลิกงานช้าที่สุด แล้วเลือกคนที่มีเวลาทำงาน overlap กับคนงานนี้ที่มีเวลาเลิกงานช้าที่สุดเป็นผู้ตรวจงาน จากนั้นลบคนงานทุก ๆ คนที่มีเวลาทำงาน overlap กับผู้ตรวจงานคนนี้ออกจากเซตของคนงานที่กำลังพิจารณา ทำแบบนี้ไปเรื่อย ๆ จนเซตของคนงานที่กำลังพิจารณาเป็นเซตว่าง

<geshi lang="c"> Supervisor() {

   G = empty set // ให้ G เป็นเซตของผู้ตรวจงาน
       S = {1,2,...,n} // เซตของคนงานที่กำลังพิจารณา ที่เรียงตามเวลาเลิกงานจากน้อยไปมาก นั่นคือ f1 <= f2 <= ... <= fn นั่นเอง
       while S not empty do
   {
    i = {j in S| min f(j)} // i เป็นคนงานในเซตของคนงานที่กำลังพิจารณาที่มีเวลาเลิกงานช้าที่สุดตอนนี้
         Oi={k in S| s(k) <= f(i) or s(i) < = f(k)} // Oi เป็นเซตของคนงานทุกคนในเซตของคนงานที่กำลังพิจารณาที่มีเวลาทำงาน overlap กับคนที่ i
    l = {m in S| min f(m)} // ให้ l เป็นคนงานที่มีเวลาทำงาน overlap กับ คนงานคนที่ i ที่เลิกงานช้าที่สุด
         G = G union l // เพิ่มคนงาน l เข้าไปในเซตของผู้ตรวจงาน
         Ol = {k in S| s(k) <= f(l) or s(l) <= f(k)} // Ol เป็นเซตของคนงานทุกคนในเซตของคนงานที่กำลังพิจารณาที่มีเวลาทำงาน overlap กับผู้ตรวจงาน l
    S= S - Ol
   }
    return G

} </geshi>

การพิสูจน์ความถูกต้องของอัลกอริทึม

จะใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ $G=\{i_{1},i_{2},...,i_{k}\}\,$ เป็นเซตของผู้ตรวจงานที่ได้จาก greedy algorithm ข้างต้น และ $OPT=\{j_{1},j_{2},...,j_{m}\}\,$ เป็นเซตของผู้ตรวจงานที่ได้จาก optimal algorithm (อัลกอริทึมสำหรับการแก้ปัญหาข้างต้นที่ให้เซตของผู้ตรวจงานที่มีจำนวนน้อยที่สุด) เราจะทำการพิสูจน์โดยบอกว่า $k=m\,$ สังเกตว่า เนื่องจาก $OPT\,$ เป็นคำตอบที่ดีที่สุด ดังนั้น $m\leq k\,$ เสมอ

สมมติให้เวลาการเข้างานของ $OPT\,$ ถูกเรียงตามเวลาเลิกงานจากน้อยไปมากด้วย

lemma:สำหรับ $r\leq m\,$ ใด ๆ แล้ว $f(i_{r})\geq f(j_{r})\,$ เสมอ

พิสูจน์:ทำการพิสูจน์โดย induction บน r กรณี base case $r=1\,$ เนื่องจาก greedy algorithm เลือกคนงานที่มีเวลาเลิกงานช้าที่สุดที่ overlap กับคนงานที่มีเวลาเลิกงานน้อยที่สุดที่กำลังพิจารณาในเซต $S\,$ เป็นผู้ตรวจงาน ดังนั้น $f(i_{1})\geq f(j_{1})\,$ จริง

พิจารณากรณีที่ $r>1\,$ สมมติให้ข้อความที่ต้องการพิสูจน์เป็นจริงสำหรับค่า $r-1\,$ นั่นคือ $f(i_{r-1})\geq f(j_{r-1})\,$ ต้องการพิสูจน์ว่า $f(i_{r})\geq f(j_{r})\,$ ด้วย

พิสูจน์โดยข้อขัดแย้ง สมมติให้ $f(i_{r})<f(j_{r})\,$ พิจารณาการที่ greedy algorithm เลือกผู้ตรวจงานถึงคนที่ $i_{r-1}\,$ แสดงว่าต้องมีคนงานคนหนึ่งให้เป็นคนที่ $k\,$ ที่มีเวลาเริ่มงานทีหลังผู้ตรวจงานคนที่ $i_{r-1}\,$ นี้ นั่นคือ $s_{k}>f(i_{r-1})\,$ เราจะได้ว่าเวลาการทำงานของคนงานคนที่ $k\,$ นี้จะต้อง overlap กับผู้ตรวจงานคนที่ $j_{r}\,$ ของ $OPT\,$ ด้วย เพราะไม่เช่นนั้นคนที่ $k\,$ นี้ก็จะไม่มีผู้ตรวจงานคนไหน ตรวจงานเค้าได้ (ไม่เป็นไปตามเงื่อนไขของบริษัท) แต่เนื่องจาก greedy algorithm เลือกผู้ตรวจงานเป็นคนงานคนที่มีเวลาเลิกงานช้าที่สุด และในที่นี้ greedy algorithm เลือกคนที่ $i_{r}\,$ จึงเกิดข้อขัดแย้งที่ว่า $f(i_{r})<f(j_{r})\,$ ดังนั้นเราสามารถสรุปได้ว่า $f(i_{r})\geq f(j_{r})\,$ สำหรับ $r\leq m\,$ ใด ๆ

ทฤษฎีบท: Greedy algorithm ใช้จำนวนผู้ตรวจงานน้อยที่สุดเท่าที่จะเป็นไปได้ กล่าวคือ $k=m\,$

พิสูจน์: สมมติเพื่อให้เกิดข้อขัดแย้งว่า $m<k\,$

พิจารณาเมื่อ $OPT\,$ เพิ่มคนงานคนที่ $j_{m}\,$ เข้าไปเป็นผู้ตรวจงาน เนื่องจากผู้ตรวจงาน $j_{1},j_{2},...,j_{m}\,$ ตรวจงานคนงานได้ครบทุกคนตามเงื่อนไขของบริษัทแล้ว แสดงว่าไม่มีคนงานคนไหนที่มีเวลาทำงานไม่ overlap กับผู้ตรวจงาน $m\,$ คนในวิธีการของ $OPT\,$ และจาก lemma เราได้ว่า $f(i_{r})\geq f(j_{r})\,$ จึงได้ว่าไม่มีคนงานคนไหนที่ที่มีเวลาทำงานไม่ overlap กับผู้ตรวจงานคนที่ $i_{m}\,$ ด้วย แต่การที่ greedy algorithm ยังเพิ่มผู้ตรวจงานคนที่ $i_{m+1}\,$ เข้าไปอีก แสดงว่า greedy algorithm ยังทำงานไม่จบ ทั้ง ๆ ที่ควรจบได้แล้ว เพราะคนงานทุกคนมีผู้ตรวจงานที่มีเวลา overlap กับตนเองแล้ว จึงเกิดข้อขัดแย้ง

ดังนั้น $k=m\,$ และ greedy algorithm ใช้จำนวนผู้ตรวจงานน้อยที่สุดเท่าที่จะเป็นไปได้

@@ แถว 21: / แถว 21: @@
 ==''การพิสูจน์ความถูกต้องของอัลกอริทึม''==
-จะใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> G=\{i_1,i_2,...,i_k \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก greedy algorithm ข้างต้น และ <math> OPT=\{j_1,j_2,...,j_m \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก optimal algorithm (อัลกอริทึมสำหรับการแก้ปัญหาข้างต้นที่ให้เซตของผู้ตรวจงานที่มีขนาดน้อยที่สุด) เราจะทำการพิสูจน์โดยบอกว่า <math> k = m \,</math> สังเกตว่า เนื่องจาก <math> OPT \, </math> เป็นคำตอบที่ดีที่สุด ดังนั้น <math> k \leq m \,</math> เสมอ
+จะใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> G=\{i_1,i_2,...,i_k \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก greedy algorithm ข้างต้น และ <math> OPT=\{j_1,j_2,...,j_m \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก optimal algorithm (อัลกอริทึมสำหรับการแก้ปัญหาข้างต้นที่ให้เซตของผู้ตรวจงานที่มีจำนวนน้อยที่สุด) เราจะทำการพิสูจน์โดยบอกว่า <math> k = m \,</math> สังเกตว่า เนื่องจาก <math> OPT \, </math> เป็นคำตอบที่ดีที่สุด ดังนั้น <math> m \leq k \,</math> เสมอ
- สมมติให้เวลาการเข้างานของ <math> OPT \, </math> ถูกเรียงตามเวลาเลิกงานจากน้อยไปมากด้วย
+สมมติให้เวลาการเข้างานของ <math> OPT \, </math> ถูกเรียงตามเวลาเลิกงานจากน้อยไปมากด้วย
-'''lemma:'''สำหรับ <math> r \leq k \,</math> ใด ๆ แล้ว <math> f(i_r) \geq f(j_r) \,</math> เสมอ
+'''lemma:'''สำหรับ <math> r \leq m \,</math> ใด ๆ แล้ว <math> f(i_r) \geq f(j_r) \,</math> เสมอ
 '''พิสูจน์:'''ทำการพิสูจน์โดย induction บน r กรณี base case <math> r=1 \, </math> เนื่องจาก greedy algorithm เลือกคนงานที่มีเวลาเลิกงานช้าที่สุดที่ overlap กับคนงานที่มีเวลาเลิกงานน้อยที่สุดที่กำลังพิจารณาในเซต <math> S \, </math> เป็นผู้ตรวจงาน ดังนั้น <math> f(i_1) \geq f(j_1) \, </math> จริง
-พิจารณากรณีที่ <math> r > 1 \, </math> สมมติให้ข้อความที่ต้องการพิสูจน์เป็นจริงสำหรับค่า <math> r-1 \, </math> นั่นคือ <math> f(i_{r-1}) \geq f(j_{r-1}) \, </math> ต้องการพิสูจน์ว่า สำหรับค่า <math> f(i_r) \geq f(j_r) \, </math> ด้วย
+พิจารณากรณีที่ <math> r > 1 \, </math> สมมติให้ข้อความที่ต้องการพิสูจน์เป็นจริงสำหรับค่า <math> r-1 \, </math> นั่นคือ <math> f(i_{r-1}) \geq f(j_{r-1}) \, </math> ต้องการพิสูจน์ว่า  <math> f(i_r) \geq f(j_r) \, </math> ด้วย
-พิสูจน์โดยข้อขัดแย้ง สมมติให้ <math> f(i_r) < f(j_r) \,</math> พิจารณาการที่ greedy algorithm เลือกผู้ตรวจงานถึงคนที่ <math> i_{r-1} \, </math> แสดงว่าต้องมีคนงานคนหนึ่งให้เป็นคนที่ <math> k \, </math> ที่มีเวลาเริ่มงานทีหลังผู้ตรวจงานคนที่ <math> i_{r-1} \, </math> นี้ นั่นคือ <math> s_k > f(i_{r-1}) \,</math> เราจะได้ว่าเวลาการทำงานของคนงานคนที่ <math> k \,</math> นี้จะต้อง overlap กับผู้ตรวจงานคนที่ <math> j_r \, </math> ของ <math> OPT \, </math> ด้วย เพราะไม่เช่นนั้นคนที่ <math> k \, </math> นี้ก็จะไม่มีผู้ตรวจงานคนไหน ตรวจงานเค้าได้ (ไม่เป็นไปตามเงื่อนไขของบริษัท) แต่เนื่องจาก greedy algorithm เลือกผู้ตรวจงานเป็นคนงานคนที่มีเวลาเลิกงานช้าที่สุด และในที่นี้ greedy algorithm เลือกคนที่ <math> i_r \,</math> จึงเกิดข้อขัดแย้งที่ว่า <math> f(i_r) < f(j_r) \,</math> ดังนั้นเราสามารถสรุปได้ว่า <math> f(i_r) \geq f(j_r) \,</math> สำหรับ <math> r \leq k \,</math> ใด ๆ
+พิสูจน์โดยข้อขัดแย้ง สมมติให้ <math> f(i_r) < f(j_r) \,</math> พิจารณาการที่ greedy algorithm เลือกผู้ตรวจงานถึงคนที่ <math> i_{r-1} \, </math> แสดงว่าต้องมีคนงานคนหนึ่งให้เป็นคนที่ <math> k \, </math> ที่มีเวลาเริ่มงานทีหลังผู้ตรวจงานคนที่ <math> i_{r-1} \, </math> นี้ นั่นคือ <math> s_k > f(i_{r-1}) \,</math> เราจะได้ว่าเวลาการทำงานของคนงานคนที่ <math> k \,</math> นี้จะต้อง overlap กับผู้ตรวจงานคนที่ <math> j_r \, </math> ของ <math> OPT \, </math> ด้วย เพราะไม่เช่นนั้นคนที่ <math> k \, </math> นี้ก็จะไม่มีผู้ตรวจงานคนไหน ตรวจงานเค้าได้ (ไม่เป็นไปตามเงื่อนไขของบริษัท) แต่เนื่องจาก greedy algorithm เลือกผู้ตรวจงานเป็นคนงานคนที่มีเวลาเลิกงานช้าที่สุด และในที่นี้ greedy algorithm เลือกคนที่ <math> i_r \,</math> จึงเกิดข้อขัดแย้งที่ว่า <math> f(i_r) < f(j_r) \,</math> ดังนั้นเราสามารถสรุปได้ว่า <math> f(i_r) \geq f(j_r) \,</math> สำหรับ <math> r \leq m \,</math> ใด ๆ
 '''ทฤษฎีบท:''' Greedy algorithm ใช้จำนวนผู้ตรวจงานน้อยที่สุดเท่าที่จะเป็นไปได้ กล่าวคือ <math>  k = m \,</math>
@@ แถว 37: / แถว 37: @@
 '''พิสูจน์:''' สมมติเพื่อให้เกิดข้อขัดแย้งว่า <math> m < k \,</math>
-พิจารณาเมื่อ <math> OPT \, </math> เพิ่มคนงานคนที่ <math> j_m \, </math> เข้าไปเป็นผู้ตรวจงาน เนื่องจากผู้ตรวจงาน <math> j_1,j_2,...,j_m \, </math> ตรวจงานคนงานได้ครบทุกคนตามเงื่อนไขของบริษัทแล้ว แสดงว่าไม่มีคนงานคนไหนที่มีเวลาทำงานไม่ overlap กับผู้ตรวจงาน <math> m \, </math> ในวิธีการของ <math> OPT \,</math> และจาก lemma เราได้ว่า <math> f(i_r) \geq f(j_r) \,</math> จึงได้ว่าไม่มีคนงานคนไหนที่ที่มีเวลาทำงานไม่ overlap กับผู้ตรวจงานคนที่ <math> i_m \,</math> ด้วย แต่การที่ greedy algorithm ยังเพิ่มผู้ตรวจงานคนที่ <math> i_{m+1} \,</math> เข้าไปอีก แสดงว่า greedy algorithm ยังทำงานไม่จบ ทั้ง ๆ ที่ควรจบได้แล้ว เพราะคนงานทุกคนมีผู้ตรวจงานที่มีเวลา overlap กับตนเองแล้ว จึงเกิดข้อขัดแย้ง
+พิจารณาเมื่อ <math> OPT \, </math> เพิ่มคนงานคนที่ <math> j_m \, </math> เข้าไปเป็นผู้ตรวจงาน เนื่องจากผู้ตรวจงาน <math> j_1,j_2,...,j_m \, </math> ตรวจงานคนงานได้ครบทุกคนตามเงื่อนไขของบริษัทแล้ว แสดงว่าไม่มีคนงานคนไหนที่มีเวลาทำงานไม่ overlap กับผู้ตรวจงาน <math> m \, </math> คนในวิธีการของ <math> OPT \,</math> และจาก lemma เราได้ว่า <math> f(i_r) \geq f(j_r) \,</math> จึงได้ว่าไม่มีคนงานคนไหนที่ที่มีเวลาทำงานไม่ overlap กับผู้ตรวจงานคนที่ <math> i_m \,</math> ด้วย แต่การที่ greedy algorithm ยังเพิ่มผู้ตรวจงานคนที่ <math> i_{m+1} \,</math> เข้าไปอีก แสดงว่า greedy algorithm ยังทำงานไม่จบ ทั้ง ๆ ที่ควรจบได้แล้ว เพราะคนงานทุกคนมีผู้ตรวจงานที่มีเวลา overlap กับตนเองแล้ว จึงเกิดข้อขัดแย้ง
-พิจารณาเวลาที่ greedy algorithm เพิ่งจะปักเสาต้นที่ <math>k \,</math> ไป เราพบว่าบ้านทุกบ้านจะต้องถูกครอบคลุมด้วยเสา <math>\ell \,</math> ต้นที่ปักไปแล้วตามการให้เหตุผลข้างต้น แต่การที่ <math>k > \ell \,</math> แสดงว่า greedy algorithm ยังทำงานต่อไปทั้งทที่มันควรจะหยุดการทำงานตั้งแต่ตอนที่ปักเสาต้นที่ <math>\ell \,</math> ไปแล้ว เกิดข้อขัดแย้ง
 ดังนั้น <math> k = m \,</math> และ greedy algorithm ใช้จำนวนผู้ตรวจงานน้อยที่สุดเท่าที่จะเป็นไปได้

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

รุ่นแก้ไขปัจจุบันเมื่อ 13:09, 21 กันยายน 2552

อัลกอริทึม

การพิสูจน์ความถูกต้องของอัลกอริทึม

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ