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

ขั้นตอนวิธีชาวฮังกาเรียน หรือ ฮังกาเรียนอัลกอริทึม  คือ ขั้นตอนวิธีการหาค่าเหมาะสมที่สุดเชิงการจัด ซึ่งใช้ในการแก้ ปัญหาการกำหนดงาน ถูกคิดค้นและตั้งชื่อโดย แฮโรลด์ วิลเลียม คุห์น ในปี ค.ศ. 1955 ที่ตั้งชื่อนี้เพราะว่าขั้นตอนวิธีนี้มีพื้นฐานส่วนใหญ่จากการคิดของนักคณิตศาสตร์ชาวฮังกาเรียน 2 คน คือ เดแนช เคอนิก (Dénes Kőnig) และ แยเนอ แอแกร์วารี (Jenő Egerváry) ต่อมาเจมส์ มุนเครสได้นำขั้นตอนวิธีนี้มาตรวจสอบในปี ค.ศ. 1957 และได้พบว่ามีประสิทธิภาพเชิงเวลาเป็นแบบ ตั้งแต่นั้นมาขั้นตอนวิธีนี้จึงเป็นที่รู้จักในชือว่า ขั้นตอนวิธีคุห์น-มุนเครส หรือ ขั้นตอนวิธีการกำหนดงานมุนเครส โดยมีประสิทธิภาพเชิงเวลาของขั้นตอนวิธีดั้งเดิมเป็น <math>O(n^4)</math> แต่อย่างไรก็ตามขั้นตอนวิธีนี้ แจ็ค เอดมันด์ และ ริชาร์ด แมนนิ่งคาร์ป ได้สามารถปรับปรุงให้มีประสิทธิภาพเชิงเวลาเป็น <math>O(n^3)</math> ได้ และในปี ค.ศ. 2006 มีการค้นพบว่า คาร์ล กุสตาฟ จาโคบี (Carl Gustav Jacobi) สามารถแก้ปัญหาการกำหนดงานได้ในคริสต์ศตวรรษที่ 19 และได้เผยแพร่ในปี ค.ศ. 1890 ในภาษาละติน
ปัญหาการกำหนดงาน.
ขั้นตอนวิธีฮังกาเรียนนี้ใช้แก้ปัญหาการกำหนดงาน ซึ่งเป็นปัญหาชนิดพิเศษของปัญหากำหนดการเชิงเส้นอีกลักษณะหนึ่ง มีรูปแบบคล้ายคลึงกับปัญหาการขนส่ง โดยปัญหาการกำหนดงานจะมีลักษณะดังนี้
ยกตัวอย่างเช่น สมมติให้มีคนงาน 3 คน คือ สมชาย สมหญิง และสมคิด แล้วมีงาน 3 งานคือ ล้างห้องน้ำ ถูพื้น และเช็ดกระจก เราจะกำหนดงานให้แต่ละคนอย่างไรจึงจะเกิดต้นทุนน้อยที่สุด โดยจะแทนต้นทุนการกำหนดต่างๆด้วยเมทริกซ์ ดังนี้
เมื่อเราใช้ขั้นตอนวิธีฮังกาเรียนแล้วจะได้ผลลัพธ์การกำหนดงานให้คนงานแต่ละคน ซึ่งจะเกิดต้นทุนน้อยที่สุดดังนี้ สมชายล้างห้องน้ำ สมหญิงถูพื้น สมคิดเช็ดกระจก
อธิบายขั้นตอนวิธี.
เมื่อเรามีตารางต้นทุนของการทำงานทุกงานของทุกคนงานแล้วเราจะมาทำตามลำดับขั้นตอนดังนี้
ตัวอย่างการใช้ขั้นตอนวิธี.
ตัวอย่างการทำขั้นตอนวิธีฮังกาเรียน สมมติให้มีคนงาน ก ข ค ง แ และมี งาน ๑ ๒ ๓ ๔ โดยมีตารางต้นทุนดังนี้
โดยต่อไปจะขอละตัวระบุคนงานและตัวระบุงานซึ่งยังมีลำดับเหมือนตารางข้างต้น
1. หาค่าน้อยสุดในแต่ละแถวแล้วนำมาลบออกจากสมาชิกทุกๆตัวในแถว จะได้ตารางใหม่เป็น
2. จากนั้นหาค่าน้อยสุดในแต่ละคอลัมน์แล้วนำมาลบออกจากสมาชิกทุกๆตัวในคอลัมน์ จะได้ตารางใหม่เป็น
3. แล้วเรายังไม่สามารถจัดงานให้คนงานให้มีต้นทุนน้อยสุดโดยไม่ซ้ำกันได้ จึงต้องทำขั้นต่อไป
4. เลือกแถวที่สามารถกำหนดงานโดยไม่ซ้ำกันเท่าที่เป็นไปได้ คือแถว 1 2 และ 3
5. แล้วทำสัญลักษณ์ที่แถวที่ไม่ได้เลือกไว้ คือแถวที่ 4 แล้วทำสัญลักษณ์ที่คอลัมน์ 4 ที่มีค่า 0 อยู่ จากนั้นดูที่คอลัมน์ 4 พบว่ามี 0 อยู่แถวที่ 2 จึงทำสัญลักษณ์ในแถวที่ 2 แล้วไม่มีค่า 0 ที่คอลัมน์อื่น จึงไปทำขั้นต่อไป
6. จากนั้นขีดเส้นให้เราขีดเส้นในคอลัมน์ที่สัญลักษณ์ และขีดเส้นแถวที่ไม่ได้ทำสัญลักษณ์
7. จะใช้สมาชิกในช่องที่ไม่ได้ถูกขีดเส้นและมีค่าน้อยสุด คือค่า 1 ลบออกจากสมาชิกทุกตัวที่ไม่ถูกขีดเส้นและ นำไปบวกเข้ากับสมาชิกที่ถูกขีดเส้นสองครั้ง
8. จากนั้นจะวนทำจนสามารถกำหนดงานได้โดยไม่ซ้ำ จึงได้ตารางดังนี้ เป็นตารางที่สามารถกำหนดงานให้คนงานได้โดยไม่ซ้ำกันและจะใช้ต้นทุนน้อยที่สุดด้วย โดยค่า 0 บอกถึงว่าคนงานต้องทำงานนั้นๆ หากมีหลายตัวคือทำสามารถได้หลายงาน ทำให้อาจจะมีคำตอบออกมาได้หลายแบบ
และจากตารางจะได้คำตอบทั้งหมด 3 แบบ ดังนี้
รหัสเทียม.
 สำหรับทุกๆแถวของตาราง
 หาค่าที่น้อยสุดในแถวแล้วไปลบออกจากสมาชิกในแถวทุกตัว
 สำหรับทุกๆคอลัมน์ของตาราง
 หาค่าที่น้อยสุดในคอลัมน์แล้วไปลบออกจากสมาชิกในคอลัมน์ทุกตัว
 ตราบเท่าที่ จำนวนคนงานที่กำหนดงานให้ได้โดยไม่ซ้ำกัน < จำนวนงาน {
 ลากเส้นผ่าน 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 ก็ทำสัญลักษณ์ที่แถวนั้นด้วย
 ลากเส้นคอลัมน์ที่ทำสัญลักษณ์ และแถวที่ไม่ได้ทำสัญลักษณ์
 คืนรายการของแถวและคอลัมน์ที่ลากเส้นผ่าน
วิเคราะห์ประสิทธิภาพเชิงเวลา.
ขั้นตอนวิธีนี้มีขั้นตอนย่อยๆหลายขั้นตอน
ดังนั้นสรุปแล้วประสิทธิภาพโดยรวมของขั้นตอนวิธีนี้เป็น <math>O(n^3)</math>