Kuhn-Munkresアルゴリズムとしても知られるハンガリーのアルゴリズムは、割り当ての問題を解決するために使用される組み合わせ最適化アルゴリズムです。割り当ての問題は、総コストを最小限に抑えるために、2つの等しいサイズのセット間の最適な1対1のマッピングを見つけることです。

ハンガリーのアルゴリズムを書くための手順の概要は次のとおりです。

1.入力データからコストマトリックスを作成します。各セルは、セットAから対応するアイテムに対応するアイテムをセットBから割り当てるコストを表します。
    
2.行のすべての要素から各行の最小値を減算して、マトリックス内のゼロの数を減らします。
    
3.列のすべての要素から各列の最小値を減算して、ゼロの数をさらに減らします。
    
4.マトリックス内のすべてのゼロをマークし、すべてのゼロをカバーするために必要な最小ライン（水平および垂直）を見つけます。
    
5.すべてのゼロが最小行数でカバーされている場合、アルゴリズムが終了し、最適な割り当てが見つかります。
    
6.ゼロが発見されていない場合は、線で覆われていない最小の要素を見つけ、列と列のゼロを覆うすべての線にそれを追加します。
    
7.すべてのゼロが最小行数でカバーされるまでプロセスを繰り返します。
    
8.最終的なソリューションは、カバーされた各列のコストが最も低い割り当てを選択することによって見つかります。
    

O（n^3）とO（n^4）バージョンの両方を含むハンガリーのアルゴリズムには、異なる実装があることに注意してください。
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.