ขั้นตอนวิธีฮังกาเรียน

จากวิกิพีเดีย สารานุกรมเสรี

ขั้นตอนวิธีชาวฮังกาเรียน ( อังกฤษ: Hungarian Algorithm ) คือ ขั้นตอนวิธีการหาค่าเหมาะสมที่สุดเชิงการจัด ซึ่งใช้ในการแก้ ปัญหาการกำหนดงาน ถูกคิดค้นและตั้งชื่อโดย แฮโรลด์ วิลเลียม คุห์น ในปี ค.ศ. 1955 ที่ตั้งชื่อนี้เพราะว่าขั้นตอนวิธีนี้มีพื้นฐานส่วนใหญ่จากการคิดของนักคณิตศาสตร์ชาวฮังกาเรียน 2 คน คือ Dénes Kőnig และ Jenő Egerváry ต่อมาเจมส์ มุนเครสได้นำขั้นตอนวิธีนี้มาตรวจสอบในปี ค.ศ. 1957 และได้พบว่ามีประสิทธิภาพเชิงเวลาเป็นแบบ strongly polynomial ตั้งแต่นั้นมาขั้นตอนวิธีนี้จึงเป็นที่รู้จักในชือว่า ขั้นตอนวิธีคุห์น-มุนเครส หรือ ขั้นตอนวิธีการกำหนดงานมุนเครส โดยมีประสิทธิภาพเชิงเวลาของขั้นตอนวิธีดั้งเดิมเป็น O(n^4) แต่อย่างไรก็ตามขั้นตอนวิธีนี้ แจ็ค เอดมันด์ และ ริชาร์ด แมนนิ่งคาร์ป ได้สามารถปรับปรุงให้มีประสิทธิภาพเชิงเวลาเป็น O(n^3) ได้ และในปี ค.ศ. 2006 มีการค้นพบว่า คาร์ล กุสตาฟ จาโคบี (Carl Gustav Jacobi) สามารถแก้ปัญหาการกำหนดงานได้ในคริสต์ศตวรรษที่ 19 และได้เผยแพร่ในปี ค.ศ. 1890 ในภาษาละติน

ปัญหาการกำหนดงาน[แก้]

ขั้นตอนวิธีฮังกาเรียนนี้ใช้แก้ปัญหาการกำหนดงาน ซึ่งเป็นปัญหาชนิดพิเศษของปัญหากำหนดการเชิงเส้นอีกลักษณะหนึ่ง มีรูปแบบคล้ายคลึงกับปัญหาการขนส่ง โดยปัญหาการกำหนดงานจะมีลักษณะดังนี้

  • จำนวนงานและจำนวนคนงานเท่ากัน ในกรณีที่ไม่เท่าจะต้องเพิ่มงานหรือคนงานสมมติแล้วแต่ว่าส่วนใดขาดหายไปและให้ต้นทุนการกำหนดงานมากที่สุด
  • คนงานจะทำงานได้เพียง 1 งาน
  • งานแต่ละงานจะมีคนรับผิดชอบเพียงคนเดียว
  • มีต้นทุนการกำหนดงาน j ให้ i ทำเป็น C_{ij} ซึ่งมีเป้าหมายของการกำหนดงานคือการทำให้เกิดต้นทุนน้อยที่สุด หรือเราสามารถดัดแปลงให้หาค่าต้นทุนมากที่สุดได้

ยกตัวอย่างเช่น สมมติให้มีคนงาน 3 คน คือ สมชาย สมหญิง และสมคิด แล้วมีงาน 3 งานคือ ล้างห้องน้ำ ถูพื้น และเช็ดกระจก เราจะกำหนดงานให้แต่ละคนอย่างไรจึงจะเกิดต้นทุนน้อยที่สุด โดยจะแทนต้นทุนการกำหนดต่างๆด้วยเมทริกซ์ ดังนี้

ล้างห้องน้ำ ถูพื้น เช็ดกระจก
สมชาย 100 200 300
สมหญิง 300 300 300
สมคิด 300 300 200

เมื่อเราใช้ขั้นตอนวิธีฮังกาเรียนแล้วจะได้ผลลัพธ์การกำหนดงานให้คนงานแต่ละคน ซึ่งจะเกิดต้นทุนน้อยที่สุดดังนี้ สมชายล้างห้องน้ำ สมหญิงถูพื้น สมคิดเช็ดกระจก

