백트래킹

DFS, 유망성검사, 재귀함수 , 가지치기

모든해, promising(u)

상태공간 트리 표현

 

 

 

 

[개념]여러 후보해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘

 

[특징]

  - 해가 될 조건을만족시키는 “진짜 해”를 효율적으로 찾는 것

 -  DFS(깊이우선탐색) 탐색하는 모든 방법

 

[절차] 문제분석>상태전이트리>DFS<마디유보성>Y:Child 검색,N:가지치기

1)깊이우선탐색(DFS)

2)유망성 검사(Promising, Non-Promising)

3)분할정복 기반 완전검색(Exhaustive Search)

4)전수검사 통한 비효율제거 (Recursive)

5)최적해 찾기

 

- 상태공간트리의깊이 우선검색실시

 - 각 마디가유망한지 점검

 - 만일 유망하지않으면 그 마디의 부모마디로 돌아가서 검색을 계속

 

[저장공간] DFS(트리깊이알때), 스택

 

[단점] 백트래킹 성능이슈 - 스택 오버플로우

[보완] 개선된 백트래킹 알고리즘

 

[소스코드] backtrack(int a[], int k, data input)

 int c[MAXCANDIDATES]; // 다음 위치가 될 수 있는 후보 위치 //

 int ncandidates;          // 다음 위치가 될 수 있는 후보 개수 //

 if ( is_a_solution(a, k, input) )

    process_solution(a, k, inpit);

 else

    construct_candidates(a, k, input, c, &ncandidates);

    for(i=0; i<ncandidates; i++)

         a[k] = c[i];

         backtrack(a, k, input);

         if(finished) return;  // 일찍 종료함 //