5 대 상용 알고리즘 의 4: 역 추적 법

1. 개념
      역 추적 알고리즘 은 실제 적 으로 매 거 진 검색 시도 과정 과 유사 하 다. 주로 검색 시도 과정 에서 문제 의 해 를 찾 는 것 이다. 해결 조건 이 만족 하지 않 는 것 을 발견 하면 '역 추적' 으로 돌아 가 다른 경 로 를 시도 한다.
   역 추적 법 은 우수한 검색 법 을 선택 하여 우수한 조건 에 따라 앞으로 검색 하여 목 표를 달성 하 는 것 이다.그러나 어떤 단 계 를 탐색 할 때 원래 의 선택 이 좋 지 않 거나 목 표를 달성 하지 못 한 것 을 발견 하면 한 걸음 물 러 서서 다시 선택한다. 이런 통 하지 않 으 면 되 돌아 가 는 기술 은 역 추적 법 이 고 역 추적 조건 을 만족 시 키 는 특정한 상태의 점 을 '역 추적 점' 이 라 고 한다.
     많은 복잡 하고 규모 가 큰 문 제 는 모두 역 추적 법 을 사용 할 수 있 으 며 '통용 문제 풀이 방법' 이라는 미칭 이 있다.
2. 기본 사상
   문 제 를 포함 하 는 모든 해 공간 트 리 에서 깊이 우선 검색 전략 에 따라 루트 노드 에서 공간 트 리 를 깊이 탐색 합 니 다.어떤 결점 을 탐색 할 때 먼저 이 결점 에 문제 의 해 가 포함 되 어 있 는 지 판단 하고 포함 되 어 있 으 면 이 결점 에서 출발 하여 계속 탐색 해 야 한다. 만약 에 이 결점 에 문제 의 해 가 포함 되 어 있 지 않 으 면 한 층 한 층 조상 결점 으로 거 슬러 올라간다.(사실 역 추적 법 은 암시 적 그림 의 깊이 에 대한 우선 검색 알고리즘 이다).
       역 추적 법 으로 문제 의 모든 해 를 구 할 때 는 뿌리 로 거 슬러 올 라 가 야 하고, 뿌리 가 맺 힌 모든 실행 가능 한 자 수 는 모두 수색 되 어야 끝난다.
       역 추적 법 으로 어떤 해 를 구 할 때 문제 의 해 를 찾 으 면 끝난다.
3. 역 추적 법 으로 문 제 를 푸 는 일반적인 절차:
    (1) 주어진 문제 에 대해 문제 의 해결 공간 을 확인한다.
            먼저 문제 의 해결 공간 을 명 확 히 정의 하고 문제 의 해결 공간 은 적어도 문제 의 하 나 를 포함해 야 한다.
    (2) 노드 의 확장 검색 규칙 확인
    (3) 깊이 우선 순위 로 공간 을 검색 하고 검색 과정 에서 가지치기 함수 로 잘못된 검색 을 피한다.
4. 알고리즘 프레임 워 크
     (1) 문제 의 틀
      문제 의 해 는 n 차원 벡터 (a1, a2,..., an) 이 고 제약 조건 은 ai (i = 1, 2, 3,...........................................................
     (2) 비 재 귀 역 추적 프레임 워 크

   1: int a[n],i;

   2:      a[];

   3: i = 1;

   4: while (i>0(    )   and  (     ))  //       

   5: {

   6:     if(i > n)                                              //       

   7:     {   

   8:                 ，  ；

   9:     }

  10:     else                                                   //    i   

  11:     { 

  12:           a[i]       ；

  13:           while(a[i]               )

  14:           {

  15:               a[i]       ；

  16:           }

  17:           if(a[i]      )

  18:          {

  19:                      ；

  20:               i = i+1;                              //        

  21:          }

  22:          else 

  23:         {

  24:                        ；            //   

  25:               i = i –1; 

  26:          }

  27: }

        (3) 재 귀적 알고리즘 프레임 워 크
         역 추적 법 은 해 공간의 깊이 에 대한 우선 검색 으로 일반적인 상황 에서 재 귀 함 수 를 사용 하여 역 추적 법 을 실현 하 는 것 이 비교적 간단 하 다. 그 중에서 i 는 검색 의 깊이 이 고 구 조 는 다음 과 같다.

   1: int a[n];

   2: try(int i)

   3: {

   4:     if(i>n)

   5:            ;

   6:      else

   7:     {

   8:        for(j =   ; j <=   ; j=j+1)  //   i       

   9:        {

  10:            if(fun(j))                 //            

  11:              {

  12:                 a[i] = j;

  13:               ...                         //     

  14:                 try(i+1);

  15:                       （ a[i]    ）;

  16:               }

  17:          }

  18:      }

  19: }