2 차원 배열의 모든 0을 포함하는 데 필요한 최소 줄 수는 어떻게 찾을 수 있습니까?

Question

나는 헝가리어 알고리즘의 적절한 구현을 시도하지만 배열의 모든 0을 포함하는 최소 수의 행을 찾는 방법을 고집합니다.

도이 라인을 알아야합니다. 3 단계에서

http://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf

그것이

를 말한다 : 일부 계산 나중에 여기

는 설명입니다

가능한 한 적은 행을 사용하여 행렬의 모든 0을 덮습니다. 기본적으로 시행 착오입니다.

시행 착오는 무엇을 의미합니까? I는, 예를 들어 5 행 5 열의의 2 차원 배열을 갖고 있다면

첫 번째 행은 제 1 및 제 2의 첫 번째 행과 첫 번째 열, 등 등 너무 많은 조합

ISN 모든 제로를 커버 할 이보다 더 효율적인 것이 있습니까? 시행 착오가 O ((N + m)!) 복잡 수단

Answer 1

미리

감사합니다.

모든 행 또는 열을 선택하면 모두 0을 포함하므로 최대 n (m) 라인을 선택하면됩니다.

큰 문제에 대해이 단계를 해결하기 위해 동적 프로그래밍 알고리즘을 구현했습니다.

Answer 2

여기에 2 부분 일치 알고리즘을 구현해야합니다. 그래프에는 두 개의 파티션이 있습니다. 그 중 하나의 꼭지점은 행을 나타내고 다른 하나의 꼭지점은 테이블의 열을 나타냅니다. 행 _i과 열 _j 사이에 모서리가 있습니다 (셀 (i, j)에 1이있는 경우). 그런 다음 최대 2 부분 일치를 만듭니다. bipartite 매칭 알고리듬의 마지막 반복 후에 어떤 매듭 점이 매칭을위한 소스와 증분 경로를 통해 연결되어 있는지를 알아 내야합니다. 증분 경로는 양수 용량의 가장자리 만 사용하는 경로입니다. 당신은해야한다 그림 같은 : 당신이 최대 양자 일치, 싱크 긍정적 용량의 가장자리를 통해 도달 할 수있는 행과 열을 찾을를 찾은 후

  row_1     col_1 
     /       \ 
    /- row_2    col_2 -\ 
source - ....  some_edges   \ sink 
     \        /
     \ - row_n    col_n/
           ..../
           col_m 

. 이제 스크래치해야하는 행과 열의 최소 수는 다음 알고리즘을 사용하여 찾을 수 있습니다. 소스에서 도달 할 수없는 모든 행과 도달 할 수있는 모든 열을 교차하며 이것이 최적의 솔루션입니다.

희망 답변이 도움이됩니다.

Answer 3

나는 그들이 당신에게 시행 착오를 지시 한 이유를 잘 모르겠습니다. 그러나 헝가리 알고리즘은 기하 급수적으로 걸리지 않습니다.

http://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation

기사도, 구현에 대한 링크를 포함하고 일부 온라인 과정 : 라인의 최소 수를 파악하는 방법의 예를 안내 위키 피 디아를 살펴 보자 (3 단계보고) 노트는 헝가리 알고리즘을 사용하는 것보다 더 완전한 기술을 제공합니다.