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

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

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

O（n^3）とO（n^4）バージョンの両方を含むハンガリーのアルゴリズムには、異なる実装があることに注意してください。
human
わかりました、私はこれを理解していると思いますが、それは本当に例を見るのに役立ちます。ハンガリーのアルゴリズムの例を教えてもらえますか？