อธิบายขั้นตอนวิธี[แก้]

  • ขั้นตอนวิธีนี้จะต้องมีจำนวนงานและคนงานเท่ากัน หากมีอย่างใดอย่างหนึ่งน้อยกว่าแล้ว เราจำเป็นต้องเพิ่มตัวลวงเข้าไปให้มีจำนวนที่เท่ากัน โดยต้นทุนของตัวลวงนี้จะมีค่าเป็นต้นทุนที่มากที่สุดในตาราง
  • หากเราไม่ต้องการหาต้นทุนน้อยสุด แต่ต้องการหาต้นทุนมากสุดเราสามารถทำได้โดย แก้ไขตารางต้นทุนในแต่ละช่องโดยสมมติให้ MAX คือค่าที่มากที่สุดในตาราง สมาชิกช่องที่ i,j จะมีค่าใหม่เป็น (MAX - สมาชิกข่องที่ i,j)

เมื่อเรามีตารางต้นทุนของการทำงานทุกงานของทุกคนงานแล้วเราจะมาทำตามลำดับขั้นตอนดังนี้

  1. เราจะหาค่าที่น้อยสุดในแต่ละแถวแล้วนำมาลบกับทุกๆสมาชิกในแต่ละแถวนั้นๆ ดังนั้นจะได้ตารางใหม่ที่มีสมาชิกในแต่ละแถวมีค่าเป็น 0 อย่างน้อย 1 ตัว
  2. ต่อจากนั้นเราจะทำแบบเดียวกับขั้นตอนที่ 1 ในทุกๆคอลัมน์ คือหาค่าที่น้อยที่สุดในแต่ละคอลัมน์แล้วนำมาลบกับสมาชิกทุกตัวในคอลัมน์นั้นๆ
  3. หากเรากำหนดงานให้คนงานได้โดยใช้เลข 0 เป็นตัวบอกว่าคนงานใดทำงานใดได้บ้างถึงจะต้นทุนน้อยสุด แล้วสามารถกำหนดงานให้ได้โดยไม่ซ้ำกันแล้ว แสดงว่าเราได้คำตอบอันเป็นที่ต้องการแล้ว ซึ่งอาจจะมีคำตอบได้หลายแบบ แต่ถ้าหากยังไม่สามารถกำหนดงานให้ได้โดยไม่ซ้ำกัน เราต้องขีดเส้นในแถวหรือคอลัมน์ใดๆให้ผ่าน 0 ครบทุกตัว โดยใช้จำนวนเส้นน้อยที่สุด ดังนี้
    1. ให้เราเลือกแถวที่สามารถกำหนดงานให้ได้โดยไม่ซ้ำกันเท่าที่เป็นไปได้
    2. จากนั้นเราจะดูแถวที่ไม่ได้เลือกไว้ และให้ทำสัญลักษณ์ที่แถวนั้น
      1. เราจะดูว่ามีค่า 0 อยู่ในคอลัมน์ใดบ้างในแถวที่เราทำสัญลักษณ์ แล้วเราจะทำสัญลักษณ์ที่คอลัมน์นั้น
      2. ดูที่คอลัมน์ที่ทำสัญลักษณ์ไว้ หากแถวใดมี 0 ก็ทำสัญลักษณ์ที่แถวนั้นด้วย
      3. วนทำจนไม่สามารถทำสัญลักษณ์ได้
    3. ให้เราขีดเส้นในคอลัมน์ที่สัญลักษณ์ และขีดเส้นแถวที่ไม่ได้ทำสัญลักษณ์ จะได้จำนวนเส้นน้อยสุด (หากว่าได้จำนวนเส้นเท่ากับจำนวนงานแล้วแสดงว่าเราได้คำตอบที่ต้องการแล้ว ให้ข้ามไปยังขั้นตอน 5)
  4. เราจะหาสมาชิกในช่องที่ไม่ได้ถูกขีดเส้นและมีค่าน้อยสุด นำไปลบกับสมาชิกทุกตัวที่ไม่ได้ถูกขีดเส้น และนำไปบวกับสมาชิกทุกตัวที่ถูกขีดทับสองเส้น และทำตามขั้นตอนที่ 3-4 ใหม่ จนสามารถกำหนดงานได้โดยไม่ซ้ำกันแล้วจึงไปยังขั้นตอนที่ 5
  5. เมื่อเราได้ตารางที่สามารถขีดเส้นผ่าน 0 ครบทุกตัวโดยใช้จำนวนเส้นเท่ากับจำนวนงานแล้ว หมายความว่าเราได้ตารางซึ่งเป็นคำตอบแล้วคือสามารถกำหนดงานให้คนงานโดยไม่ซ้ำกันและมีต้นทุนน้อยสุด โดยดูว่าช่องใดเป็น 0 ก็คือให้คนงานทำงานนั้นได้ ซึ่งอาจมีคำตอบได้มากกว่า 1 แบบ

