되추적(Backtracking)

되추적(Backtracking)

● 완전 탐색을 개선한 기법

● 후보 해들을 단계적으로 만들어 가는 과정에서 후보 해들을 평가

● 만약 한 후보 해가 최종 해가 될 수 없다고 판단되면 탐색을 멈추고 다른 후보 해를 탐색

● 최적화 문제와 결정 문제 해결 가능

 

하산 길 선택

● 하산 길에 갈림길에 안내 표지판이 없다면??

1. 갈림길에서 한 길을 선택한 후 그 길을 따라 계속해서 간다.

2. 길이 끊어지거나 절벽에 도달하면 갈림길로 되돌아온다.

3. 갈림길에서 다른 길을 선택해서 간다.

 

상태공간 트리란 무엇일까?

● 특정 알고리즘의 진행 과정을 나타낸 트리

- 노드: 한 해의 구성요소들에 대한 특정 선택

- 후보 해: 루트 노드에서 종단 노드까지의 경로

- 후보 해 중에 해가 있음

- 해가 될 가능성이 전혀 없는 노드의 자손 노드들을 고려하지 않음

예: 미로 찾기

↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓    

 

● 노드의 유망성

- 해가 될 가능성이 있는 노드는 유망하고 아니면 유망하지 않다.

 

● 되추적이란??

- 어떤 노드의 유망성을 점검한 후, 유망하지 않다고판정이 되면 그 노드의 부모 노드로 돌아가서    다음 자식 노드에 대한 탐색을 계속한다.

 

- 상태공간 트리에서 깊이 우선 탐색한다. 유망한 노드만 자식 노드 탐색하고, 유망하지 않은 노드는 탐색 중단.