[이론]백트래킹

상태공간트리

• 문제 해결 과정의 중간 사태를 각각 한 노드로 나타낸 트리

• 문제 풀이가 진행된 상태를 노드로 나타낸 것

백트래킹

• 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는 방법

• DFS는 백트랙킹의 골격을 이루는 알고리즘

• 상태공간 트리의 루트에서 시작해서 DFS 방식으로 탐색을 해나가는 것과 대응

• 주로 재귀적으로 구현

미로찾기 문제

• 여러 개의 정점(a:출발점 b, c, d, e, f, t: 출구)에서 출구 찾기

알고리즘

maze(v){
visited[v] == YES;
    if(v==T) then {return "성공";} //끝내기
    for each x in L(v) //L(v)은 정점 v와 인접한 정점 집합
     if(visited[x] == NO) then{
         prev[x] = v;
            maze(x);
        }
}