ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 7"
ไปยังการนำทาง
ไปยังการค้นหา
Aoy (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''== เรียงเวลาการเข้างานของคนงานตามเวล…') |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
==''อัลกอริทึม''== | ==''อัลกอริทึม''== | ||
| − | เรียงเวลาการเข้างานของคนงานตามเวลาเลิกจากน้อยไปหามาก | + | เรียงเวลาการเข้างานของคนงานตามเวลาเลิกจากน้อยไปหามาก เมื่อพิจารณาเวลาการทำงานของคนงานที่มีเวลาเลิกงานช้าที่สุด แล้วเลือกคนที่มีเวลาทำงาน overlap กับคนงานนี้ที่มีเวลาเลิกงานช้าที่สุดเป็นผู้ตรวจงาน จากนั้นลบคนงานทุก ๆ คนที่มีเวลาทำงาน overlap กับผู้ตรวจงานคนนี้ออกจากเซตของคนงานที่กำลังพิจารณา ทำแบบนี้ไปเรื่อย ๆ จนเซตของคนงานที่กำลังพิจารณาเป็นเซตว่าง |
<geshi lang="c"> | <geshi lang="c"> | ||
| แถว 6: | แถว 6: | ||
{ | { | ||
G = empty set // ให้ G เป็นเซตของผู้ตรวจงาน | G = empty set // ให้ G เป็นเซตของผู้ตรวจงาน | ||
| − | + | S = {1,2,...,n} // เซตของคนงานที่กำลังพิจารณา ที่เรียงตามเวลาเลิกงานจากน้อยไปมาก นั่นคือ f1 <= f2 <= ... <= fn นั่นเอง | |
while S not empty do | while S not empty do | ||
{ | { | ||
| − | i = {j in S| | + | 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> | </geshi> | ||
รุ่นแก้ไขเมื่อ 08:12, 19 กันยายน 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>
