알고리즘 편 - 역 추적 법

머리말:
       역 추적 법 은 여러 절차 로 구 성 된 문제 에 매우 적합 하고 모든 절차 에 여러 가지 옵션 이 있다.우리 가 어떤 단계 에서 그 중의 한 옵션 을 선 택 했 을 때, 다음 단계 로 들 어간 다음, 또 새로운 옵션 에 직면 하 게 된다.우 리 는 최종 상태 에 이 를 때 까지 이렇게 선택 을 반복 한다.       일반적으로 역 추적 법 알고리즘 은 재 귀 실현 코드 에 적합 하 다.우리 가 특정한 노드 에 도 착 했 을 때 가능 한 모든 옵션 을 시도 하고 조건 을 만족 시 키 는 전제 에서 다음 노드 에 전달 합 니 다.다음은 복잡 하지 않 은 코드 를 통 해 두 가지 간단 한 예 제 를 소개 하 겠 습 니 다.
예 1: 행렬 에 어떤 문자열 의 모든 문 자 를 포함 하 는 경로 가 있 는 지 판단 하기 위해 함 수 를 설계 하 십시오.경 로 는 임의의 칸 에서 시작 하여 한 걸음 한 걸음 위로, 아래, 왼쪽, 오른쪽으로 이동 할 수 있다.한 경로 가 행렬 의 한 칸 을 지나 면 이 경 로 는 다시 이 칸 에 들 어 갈 수 없습니다.

//          

bool exist_path(char* matrix,int rows,int cols,char* str){

if(matrix==nullptr || rows<1 || cols<1 ||str==nullptr )
return  false;

bool *visted=new bool[rows*cols];
memset(visted,0,rows*cols);
int pathlength=0;

for(int i=0;i<rows;++i){
for(int j=0;j<cols;++j){
  if(has_path(maxrix,rows,cols,row,col,str,pathlength,visted)){
    return true;
}

}

}
  deleted []visted;
  return false;
}

bool has_path(char* maxrix,int rows,int cols,int row,int col,const char* str,int& pathlength,bool *visted){

if(str[length]='\0')
return true;

bool haspath=false;
if(row>=0&&row<rows && col>=0&&col<cols && !visted[row*cols+col] && maxrix[row*cols+col]==str[pathlength]){
//     
++pathlength;
visted[row*cols+col]=true;
haspath=has_path(maxrix,rows,cols,row-1,col,str,pathlength,visted)
      || has_path(maxrix,rows,cols,row+1,col,str,pathlength,visted) 
      ||has_path(maxrix,rows,cols,row,col+1,str,pathlength,visted)
      ||has_path(maxrix,rows,cols,row,col-1,str,pathlength,visted);


if(!haspath){
   --pahthlength;
   visted[row*col]=false;
}
}

}

  예 2: 고전적 인 8 황후 문제

//                     。    ，      。
//        ，    ，  ，    。     8*8    ，      ，
//                ，  ，     ？

 1 #include<iostream>
 2 #include<math.h>
 3 using namespace std;
 4 
 5 int n=8;
 6 int total=0;
 7 int *c=new int(n);
 8 
 9 bool is_ok(int row){
10     for(int j=0;j!=row;j++){
            //if                        
11         if(c[row]==c[j] || row-c[row]==j-c[j] || row+c[row]==j+c[j])
12             return false;
13     }
14     return true;
15 }
16 
17 void queen(int row){
18     if(row==n)
19         total++;
20     else
21         for(int col=0;col!=n;col++){
22             c[row]=col;
23             if(is_ok(row))
24                 queen(row+1);
25         }       
26 }
27 
28 int main(){
29     queen(0);
30     cout<<total;
31     return 1;
32 }
33  

이 8 황후 문제 해법 은 상당히 간단 한 버 전 일 것 입 니 다. 논리 도 뚜렷 합 니 다. 코드 를 생각해 보고 거 슬러 올 라 가 는 사상 을 이해 할 수 있 습 니 다.모 르 는 곳 은 댓 글로 남 겨 주세요.