[Algorithms] Backtracking

백트래킹은 어떠한 기준을 만족하는 순서를 구하기 위해서 사용하는 알고리즘 기법이다. 솔루션을 찾아나가는 과정에서 잘못되었을 경우 backtrack을 통해 기존의 부분적인 해로 되돌아 갈 수 있다. 백트래킹 과정은 어떠한 상태의 변화를 나타내는 state space tree를 Depth First Search(DFS)하는 과정으로 볼 수 있으며 중간 중간에 상태가 해를 만들수 있는지 없는지를 판단하여 적절치 못한 부분적인 해일 경우 backtrack한다. 그 적절함의 여부를 promising이라고 하기도 한다. 즉, 어떠한 노드가 non-promising하면 backtrack한다. 백트랙킹은 recursive DFS알고리즘을 통하여 구현될 수 있다. 백트래킹은 시간의 문제일 뿐 해가 존재한다면 어떻게든 반..
Computer Science 2011. 7. 7. 20:02
1