이분 도 최대 일치 하 는 헝가리 알고리즘 전체 코드

이 글 은 헝가리 알고리즘 이 2 분 도 에 가장 일치 하 는 알고리즘 사고, 완전한 코드 를 구하 고 알고리즘 학습 중의 몇 가지 작은 문제 에 대해 의견 을 발표 했다.
    먼저 이분 도의 2 측 을 A 측 과 B 측 으로 명명 하 다.헝가리 알고리즘 에서 이분 도의 최대 일치 성 을 구 하 는 관건 적 인 명 사 는 확대 경로 이다. 정 의 는 P 가 그림 G 에서 두 개의 일치 하지 않 는 정점 을 연결 하 는 경로 이 고 M 에 속 하 는 변 과 M 에 속 하지 않 는 변 (즉 일치 하고 일치 하 는 변) 이 P 에서 교체 되면 P 를 M 에 대한 확대 경로 라 고 한다.예: (1) A 측 점 a1 과 B 측 점 b1 사이 에 변 이 연결 되 어 있 고 변 a1b1 이 일치 하지 않 으 며 점 a1, b1 도 다른 일치 변 의 점 에 속 하지 않 는 다 면 a1b1 은 확대 경로 입 니 다.다시 말 하면 이렇게 이해 하면 하나의 이분 도 에 대해 초기 상황 에서 임의의 A 와 B 가 연 결 된 변 은 모두 확대 경로 이다.(2) 변 a1b1, b1a 2, a2b 2 가 있 고 b1a 2 가 일치 하 며 a1b1, a2b 2 가 일치 하지 않 으 며 점 a1 과 b2 가 다른 일치 하 는 점 에 속 하지 않 으 면 이 세 변 은 확장 경 로 를 구성한다.
    증 광로 의 정의 에서 다음 과 같은 세 가지 결론 을 내 릴 수 있다.    1. P 의 경로 길 이 는 반드시 홀수 이 고 첫 번 째 변 과 마지막 변 은 모두 M 에 속 하지 않 습 니 다.    2. P 는 역작 동 을 통 해 더 큰 일치 M 을 얻 을 수 있 습 니 다.    3. M 은 G 의 최대 일치 이 며 M 에 대한 확장 경로 가 존재 하지 않 는 다 고 생각 합 니 다.
    알고리즘 윤곽:

(1) M（  ）   (2)        P，             M’  M (3)  (2)             。

    만약 네가 이 알고리즘 을 배 운 적 이 없다 면, 여기까지 이해 할 수 있 을 것 이다.많은 글 에서 확대 경 로 를 찾 으 면 다음 글 이 없다 고 언급 했 습 니 다. 완전한 코드 비교 도 어렵 습 니 다. 다음 문 제 는 다음 과 같 습 니 다. (3) 중복 (2) 어떻게 합 니까?더욱 세분 화 하려 면 반드시 이렇게 해 야 한다.

          for    A     i do   i             ，     （         ）。

    이 산법 의 정확성 은 내 가 아직 하지 않 았 다 는 것 을 증명 하 니, 먼저 실현 을 고려 한 후에 다시 이야기 하 자.우 리 는 알고리즘 을 디자인 할 때 정확성 증명 을 할 생각 을 하지 않 는 다. 일반 알고리즘 책의 욕심 산법 1 장 은 정확성 증명 이론 (의 진) 과 관련 되 지만 중시 되 지 않 는 다.최대 일치 라 는 문제 에 부 딪 히 면 정확성 증명의 중요성 을 알 수 있 고, 그렇지 않 으 면 항상 좀 불안 하 다.먼저 체험 해 볼 수 있 습 니 다. 만약 에 우리 가 A 측 각 점 에서 출발 하여 최대 일치 하 는 경 로 를 찾 을 수 있다 면 마지막 으로 얻 은 최대 일치 하 는 변 수 는 A 측 점 의 수량 과 같 습 니 다. 즉, A 측의 점 을 모두 사용 하면 자 연 스 럽 게 최대 일치 합 니 다.
    여기까지 아직 끝나 지 않 았 습 니 다. 기껏해야 1 / 2 를 할 수 있 는 셈 입 니 다. 순환 중의 매번 확대 경 로 를 찾 는 것 도 쉽 지 않 습 니 다.투 령 상 수상자 의 유명한 공식 을 떠 올 리 면 '프로그램 = 알고리즘 + 데이터 구조' 이다.나 는 이 언론 을 발표 한 논문 을 본 적 이 없다. 이전에 나 는 이 말 에 대해 항상 불확실 한 느낌 을 가지 거나 더 많은 실증 이 필요 했다.나중에 저 는 알고리즘 프로그램 을 작성 하 는 과정 에서 이 말 은 대체적으로 알고리즘 의 윤곽 만 알 면 아직 멀 었 습 니 다. 이 알고리즘 을 적당 한 데이터 구조 에서 실현 해 야 알 수 있 습 니 다. 알고리즘 구 조 를 아 는 것 부터 실현 하 는 것 까지 큰 차이 가 있 기 때 문 입 니 다.이것 은 단지 깨 달 은 한 방면 일 뿐이다.
    알고리즘 을 더욱 세분 화 합 니 다. 이분 도 를 A, B 양측 으로 나 누 는데 이런 방법 은 A 측의 깊이 를 옮 겨 다 니 는 것 으로 볼 수 있 고 A 측 과 B 측의 점 처리 방법 이 다르다 고 볼 수 있 습 니 다.

     A （          A ）    ，      ： 1.  A[i]    。 2. A  B           。 （1） A   A[i]：          。    B             ，               （                         ），      。    B            ， B    B[j]，   （2）。        ，      。        ，     A[i]        。  ，          A     （     ），B           。 （2） B   B[j]，        ，         ，     B[j]       A     A[k]， A[k]           （1）。

    이 과정 에서 하나의 대기 열 기록 으로 확대 경로 가 A 와 B 에서 지나 간 점 을 찾 으 면 확대 경 로 를 찾 은 후에 최대 일치 하 는 것 을 수정 할 수 있 습 니 다.
    자신 이 알고리즘 을 설계 할 때 위조 코드 의 역할 이 나 타 났 다.다음은 위조 코드 를 바탕 으로 완전한 실현 코드 입 니 다.

