헝가리어 알고리즘 - 각 행과 열에 하나만 선택되도록 0s를 선택하는 마지막 단계

Question

Java에서 헝가리어 알고리즘을 구현하려고합니다. 나는 NxN 비용 매트릭스를 가지고있다. 나는 단계별로 this 가이드 단계에 따라 오전 9 단계에 도달했습니다 - ". 각 행 또는 열이 선택된 한 가지도록 제로의 세트를 선택하여 일치하는 선택"

가

이미 0이있는 행렬이 있습니다. 나는 이것을 알아 내려고 노력하고 있었고 나를 위해 일하는 유일한 방법은 무력의 방법이었다.

내가 처음 만났을 때 0을 만났을 때 그 열을 제거하고 & 행을 반복했다. 그러나이 방법은 효과가 없습니다.

트릭이나 방법이 있습니까? 너무 복잡하지 않은 것? 어떤 제안이라도 감사하겠습니다.

감사

Answer 1

헝가리어의 답변 : :)

• 각 행과 열의 0 소자의 수를 계산한다. (row[] 및 column[])
• 최소 (양수) 행과 열의 값을 선택하십시오. 예를 들어, column[3]으로합시다. row에 최소값이있는 경우에도 동일하게 적용되며 행과 열을 바꿔야합니다. 둘 이상의 값이 같은 경우 하나를 선택하십시오.
• 해당 열에서 0 요소를 선택하고 표시하십시오. 둘 이상인 경우 하나를 선택하십시오.
• 당신이 0 요소를 찾을 경우 긍정적를 찾을 수없는 경우, 1
• 하여 해당 row[i] 값을 감소, column[3]의 모든 요소에 column[3] (선택하지 않은 다음)
• 으로 반복 0에 설정 행 또는 열에 값이 없으면 작업이 완료됩니다.