割り当て問題の解法（ハンガリアン法）

機能

• ハンガリアン法で最適解を算出（順列の総当たりはしない）
• 最小化・最大化の両方に対応
• 行数と列数が異なる場合も自動処理し、未割り当ての行・作業を表示
• 数字のみとラベル付きの 2 形式を自動判別
• 割り当てを 1 件 1 行で表示し、個別にコピー可能
• 合計コストを表示（最大化時は総利得として表示）
• 正方行列を要求する設定も可能（非正方なら明確にエラー）
• 最適性が証明された結果。既知の最適解によるテストで担保

使い方

1. コスト行列を入力欄に貼り付けます（数字のみでもラベル付きでも可）
2. 問題の種類を選びます：最小化 / 最大化
3. 非正方行列の場合は自動処理か正方要求を選びます
4. 結果がすぐに表示されるので、必要な割り当てをコピーします

よくある質問

入力できる行列の形式は？

2 通りあります。① 数字のみ：各行がその行のコスト列で、空白かカンマ区切り。行・列は R1…、C1… と命名されます。② ラベル付き：1 行目が列名、以降の各行は先頭が行名で、残りがその行のコストです。判定は「1 行目に数字でない項目が 1 つでもあればラベル付き」なので、数字のみの表を誤判定しません。

行数と列数が違う場合はどうなりますか？

自動処理モードでは、行が多いときはコスト 0 の仮想列を補い、最後に割り当てられなかった行を示します。列が多いときも同様に仮想行を補い、実施されない作業を示します。すべての行・列の制約を満たしつつ、合計は最適のままです。厳密に正方行列を求める場合は「正方行列を要求」に切り替えてください。

この最適解は信頼できますか？

信頼できます。標準的な最短増加路のハンガリアン法（O(n³)）を使い、任意の実数コスト行列で大域最適解を求めます。リポジトリには、既知の最適解を持つ 5×5 行列（最適 13）で結果を固定するテストと、4×4 を総当たりで検算するテストがあります。

最大化はどのように扱われますか？

コストを負にして最小化します。数学的に最大化と等価です。結果には元の利得の合計を表示し、「総利得」と表記するので、負の数の並びを見せられることはありません。