ハンガリー語の方法：構成要素、例 - ドゥーダス - 2025

ハンガリーの方法は、あなたが、コストを最小限に抑えたいとき配分の問題で使用されるアルゴリズムです。つまり、最小コストに基づいて複数の人々をさまざまな活動に割り当てることにより、最小コストを見つけるために使用されます。各アクティビティは、別の人に割り当てる必要があります。

割り当て問題は特別なタイプの線形計画問題であり、複数の人が複数のジョブを完了するコストまたは時間を最小限に抑えることが目標です。

出典：pixabay.com

割り当て問題の重要な特徴の1つは、1つのジョブ（またはワーカー）のみがマシン（またはプロジェクト）に割り当てられることです。

このメソッドは、ハンガリーの数学者D.ケーニッヒによって開発されました。このため、ハンガリー語の割り当て問題の方法として知られています。Kuhn-Munkres割り当てアルゴリズムとしても知られています。

割り当ての問題は、次の2つのフェーズで構成されるこの方法を適用することで簡単に解決できます。

-第1フェーズでは、行の削減と列の削減が実行されます。

-第2段階では、ソリューションが反復的に最適化されます。

ハンガリーの方法とは何ですか？

ハンガリー語の方法は、4つのステップで構成されます。最初の2つのステップは1回だけ実行され、最適な割り当てが見つかるまでステップ3と4が繰り返されます。

n行n列の正方行列は入力データと見なされ、負でない要素のみを含む必要があります。

特定の問題について、マトリックスの行数が列数と等しくない場合は、ケースに応じて、ダミー行またはダミー列を追加する必要があります。これらのダミーセルの割り当てコストは、常にゼロとして割り当てられます。

ステップ1：各行の最小値を引く

配列の各行について、最小値の要素が選択され、その行の各要素から差し引かれます。

ステップ2：各列から最小値を引く

同様に、最小値を持つアイテムが各列で選択され、その列の各アイテムから差し引かれます。

ステップ3：すべてのゼロを最小数の行でカバーする

手順2で得られた行列のすべてのゼロは、行または列のいずれかで、最小数の水平線と垂直線を使用してカバーする必要があります。

すべてのゼロをカバーするために合計n行が必要な場合、nは行列のn倍nのサイズに等しい場合、ゼロ間に最適な割り当てが存在するため、アルゴリズムは停止します。

それ以外の場合で、配列内のすべてのゼロをカバーするために必要な行がn未満の場合は、手順4に進みます。

ステップ4：追加のゼロを作成する

手順3で作成した行の1つでカバーされていない行列（kと呼ばれる）の最小要素が選択されます。

kの値は、線でカバーされていないすべての要素から差し引かれます。続いて、kaの値が2つの線の交点でカバーされるすべての要素に追加されます。

1行でカバーされているアイテムはそのまま残されます。このステップを実行した後、ステップ3に戻ります。

最適な割り当て

アルゴリズムがステップ3で停止した後、各行と各列で1つのゼロのみが選択されるように、ゼロのセットが選択されます。

この選択プロセスで行または列にゼロが1つもない場合、それらのゼロの1つが選択されます。その列または行の残りのゼロは削除され、他の割り当てについても同じことが繰り返されます。

単一のゼロ割り当てがない場合、複数のソリューションがあります。ただし、割り当てのセットが異なっても、コストは変わりません。

追加されたダミーの行または列は削除されます。したがって、この最終行列で選択されたゼロは、元の行列で必要な理想的な割り当てに対応します。

例

4人の労働者（T1、T2、T3、T4）が実行する必要がある4つのアクティビティ（A1、A2、A3、A4）がある会社を考えてみましょう。ワーカーごとに1つのアクティビティを割り当てる必要があります。

次のマトリックスは、特定のワーカーを特定のアクティビティに割り当てるコストを示しています。目的は、これらの4つのアクティビティで構成されるタスクの総コストを最小限に抑えることです。

ステップ1：各行の最小値を引く

まず、各行の最小値を持つ要素を、その行の他の要素から減算します。たとえば、最初の行の最小要素は69です。したがって、最初の行の各要素から69が引かれます。結果の行列は次のとおりです。

ステップ2：各列から最小値を引く

同様に、各列の最小値を持つ要素がその列の他の要素から差し引かれ、次の行列が得られます。

ステップ3：すべてのゼロを最小数の行でカバーする

ここで、マトリックスのすべてのゼロをカバーするために必要なライン（水平または垂直）の最小数を決定します。すべてのゼロは、3行を使用してカバーできます。

必要な行数は3であり、行列のサイズ（n = 4）より小さいため、手順4に進みます。

ステップ4：追加のゼロを作成する

線で覆われていない最小の要素が選択されます。その値は6です。この値は、覆われていないすべての要素から差し引かれ、この同じ値が2つの線の交点で覆われているすべての要素に追加されます。これにより、次のマトリックスが得られます。

ハンガリーの方法で示されているように、ステップ3を再度実行する必要があります。

ステップ3（繰り返し）

ここでも、マトリックスのすべてのゼロをカバーするために必要な最小ライン数が決定されます。今回は4行必要です。

必要な行数は4であり、行列のサイズ（n = 4）に等しいため、行列のゼロ間の最適な割り当てがあります。したがって、アルゴリズムが停止します。

最適な割り当て

方法が示すように、次のゼロからなる選択は最適な割り当てに対応します。

このゼロの選択は、元のコストマトリックスの次の最適な割り当てに対応します。

したがって、ワーカー1はアクティビティ3、ワーカー2、アクティビティ2、ワーカー3、アクティビティ1、ワーカー4はアクティビティ4を実行する必要があります。この最適な割り当ての合計コストは69 + 37 + 11 + 23 = 140。

参考文献

1. ハンガリー語アルゴリズム（2019）。ハンガリーのアルゴリズム。hungarianalgorithm.comから取得。
2. 調査（2019）。ハンガリー語のアルゴリズムを使用した割り当て問題の解決。study.comから取得。
3. 知恵の仕事（2018）。割り当て問題を解決するためのハンガリーの方法-管理のための定量的手法。取得元：wisdomjobs.com。
4. Geeks for Geeks（2019）。割り当て問題のためのハンガリーのアルゴリズム。取得元：geeksforgeeks.org。
5. カーリー・ムーア、ネイサン・ランドマン（2019）。ハンガリー最大一致アルゴリズム。鮮やかさ。 brilliant.orgから取得。