[알고리즘] 백트래킹(backtracking) 알고리즘 / 파이썬 Python

되추적 / 백트래킹(backtracking)

• 임의의 집합(set)에서 주어진 기준(criterion)대로
  • 원소의 순서를 선택하는 문제를 푸는 데 적합
• 트리 자료구조의 변형된 깊이 우선 탐색(DFS)
• 모든 문제 사례에 대해 효율적이진 않지만 많은 문제 사례에 대해 효율적임
  • n-Queens, 부분 집합의 합, 0-1 배낭문제, etc

미로찾기 문제

출처: https://www.youtube.com/watch?v=HRwFgtiqHH0

해당 문제는 스택 알고리즘을 이용해서도 풀 수 있다.

예시

pop: stack의 마지막에 있는 것 꺼낸다

posh: stack의 제일 뒤에 쌓는다

DFS 형태로 방문하고 백트래킹 하는 형식으로 문제를 해결할 수 있다.

 

상태공간트리(State Space Tree)

• 상태공간: 해답을 탐색하기 위한 탐색 공간
• 상태공간트리: 탐색 공간을 트리 형태의 구조로 암묵적으로 해석

 

백트래킹 기법

• 상태공간트리를 깊이 우선 탐색(DFS)으로 탐색
• 방문 중인 노드에서 더 하위 노드로 가면 해답이 없을 경우
  •  해당 노드의 하위 트리를 방문하지 않고 부모 노드로 되돌아감 (backtrack)

유망함(promising)

• 방문 중인 노드에서 하위 노드가 해답을 발견할 가능성이 있으면 유망(promising)
• 하위 노드에서 해답을 발견할 가능성이 없으면 유망하지 않음(nonpromising)

백트래킹과 가지치기

• 백트래킹: 상태공간트리를 DFS로 탐색
• 방문 중인 노드가 유망한지 체크
• 만약 유망하지 않으면, 부모노드로 되돌아감(backtrack)

 

가지치기(pruning)

• 유망하지 않으면 하위 트리를 가지치기함
• 가지치기한 상태: 방문한 노드의 방문하지 않는 하위 트리(pruned state)

 

 

백트래킹 알고리즘의 구현

• 상태공간트리를 실제로 구현할 필요는 없음
• 현재 조사중인 가지의 값에 대해 추적만 하면 됨
• 상태공간트리는 암묵적으로 존재한다고 이해하면 됨

n-Queens 문제

• 8-Queens(n=8) 문제의 일반화된 문제
• n*n 체스보드에 n개의 퀸을 배치하는 문제
  • 어떤 퀸도 다른 퀸에 의해서 잡하먹히지 않도록 배치해야함
  • 즉 같은 행, 열, 대각선에는 다른 퀸을 놓을 수 없음

퀸을 놓으면 해당 행, 열, 대각선에는 놓을 수 없음 (공격하므로)

 

n-Queens 문제: 백트래킹(backtracking)

• 백트래킹으로 문제 해결:
• 임의의 집합에서 기준에 따라 원소의 순서를 선택

 

n-queens 문제에 적용:

• 임의의 집합(set): 체스 보드에 있는 n^2개의 가능한 위치
• 기준(criterion): 새로 놓을 퀸이 다른 퀸을 위협할 수 없음
• 원소의 순서(sequence): 퀸을 놓을 수 있는 n개의 위치

 

4-Queens 문제 (n = 4)

4개의 퀸을 4x4 체스보드에 배치

일단, 기본 가정으로 같은 행(row)에는 놓을 수 없음

후보 해답: 4 * 4 * 4 * = 256 가지의 탐색 공간이 있음 (하나의 행에 하나만 놓을 수 있다는 것 -> 4가지, 4개의 행) -> 4*4*4*4

 

 

 

1,1 -> 1번째행의 1번째 열에 놓는다

 

대충 256가지가  이러한 방식으로 나온다 (정답은 아님) - 상태공간트리의 예시