4

特定の2D配列の特定の最小プロパティ（共通の行または列を持たない最小値の合計）を決定するための高速アルゴリズムを探しています。これには名前が必要だと思いますが、それが何と呼ばれているのかわかりません。

入力文字列をスペースで分割し、検索値のコーパス（スペースでも分割）と比較し、各文字列内のトークン間の距離のマトリックスを返す文字列照合システムがあります。これは、入力/出力トークンの組み合わせを再利用しない距離の最小の組み合わせを取ることにより、単一の集約距離になります。

例：

{ 1, 2 }   => 5 (either 1+4, or 3+2)
{ 3, 4 }

{ 0, 2 }   => 6 (because 2+4 < 0+8)
{ 4, 8 } 

{ 1, 0, 0 }
{ 0, 1, 0 } => 0
{ 0, 0, 1 }

{ 2, 3, 4 }
{ 3, 2, 4 } => 6 (2+2+2)
{ 4, 3, 2 }

私が今まで使用してきた素朴なアルゴリズムは次のようになります（C＃）：

public static int Minimux(this int[,] array) {
  var xUsed = new bool[array.GetLength(0)];
  var yUsed = new bool[array.GetLength(1)];
  var xMax = array.GetLength(0);
  var yMax = array.GetLength(1);
  var minima = new List<int>();
  var limit = Math.Min(xMax, yMax);
  int xMin = 0, yMin = 0;
  while (minima.Count < limit) {
    var vMin = Int32.MaxValue;
    for (var x = 0; x < xMax; x++) {
      for (var y = 0; y < yMax; y++) {
        if (xUsed[x] || yUsed[y] || array[x, y] >= vMin) continue;
        vMin = array[x, y];
        xMin = x;
        yMin = y;
      }
    }
    xUsed[xMin] = true;
    yUsed[yMin] = true;
    minima.Add(vMin);
  }
  return (minima.Sum());
}

基本的に配列スイープを実行し、各最小値を検出すると、その行/列の組み合わせを「使用済み」としてマークするため、再度考慮されることはありません。リストに最小値が含まれると、最短の要素と同じ数になります。配列の次元。これらの最小値の合計を返します。

問題は、次のような場合に故障することです。

{ 0, 0, 0 }
{ 0, 0, 0 } => 3 (when it should be returning 1)
{ 1, 2, 3 }

スイープが最後の行に到達するまでに、列0と1はすでに「使用済み」としてマークされているため、行2の未使用の最小値は、3実際に使用する必要があるときです。1

この操作を実行するための標準的なアルゴリズムはありますか？

4

1 に答える 1

5

はい、この問題を正確に解決する標準的なアルゴリズムがあります。その名前はハンガリーのアルゴリズムです。

于 2013-03-12T14:48:05.380 に答える