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

อัลกอริทึม

เรียงเวลาการเข้างานของคนงานตามเวลาเลิกจากน้อยไปหามาก เมื่อพิจารณาเวลาการทำงานของคนงานที่มีเวลาเลิกงานช้าที่สุด แล้วเลือกคนที่มีเวลาทำงาน 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 ใช้จำนวนผู้ตรวจงานน้อยที่สุดเท่าที่จะเป็นไปได้