Backtracking

Backtracking

• 모든 경우의 수를 전부 고려한다.
• 탐색할 필요가 없는 상태(=부분적인 조합)를 가지치기(pruning)한다.
• combinatorial search와 연관이 있다.

Backtracking 순서

1. DFS/BFS로 탐색
2. 탐색 도중 해당 탐색이 무의미하다는 판단이 내려지면
3. 새로운 탐색이 가능한 이전 choice point로 backtrack
4. 해당 지점에서 새로운 탐색 개시

고려해야 될 점

1. dfs로 탐색 중 cyclic한 경로가 생길 경우 무한 루프를 돈다.
2. dfs로 구현하면 스택 오버플로우 나는 깊이를 탐색할 경우 프로그램이 죽는다.
3. bfs로 구현하면 queue의 크기를 고려해야 한다.

---

	
    //// pseudocode 
    backtracking(currentNode){
    	if promising(currentNode){ //현재 방문 노드에서 더 탐색할지 여부
        	// 현재 방문 노드가 solution
            if isSolution(currentNode) 
            	sol(currentNode)
            // 현재 방문 노드가 solution이 아닐 경우 계속 탐색
            else  
            	for all childNodes of currentNode // 다음 노드 방문
                	backtracking(childNodes)
        }
		return 
	}

Heuristic

단어의 의미를 이해하기 위해 어원을 살펴보자. "heutiskein" 가 어원이며 "to discover" 라는 의미를 가진다. 무언가를 찾아내는 과정, 시행착오(trial and error)를 통해 지식을 얻게 되는 과정을 뜻한다.

경험적인 지식이기 때문에 항상 해를 보장하지는 않는다. 예를 들어, 무릎이 쑤시니까 비가 온다는 할머니의 경험적인 판단이 높은 확률값을 가질 수 있지만, 당연히 할머니의 무릎이 쑤셔도 비가 안 올 수도 있다.

이런 휴리스틱은 backtracking에서 가지치기 할 때 유용하게 사용 되는 방법론이다. 개발자가 어떤 기준을 가지고 이러이러한 조건에서는 더 이상 탐색할 필요가 없어! 하고 휴리스틱적 판단을 하는 코드를 작성해서, 더 이상 탐색을 진행하지 않고, choice point로 backtrack해서 새로운 탐색을 시작하게 된다.

다만 휴리스틱의 본성상 foolproof하지 않기 때문에, 프로그래머의 문제에 대한 이해도가 중요하다. bounding function은 이런 휴리스틱의 구현이라고 볼 수 있다.

---

REFERENCE

[1] https://www.youtube.com/watch?v=Ar40zcPoKEI&t=305
[2] http://www.aistudy.com/heuristic/heuristic.htm