Advanced05 백트래킹 (1)백트래킹

1) 소개

* 8퀸 문제

  : 퀸 8개를 8x8 크기의 체스판 안에서 서로 위협하지 않도록 배치하는 모든 경우의 수를 구하는 문제.

- 퀸은 현재 위치에서 상하좌우의 직선방향, 대각선 방향으로 움직일 수 있음.

- 어떤 두 Queen도 서로를 위협하지 않아야함.

- Queen을 배치한 n개의 위치를 어떻게 찾을 수 있을까? 효율적으로 가능한 모든 경우를 찾는 방법은??

* 백트래킹 기법

  : 해가 아니면 되돌아가서 다시 해를 찾아가는 기법.

-> 최적화(optimization) 문제와 결정(decision) 문제 해결 가능.

- 결정 문제 : 문제의 조건을 만족하는 해의 존재 여부를 yes, no로 답하는 문제

ex)  미로찾기 - 미로의 입구에서 출구까지 가는 경로의 존재 유무. 

부분집합의 합(Subset Sum) 문제 - 원소의 합이 조건에 맞는 부분 집합 존재 유무.

n-Qeen, Map coloring 등

- 최적화 문제 : 

ex) 미로찾기 - 출구까지 가는 경로 중 최단 경로를 찾는 문제.

부분집합의 합 문제 : 원소의 개수가 최대인 부분 집합을 찾는 문제.

  : 초기 상태에서 목표 상태로 가는 경로를 탐색하는 기법.

- 여러 선택지(옵션) 중 1가지 선택 -> 선택 후 새로운 선택지 생성 -> 선택을 반복하다 최종 상태에 도달.

   => 올바른 선택들을 계속하면 목표 상태에 도달할 것.

- 당첨 단말 노드 찾기.

: 당첨 노드까지 가기 위한 모든 경로에 대해서 탐색하는 과정.

1. 루트에서 갈 수 있는 노드 선택.

2. 꽝 노드까지 도달 시 최근 선택부터 다시 시작.

3. 더 이상 선택지가 없을 경우 이전 선택지로 돌아가 다른 선택.

4. 루트까지 돌아갔을 때 더 이상 선택지가 없는 경우, 찾는 답이 없음.

- 상태 공간 트리

: 해를 찾기 위한 과정을 트리로 표현한 것.

 - 중간노드 : 최종상태로 가는 중간 상태 표현.

 - 단말노드 : 하나의 후보에 대한 최종 상태.

 - 상태 공간 트리 탐색 => 모든 후보 해 탐색.

*** 트리를 깊이 우선 탐색하는 방법 : 백트래킹 알고리즘 기본 형태.

- 백트래킹과 깊이 우선 탐색과의 차이

: 백트래킹은 경로가 해결책으로 이어지지 않을것 같으면 더 이상 그 경로를 따라가지 않음 => 시도 횟구를 줄임.

+깊이 우선 탐색

- 최종상태로 가는 중간 상태 표현.(모든 경로를 추적함.)

- 경우의 수가 너무 많으면(N! 가지 경우의 수를 가진 문제) 처리 불가능.

+백트래킹

- 가지치기로 불필요한 경로 조기 차단.

- 일반적으로 경우의 수가 줄어 처리 가능.

   but, 최악의 경우, 지수 함수 시간을 요하여 처리 불가능.

* 8퀸 문제

- 모든 후보 해의 수 : 64칸에서 8칸을 선택하는 경우의 수.    64 C 8 = 44억개.

- 실제 해의 수 : 92개.

=> 44억 개가 넘는 후보해들에서 실제 해 92개를 최대한 효율적으로 찾아내는 것이 관건!

* 4퀸 문제

- 퀸들은 같은 행에 존재할 수 없음.

- 각 퀸에 대해 행의 위치를 미리 결정하고, 열의 위치에 대해서만 고려.

- 각 퀸의 위치 결정을 위해 4개의 선택지가 존재함.

- 모든 후보 해의 개수 = 4*4*4*4 = 256 개 = 단말 노드의 개수

- 후보해 : 루트노드 ~ 단말노드의 경로.

- 깊이 우선 탐색을 하여 모든 단말 노드를 방문하면서 후보해들 중 해를 찾음.

- 해답이 될 가능성이 전혀 없는 노드의 후손노드들도 모두 검색해야 하므로 비효율적.

- 해답으로 가는 길이 아니라면(조건을 만족하지 않을 경우) 포기하고 다른 경로 탐색.

방문하는 노드에서 해답 가능성이 없는 경우 탐색 중지

=> 깊이 우선 탐색에 비해 방문하는 노드 수 줄어듦.