ตัวอย่างการใช้ขั้นตอนวิธี[แก้]

ตัวอย่างการทำขั้นตอนวิธีฮังกาเรียน สมมติให้มีคนงาน ก ข ค ง แ และมี งาน ๑ ๒ ๓ ๔ โดยมีตารางต้นทุนดังนี้

32 27 29 30
28 34 26 22
22 24 20 29
31 27 29 26

โดยต่อไปจะขอละตัวระบุคนงานและตัวระบุงานซึ่งยังมีลำดับเหมือนตารางข้างต้น

1. หาค่าน้อยสุดในแต่ละแถวแล้วนำมาลบออกจากสมาชิกทุกๆตัวในแถว จะได้ตารางใหม่เป็น

5 0 2 3
6 12 4 0
2 4 0 9
5 1 3 0

2. จากนั้นหาค่าน้อยสุดในแต่ละคอลัมน์แล้วนำมาลบออกจากสมาชิกทุกๆตัวในคอลัมน์ จะได้ตารางใหม่เป็น

3 0 2 3
4 12 4 0
0 4 0 9
3 1 3 0

3. แล้วเรายังไม่สามารถจัดงานให้คนงานให้มีต้นทุนน้อยสุดโดยไม่ซ้ำกันได้ จึงต้องทำขั้นต่อไป

3 0 2 3
4 12 4 0
0 4 0 9
3 1 3 0

4. เลือกแถวที่สามารถกำหนดงานโดยไม่ซ้ำกันเท่าที่เป็นไปได้ คือแถว 1 2 และ 3

3 0 2 3
4 12 4 0
0 4 0 9
3 1 3 0

5. แล้วทำสัญลักษณ์ที่แถวที่ไม่ได้เลือกไว้ คือแถวที่ 4 แล้วทำสัญลักษณ์ที่คอลัมน์ 4 ที่มีค่า 0 อยู่ จากนั้นดูที่คอลัมน์ 4 พบว่ามี 0 อยู่แถวที่ 2 จึงทำสัญลักษณ์ในแถวที่ 2 แล้วไม่มีค่า 0 ที่คอลัมน์อื่น จึงไปทำขั้นต่อไป

×
3 0 2 3
× 4 12 4 0
0 4 0 9
× 3 1 3 0

6. จากนั้นขีดเส้นให้เราขีดเส้นในคอลัมน์ที่สัญลักษณ์ และขีดเส้นแถวที่ไม่ได้ทำสัญลักษณ์

×
3 0 2 3
× 4 12 4 0
0 4 0 9
× 3 1 3 0

7. จะใช้สมาชิกในช่องที่ไม่ได้ถูกขีดเส้นและมีค่าน้อยสุด คือค่า 1 ลบออกจากสมาชิกทุกตัวที่ไม่ถูกขีดเส้นและ นำไปบวกเข้ากับสมาชิกที่ถูกขีดเส้นสองครั้ง

×
3 0 2 4
× 3 11 3 0
0 4 0 10
× 2 0 2 0

8. จากนั้นจะวนทำจนสามารถกำหนดงานได้โดยไม่ซ้ำ จึงได้ตารางดังนี้ เป็นตารางที่สามารถกำหนดงานให้คนงานได้โดยไม่ซ้ำกันและจะใช้ต้นทุนน้อยที่สุดด้วย โดยค่า 0 บอกถึงว่าคนงานต้องทำงานนั้นๆ หากมีหลายตัวคือทำสามารถได้หลายงาน ทำให้อาจจะมีคำตอบออกมาได้หลายแบบ

1 0 0 4
1 11 1 0
0 6 0 12
0 0 0 0

และจากตารางจะได้คำตอบทั้งหมด 3 แบบ ดังนี้

ผลเฉลยที่ 1 ผลเฉลยที่ 2 ผลเฉลยที่ 3
กำหนดงาน ต้นทุน กำหนดงาน ต้นทุน กำหนดงาน ต้นทุน
ก → ๒ 27 ก → ๒ 27 ก → ๓ 29
ข → ๔ 22 ข → ๔ 22 ข → ๔ 22
ค → ๑ 22 ค → ๓ 20 ค → ๑ 22
ง → ๓ 29 ง → ๑ 31 ง → ๒ 27
รวม 100 รวม 100 รวม 100

