The Hungarian Algorithm, also known as the Kuhn-Munkres algorithm, is a combinatorial optimization algorithm used to solve the assignment problem. The assignment problem is finding the optimal one-to-one mapping between two equal-sized sets to minimize the total cost.

Here's an outline of the steps for writing the Hungarian Algorithm:

1.  Create a cost matrix from the input data, where each cell represents the cost of assigning the corresponding item from set A to the corresponding item from set B.
    
2.  Subtract the minimum value in each row from all elements in the row to reduce the number of zeros in the matrix.
    
3.  Subtract the minimum value in each column from all elements in the column to further reduce the number of zeros.
    
4.  Mark all the zeros in the matrix and find the minimum number of lines (horizontal and vertical) required to cover all the zeros.
    
5.  If all zeros are covered by the minimum number of lines, then the algorithm is finished and the optimal assignments are found.
    
6.  If there are uncovered zeros, find the smallest element not covered by a line and add it to all the lines covering the zeros in its row and column.
    
7.  Repeat the process until all zeros are covered by the minimum number of lines.
    
8.  The final solution is found by choosing the assignment with the lowest cost for each covered row.
    

Note that there are different implementations of the Hungarian Algorithm, including both O(n^3) and O(n^4) versions.
อัลกอริทึมของฮังการีหรือที่รู้จักในชื่ออัลกอริทึม Kuhn-Munkres เป็นอัลกอริทึมการหาค่าเหมาะที่สุดแบบผสมผสานที่ใช้ในการแก้ปัญหาการมอบหมายงาน ปัญหาในการมอบหมายงานคือการหาแผนที่แบบหนึ่งต่อหนึ่งที่เหมาะสมที่สุดระหว่างชุดที่มีขนาดเท่ากันสองชุดเพื่อลดต้นทุนทั้งหมด ต่อไปนี้เป็นโครงร่างของขั้นตอนในการเขียนอัลกอริทึมของฮังการี: 1. สร้างเมทริกซ์ต้นทุนจากข้อมูลอินพุต โดยแต่ละเซลล์แทนต้นทุนในการกำหนดรายการที่เกี่ยวข้องจากชุด A ให้กับรายการที่เกี่ยวข้องจากชุด B 2. ลบค่าต่ำสุด ค่าในแต่ละแถวจากองค์ประกอบทั้งหมดในแถวเพื่อลดจำนวนศูนย์ในเมทริกซ์ 3. ลบค่าต่ำสุดในแต่ละคอลัมน์ออกจากองค์ประกอบทั้งหมดในคอลัมน์เพื่อลดจำนวนศูนย์เพิ่มเติม 4. ทำเครื่องหมายศูนย์ทั้งหมดในเมทริกซ์และค้นหาจำนวนเส้นขั้นต่ำ (แนวนอนและแนวตั้ง) ที่จำเป็นเพื่อให้ครอบคลุมศูนย์ทั้งหมด 5. หากศูนย์ทั้งหมดครอบคลุมด้วยจำนวนบรรทัดขั้นต่ำ แสดงว่าอัลกอริทึมเสร็จสิ้นและพบการกำหนดที่เหมาะสมที่สุด 6. หากมีศูนย์ที่เปิดอยู่ ให้ค้นหาองค์ประกอบที่เล็กที่สุดที่ไม่ครอบคลุมด้วยเส้นและเพิ่มลงในทุกบรรทัดที่ครอบคลุมศูนย์ในแถวและคอลัมน์ 7. ทำซ้ำขั้นตอนนี้จนกว่าศูนย์ทั้งหมดจะครอบคลุมตามจำนวนบรรทัดขั้นต่ำ 8. วิธีแก้ปัญหาสุดท้ายพบได้โดยเลือกงานที่มีต้นทุนต่ำที่สุดสำหรับแถวที่ครอบคลุมแต่ละแถว โปรดทราบว่ามีการใช้งานอัลกอริทึมของฮังการีที่แตกต่างกัน รวมถึงเวอร์ชัน O(n^3) และ O(n^4)
spam fails_task lang_mismatch pii not_appropriate hate_speech sexual_content quality toxicity humor helpfulness creativity violence