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\,$ ถูกเรียงตามเวลาเลิกงานจากน้อยไปมากด้วย

lemma:สำหรับ $r\leq k\,$ ใด ๆ แล้ว $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})\,$