รหัสเทียม[แก้]

สำหรับทุกๆแถวของตาราง
  หาค่าที่น้อยสุดในแถวแล้วไปลบออกจากสมาชิกในแถวทุกตัว
สำหรับทุกๆคอลัมน์ของตาราง
  หาค่าที่น้อยสุดในคอลัมน์แล้วไปลบออกจากสมาชิกในคอลัมน์ทุกตัว
ตราบเท่าที่ จำนวนคนงานที่กำหนดงานให้ได้โดยไม่ซ้ำกัน < จำนวนงาน {
  ลากเส้นผ่าน 0 ทุกตัวโดยใช้เส้นน้อยสุด
  หาค่าที่น้อยที่สุดที่ไม่ถูกลากเส้นผ่านนำไปลบกับสมาชิกทุกตัวที่ไม่ถูกลากเส้นผ่าน และไปบวกกับสมาชิกทุกตัวที่ถูกลากเส้นผ่าน 2 เส้น
 }
ฟังก์ชัน หาจำนวนคนงานที่กำหนดงานได้โดยไม่ซ้ำกัน ให้ n คือ จำนวนงาน, count คือ ตัวนับจำนวนคนงานที่สามารถกำหนดงานให้ได้โดยไม่ซ้ำ {
  แถวข้อมูลกำหนดงาน[n] = -1
  แถวกำกับ[n] = 0
  คอลัมน์กำกับ[n] = 0
  สำหรับทุกๆคนงาน i = 0 to n -1
    สำหรับทุกๆงาน j = 0 to n -1
        ถ้า ตาราง[i][j] เท่ากับ 0  และ แถวกำกับ[i] กับ คอลัมน์กำกับ[j] ไม่เท่ากับ 1 {
              แถวข้อมูลกำหนดงาน[i] = j (คนงาน i ทำงาน j)
              แถวกำกับ[i] = แถวกำกับ[j] = 1
              count++
        }
 ถ้า count  ไม่เท่ากับจำนวนงาน คืนค่า count
 หรือถ้า count เท่ากับจำนวนงานแล้ว คืน แถวข้อมูลกำหนดงาน
}
ฟังก์ชัน ลากเส้นผ่าน 0 ทุกตัวโดยใช้จำนวนเส้นน้อยสุด คืนค่าเป็นรายการของแถวและคอลัมน์ที่ลากเส้นผ่าน {
  เลือกแถวที่ไม่สามารถกำหนดงานให้ได้โดยไม่ซ้ำทำสัญลักษณ์ไว้
  ตราบเท่าที่ ยังสามารถทำสัญลักษณ์ที่แถวหรือคอลัมน์ใดๆได้ {
     ทำสัญลักษณ์ที่คอลัมน์ที่มีค่า 0 ในแถวที่ทำสัญลักษณ์ไว้
     ที่คอลัมน์ที่ทำสัญลักษณ์ไว้ หากแถวใดมี 0 ก็ทำสัญลักษณ์ที่แถวนั้นด้วย
  }
  ลากเส้นคอลัมน์ที่ทำสัญลักษณ์ และแถวที่ไม่ได้ทำสัญลักษณ์
  คืนรายการของแถวและคอลัมน์ที่ลากเส้นผ่าน
}

วิเคราะห์ประสิทธิภาพเชิงเวลา[แก้]

ขั้นตอนวิธีนี้มีขั้นตอนย่อยๆหลายขั้นตอน

  1. การลบสมาชิกทุกตัวด้วยสมาชิกที่มีค่าน้อยสุดในแต่ละแถวและคอลัมน์จะใช้เวลา \Theta(n^2)
  2. แล้วฟังก์ชันหาจำนวนคนงานที่กำหนดงานได้ก็ใช้เวลา \Theta(n^2)
  3. การลากเส้นผ่าน 0 ทุกตัวโดยใช้เส้นโดยที่สุดนั้นจะใช้เวลา O(n^2) โดยจะทำเป็นจำนวนอย่างมากไม่เกินจำนวนงานครั้ง ทำให้ในวงวนนี้ใช้เวลา O(n^3)

ดังนั้นสรุปแล้วประสิทธิภาพโดยรวมของขั้นตอนวิธีนี้เป็น O(n^3)

อ้างอิง[แก้]

แหล่งข้อมูลอื่น[แก้]

ตัวอย่าง ซอร์สโค้ด เพิ่มเติม[แก้]