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

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

 ปัญหาการกำหนดงาน 
ขั้นตอนวิธีฮังกาเรียนนี้ใช้แก้ปัญหาการกำหนดงาน ซึ่งเป็นปัญหาชนิดพิเศษของปัญหากำหนดการเชิงเส้นอีกลักษณะหนึ่ง มีรูปแบบคล้ายคลึงกับปัญหาการขนส่ง โดยปัญหาการกำหนดงานจะมีลักษณะดังนี้
 จำนวนงานและจำนวนคนงานเท่ากัน ในกรณีที่ไม่เท่าจะต้องเพิ่มงานหรือคนงานสมมติแล้วแต่ว่าส่วนใดขาดหายไปและให้ต้นทุนการกำหนดงานมากที่สุด
 คนงานจะทำงานได้เพียง 1 งาน
 งานแต่ละงานจะมีคนรับผิดชอบเพียงคนเดียว
 มีต้นทุนการกำหนดงาน  ให้  ทำเป็น  ซึ่งมีเป้าหมายของการกำหนดงานคือการทำให้เกิดต้นทุนน้อยที่สุด หรือเราสามารถดัดแปลงให้หาค่าต้นทุนมากที่สุดได้
ยกตัวอย่างเช่น สมมติให้มีคนงาน 3 คน คือ สมชาย สมหญิง และสมคิด แล้วมีงาน 3 งานคือ ล้างห้องน้ำ ถูพื้น และเช็ดกระจก เราจะกำหนดงานให้แต่ละคนอย่างไรจึงจะเกิดต้นทุนน้อยที่สุด โดยจะแทนต้นทุนการกำหนดต่างๆด้วยเมทริกซ์ ดังนี้
  ล้างห้องน้ำ  ถูพื้น  เช็ดกระจก สมชาย  100  200  300 สมหญิง  300  300  300 สมคิด  300  300  200
เมื่อเราใช้ขั้นตอนวิธีฮังกาเรียนแล้วจะได้ผลลัพธ์การกำหนดงานให้คนงานแต่ละคน ซึ่งจะเกิดต้นทุนน้อยที่สุดดังนี้ สมชายล้างห้องน้ำ สมหญิงถูพื้น สมคิดเช็ดกระจก

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

 ตัวอย่างการใช้ขั้นตอนวิธี 
ตัวอย่างการทำขั้นตอนวิธีฮังกาเรียน สมมติให้มีคนงาน ก ข ค ง แ และมี งาน ๑ ๒ ๓ ๔ โดยมีตารางต้นทุนดังนี้
  1  2  3  45 A 8  11  15  1013 B 9  12  13  1110 C 10  13  14  1112 D 9  14  13  1011E811151210
โดยต่อไปจะขอละตัวระบุคนงานและตัวระบุงานซึ่งยังมีลำดับเหมือนตารางข้างต้น

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 ก็ทำสัญลักษณ์ที่แถวนั้นด้วย
   }
   ลากเส้นคอลัมน์ที่ทำสัญลักษณ์ และแถวที่ไม่ได้ทำสัญลักษณ์
   คืนรายการของแถวและคอลัมน์ที่ลากเส้นผ่าน
 }

 วิเคราะห์ประสิทธิภาพเชิงเวลา 
ขั้นตอนวิธีนี้มีขั้นตอนย่อยๆหลายขั้นตอน
 การลบสมาชิกทุกตัวด้วยสมาชิกที่มีค่าน้อยสุดในแต่ละแถวและคอลัมน์จะใช้เวลา 
 แล้วฟังก์ชันหาจำนวนคนงานที่กำหนดงานได้ก็ใช้เวลา 
 การลากเส้นผ่าน 0 ทุกตัวโดยใช้เส้นโดยที่สุดนั้นจะใช้เวลา  โดยจะทำเป็นจำนวนอย่างมากไม่เกินจำนวนงานครั้ง ทำให้ในวงวนนี้ใช้เวลา 
ดังนั้นสรุปแล้วประสิทธิภาพโดยรวมของขั้นตอนวิธีนี้เป็น 

 อ้างอิง 
 Beryl Castello, The Hungarian Algorithm 
 Hungarian Algorithm tutorial 

 แหล่งข้อมูลอื่น 
 Mordecai J. Golin, Bipartite Matching and the Hungarian Method, Course Notes, Hong Kong University of Science and Technology.
 R. A. Pilgrim, Munkres' Assignment Algorithm. Modified for Rectangular Matrices , Course notes, Murray State University.
 Mike Dawes, The Optimal Assignment Problem , Course notes, University of Western Ontario.
 On Kuhn's Hungarian Method – A tribute from Hungary , András Frank, Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Hungary.
 ตัวอย่าง ซอร์สโค้ด เพิ่มเติม 
 Java implementation
 Python implementation (ดูเพิ่มเติม ที่นี่ )
 Ruby implementation with unit tests
 C# implementation
 Online interactive implementation
 Serial and parallel implementations.
 Implementation in Matlab and C 
 Perl implementation
 Lisp implementation 
 C++ implementation
 Another C++ implementation with unit tests 
 Another Java implementation with JUnit tests (Apache 2.0)
 Matlab implementation 

หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:การจับคู่