#include<iostream> #include<deque>
using namespace std; const int COUNTA=6,COUNTB=7;          //   A、B      
int connection[COUNTA][COUNTB] = {0}; //  A、B      （ ）
int match[COUNTA][COUNTB] = {0};      //A、B      

struct elem{ int element; int currentpartner; }; deque<elem> que; void init() { connection[0][0] = 1; connection[0][1] = 1; connection[0][3] = 1; connection[1][1] = 1; connection[1][4] = 1; connection[2][0] = 1; connection[2][3] = 1; connection[2][6] = 1; connection[3][2] = 1; connection[3][3] = 1; connection[3][5] = 1; connection[4][3] = 1; connection[5][3] = 1; } bool bPointInMatch(int point)//  B          
{ for(int i=0;i<COUNTA;i++) { if(match[i][point]==1) { return true; } } return false; } int bFindMatchPoint(int point)//  B           A   
{ for(int i=0;i<COUNTA;i++) { if(match[i][point]==1) { return i; } } return -1; } void maxMatch() { elem queElem; for(int i=0;i<COUNTA;i++) { bool findAugmentPathA = false; int counter=0; queElem.element = i; queElem.currentpartner = -1; que.push_back(queElem);//  

        while(findAugmentPathA==false && counter>=0) { if(!findAugmentPathA) { int aPoint; bool findAugmentPathB = false; for(int j=que[counter].currentpartner+1;j<COUNTB;j++) { if(connection[que[counter].element][j]==1 && match[que[counter].element][j]==0 && !bPointInMatch(j))//         
 { que[counter].currentpartner++; findAugmentPathA = true; //B  
                        counter++; queElem.element = j; queElem.currentpartner = -1; que.push_back(queElem); break; } else if(connection[que[counter].element][j]==1 && match[que[counter].element][j]==0 && bPointInMatch(j)) { que[counter].currentpartner++; findAugmentPathB = true; counter++;//B  
                        queElem.element = j; queElem.currentpartner = -1; que.push_back(queElem); // B     A   
                        aPoint = bFindMatchPoint(j); counter++; queElem.element = aPoint; queElem.currentpartner = -1; que.push_back(queElem); break; } else{ //TODO:      if      ？
 } } if(!findAugmentPathB) { counter = counter-2; } } } //      
        if(findAugmentPathA==true) { bool direction = false; for(int i=0;i<que.size()-1;i++) { if(direction==false) { direction=true; match[que[i].element][que[i+1].element]=1; } else{ direction=false; match[que[i+1].element][que[i].element]=0; } } } while(que.size()>0)//    
 { que.pop_front(); } } //      
    for(int i=0;i<COUNTA;i++) { for(int j=0;j<COUNTB;j++) { if(match[i][j]==1) { cout<<"("<<i<<","<<j<<")"<<endl; break; } } } } int main() { init(); maxMatch(); return 0; }