2D 배열에서 교차하지 않는 값의 최소 합계를 찾는 알고리즘이 있습니까?

Question

주어진 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()); 
} 

및 각각의 최소한의 가치를 발견로 행/열 조합을 'used'로 표시하므로 다시 고려되지 않습니다. 그리고 최단 배열 차원에 요소가있는만큼 목록에 최소값이 있으면 해당 최소값의 합을 반환합니다.

문제는이 같은 경우에 고장이다 : 스윕은 마지막 행에 도달하는 시간으로

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

, 이미 열을 '사용'등 최소 사용되지 않는 값으로 0과 1로 표시된 것 행 2에서 3이 실제로 사용되어야하는 경우 1

이 작업을 수행하기위한 표준 알고리즘이 있습니까?

Answer 1

예,이 문제를 정확하게 해결하는 표준 알고리즘이 있습니다. 그것의 이름은 Hungarian algorithm입니다.