[Algorithms] Backtracking

백트래킹은 어떠한 기준을 만족하는 순서를 구하기 위해서 사용하는 알고리즘 기법이다.
솔루션을 찾아나가는 과정에서 잘못되었을 경우 backtrack을 통해 기존의 부분적인 해로 되돌아 갈 수 있다.

백트래킹 과정은 어떠한 상태의 변화를 나타내는 state space tree를 Depth First Search(DFS)하는 과정으로 볼 수 있으며
중간 중간에 상태가 해를 만들수 있는지 없는지를 판단하여 적절치 못한 부분적인 해일 경우 backtrack한다.
그 적절함의 여부를 promising이라고 하기도 한다. 즉, 어떠한 노드가 non-promising하면 backtrack한다.

백트랙킹은 recursive DFS알고리즘을 통하여 구현될 수 있다.
백트래킹은 시간의 문제일 뿐 해가 존재한다면 어떻게든 반드시 그 해를 찾게 된다.
하지만 그 시간의 문제가 곧 단점이다. 해와는 먼 방향으로 DFS해나갈경우 무한에 가까운 시간이 걸릴 수도 있다.
또한 DFS하기 때문에 같은 부분이 반복될 경우 무한 루프에 빠질 가능성도 있다.

그래도 확실히 해를 찾는다는 첨은 상당히 매력적인것 같다.

백트래킹의 복잡도는 측정할 수 없다.(맞나?)

백트래킹을 이용하여서 위에서 언급한 어떠한 순서를 찾는 문제에 사용할 수 있으며
n개의 queen이 서로 위협하지 않도록 배치하는 n-queen 문제,
그래프의 인접 노드를 서로 다른색으로 칠하도록 하는 m-coloring 문제,
Greedy approach로는 해결 불가능한 0-1 knapsack 문제 등에 사용할 수 있다.

백트래킹 알고리즘을 구현하면 다음과 같은 형태를 띈다.

void backtrack(node v)

{

node u;

if (node v가 promising하면)

  if (v가 해이면)

//해에 관한 적절한 동작

  else

for (v의 모든 child u에 대해서)

  backtrack(u) ;

}