🌓 Back Tracking

💫 Back Tracking

---

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
Like 프린세스 메이커, 미연시, 역전 재판, 검은방, 회색도시, 문명 등 선택지가 나눠지는 게임에서 세이브 파일을 통해 현재 선택 이후, 다른 선택지도 선택해보고, 모든 선택지를 다 플레이 해보는 방법
Like 알파고

상태공간트리

백트래킹은 상태를 넘나든다
상태를 넘나든가는 것은, 예를 들어 어떤 시점의 리스트에서 다른 시점의 리스트로 넘어간다는 것

---

Like 보물찾기, 어딘가 숨어 있는 보물(해답)을 찾는 것
보물을 찾으려면 힌트가 있는 지도(Map)가 있어야함

모든 곳을 뒤져봐도 되지만,
보다 빨리, 효울적으로 찾아보자는 것

보물을 찾아내는 전략이 중요 (전략에 따라 백트래킹의 효율이)
i.e. 보물이 있을 만한 곳만 찾아본다던지 (없는 곳은 패스)

Backtracking - 되돌아간다
되돌아가거나 되짚어 가려면, 이미 지나온 길이 당연히 반드시 존재
Why, 더 이상 이 길로 갈 수가 없거나 (필요가 없나), 이미 다 가본 길
(지나간 길을 기억)
So, 되돌아가서 새로운 길을 찾기 위함

i.e. 미로 찾기
출구룰 찾을 때까지 다음 반복

1. 분기점이 나올 때까지 길을 따라 간다. 이 때 지나가는 길은 표시
2. 분기점을 만나면 한 길을 선택하여 역시 표시하면서 계속 진행
3. 길이 막혀 있으면 직전 분기점으로 되돌아감
4. 시도하지 않은 다른 길을 선택하여 1 시작
5. 모든 길을 시도하였다면 직전 분기점까지 되돌아가고, 4 시작

백트래킹은 어떤 일을 한 이후에 그 일을 되물리는(Undo, 없던 일로) 것까지 포함

i.e. 깊이우선탐색 DFS
노드를 방문하고 기록, 아직 방문하지 않은 자식 노드들에 대해 다시 DFS
더 이상 방문할 자식 노드가 없으면, 부모 노드로 돌아감 (Backtracking)

지도
결론적으로 모든 지도는 Tree로 나타냄, Tree를 따라다니며 해결
Tree를 구성하는 노드들을, 상태

🫧 핵심

1. 트리를 어떻게 만들거냐/모델링 할거냐
2. 전략을 세우는 일 (전체 트리 중에 안 방문해도 되는 서브트리/노드 발굴)

DFS를 기반으로 하여 지수 시간 이상의 시간 복잡도를 갖는 문제를 해결하기 위한 기법

• DFS와 차별되는 거의 유일한 특성은 가지치기
  • 가지치기가 거의 이루어지지 않으면 모든 경우의 수를 다 확인해야 하는 무작위 기법과 유사
  • 가지치기가 일어나는 노드가 단말 노드에 가까울수록 효과가 없음. But 루트 노드에서 가까운 노드 에서 가지치기는 잘 발생하지 않음
  • 상대적으로 많은 정보가 축적된 단말 노드 쪽에서 발생할 확률이 높음

💫 상태 State

---

상태 State
시작해서 주어진 문제를 해결하는 과정 중을 특정 순간, 스냅샷을 상태로 (물론 의미있게 구분되는 순간)

i.e. 바둑/체스/오목/틱택토 등 턴제 보드 게임 : 어떤 한 순간의 바둑판/체스판/판 모습
i.e. 0-1 배낭 문제 : 어떤 한 순간의 배낭 모습 (어떤 물건이 들어있고 총 무게의 이익은 얼마인가)

1. 시작 상태에서 출발
   • i.e. 오목 : 빈 바둑판
   • i.e. 0-1 배낭 문제 : 빈 배낭
2. 주어진 규칙에 따라 상태를 계속해서 변화
   • i.e. 오목 : 순서에 맞게 돌을 둘 때마다 (상태가 변화)
   • i.e. 0-1 배낭 문제 : 해당 물건을 집어넣거나 집어넣지 않거나를 결정할 때마다 (상태가 변화)
3. 최종 상태
   • i.e. 오목 : 누가 승리한 상태
   • i.e. 0-1 배낭 문제 : 모든 물건에 대한 결정이 끝난 상태
4. 원하는 해답인 최종 상태일 수도 있고, 해답이 아닌 최종 상태도 가능
   • i.e. 오목 : 우리편이 이긴 최종 상태와 상대방이 이긴 최종 상태
   • i.e. 0-1 배낭 문제 : 이익이 최대인 최종 상태와 그보다는 작은 최종 상태

최종상태는 후보해 Candidate Solution라 부르기도 함
주의 : 대부분은 최종 상태에 해답이 있는데, 어떤 문제는 최종 상태가 아니더라도 해답을 찾을 수 있음

💫 상태 공간 트리 - State Space, Prolem Space

---

지금 이 순간의 내 모습이 최종 상태라면,
탄생으로부터 지금까지 있었던, 있을 수 있던 수많은 갈림길이 상태인 것이고,
그런 수많은 갈림길을 속에 있을 수 있었던, 어쩌 지금 내 모습일 수도 있었던, 또 다른 나의 모습의 무한한 가능성들의 길을 그려 한데 모은 것이 상태 공간 트리와 같은 것이다.

가능한 모든 상태를 트리로 묶어 낸 것
각 상태는 이전 상태로부터 변한 것이고, 이는 다른 모습의 이후 상태로 변화해나감
시작 상태에서 출발하여 전이(Transition)가 가능한 이후 상태를 자식 노드로 연결하고 이 과정을 최종 상태에 이르기까지 반복 -> 상태 공간 트리

• 노드 : 상태
• 루트 노드 : 시작 상태
• 부모 노드 : 이전 상태
• 자식 노드 : 이후 상태

i.e. 0-1 배낭 문제의 상태 공간 트리
@ 5_0000
1', 2, 1', 2, 3', 1', 2, 3', 4' 는 배낭 모양은 똑같지만 (물건 2만 들어가 있지만), 서로 다른 상태

유망하지 않은 노드(Nonpromising Node) : 자식의 상태를 확인할 필요가 없음 (거기로 가봐야 보물이 없어, 답이 없어, 난가?)
유망한 노드 (Promising Node) : 해답을 얻기 위해 자식 노드로 진행할 필요가 있음 (요오망한 노드 ㄷㄷ; 미래가 창창한, 가능성이 있는)

유망하지 않은 노드를 가능한 많이 걸러내는 전략이 매우 중요 - 가지치기 Proning
답이 없는 것들을 미리 쳐낼 수 있는 객관안이 중요하다.

💫 코드 구조와 최적화

---

🫧 DFS

상태 공간 트리의 탐색에는, 효율적인 탐색을 위해, 상태 변화를 추적하기 용이한 DFS를 사용한다.
그래프 DFS를 수정하면 트리 DFS를 구할 수 있다.
이진 트리의 전위 순회를, 트리의 전위 순회로 일반화한다. (가장 왼쪽/오른쪽에 있는 노드부터 ~)

void DFS_Tree(Node node)
{
	DoSomething();
	foreach (Node child in node.Childs)
		DFS_tree(child);
}

• Why Not BFS?
  • 답이 일반적으로 최종 단계, 최종/말단 노드에 있기 때문에, 하나라도 빨리 말단 노드까지 가서 답인지 아닌지 확인해보는게 더 빠르다.
  • 상태를 쓰기 때문이다.
    • 이전 상태를 기억해야 하는데, BFS는 바로 이전 상태가 아닌 정보도 함께 기억해야 된다. 비직관적이고, 비효율적이다.
    • DFS에서는 바로 이전 상태만 기억하기 때문에, 직관적이고 (자연스럽고), 효율적이다.
    • 모든 자식 노드는 이전에 방문하지 않은 노드이고, 자식 노드만을 대상으로 DFS가 이루어지기 때문에 노드를 방문했다는 사실을 기억하거나 확인할 필요가 없다.

🫧 DFS를 더 효율적으로 쓰기 위한 전략

DFS와 Back-Tracking의 차이점, Purning 유무

1. Pruning 가지치기 : 유망하지 않은 노드 걸러내기
2. 유망한 노드에 대해서만 순환호출(Backtracking)

// 백트래킹의 공통된 구조, DFS에 이것저것 붙인 정도
void Backtracking(Node v)
{
	if (Promising(v)) // 1. 요망한 놈에 대해서만 (가지치기, Pruning)
		return;

	if (IsSolution(v)) // 해답이라면 ?
	{
		OutputSolution(v); // 끝 (진행을 끝내는 코드가 생략됨)
	}
	else // 해답이 아니라면 ?
	{
		// 2. (요망한 놈에 대해서만 Backtracking하는 코드가 생략됨)
		foreach (var child in v.Childs)
			Backtracking(child);
	}
}

🫧 최적화 문제 해결을 위한 구조

• 모든 해답을 다 찾아야 하는 문제에 대한 백트래킹: N-Queen
• 결정 문제에 대한 백트래킹: 해밀턴 사이클 문제
• 최적화 문제에 대한 백트래킹
  • 상태 공간 트리를 모두 뒤지는 것이 목표
  • 현재까지의 최적해를 항상 기억하고 있다가, 방문하는 새 노드의 해와 비교한 후 새 노드의 해가 더 낫다면 최적해 값을 변경(갱신)

void BT_OPT(Node v)
{
	optimal = Winner(optimal, Solution(v));
	
	if (Promising(v))
		foreach (Node child in v.childNodes)
			BT_OPT(child);
}

🫧 그 외 전략

• 메모리 낭비를 줄이기 위해 순환 함수를 호출할 때 값이 변하는 변수만 파라미터로 넘기고 순환호출에서 변하지 않는 변수는 전역 변수로 선언

• 트리

  1. 만드는 과정이 너무 오래 걸린다. (이진트리일때, 2^n)
  2. 너무 크다 (메모리 낭비)
     • So, 실제 구현에서는 트리를 안만들고 시작한다 (대안)
     • 상태 공간 트리를 만드는 것이 아니라, 탐색하는 노드의 상태를 배열에 기록하고 추적
       • 상태 공간 트리의 탐색 과정을 배열을 이용하여 시뮬레이션
       • 유망한 노드에 대해서만 배열에 기록하는 작업이 필요

i.e. 0-1 배낭 문제에서 노드의 상태 기록
각 레이어/레벨에서 기억해야 할 정보는, 물건을 배낭에 넣었냐 안넣었냐 딱 하나
따라서 각 단계마다, 현재 레이어/레벨에 들어갈 정보 하나를 넣음
그래서 각 레이어/레벨을 오르락 내리락하면서 답을 찾음 -> 필요한 데이터를 저장하기 위해서는 레이어 높이 만큼의 1차원 배열 하나만 있으면 됨

💫 이용

---

N-Queen
해밀턴 사이클
K-Graph-Coloring
Subset-Sum-Problem
0-1-KnapSack-Problem

💫 Branch and Bound

---

• 백트래킹과 유사하지만 대개 BFS을 기반으로 한 최고 우선 검색(best-first search) 사용
  • 노드를 방문한 후 자식 노드들을 대상으로 각각의 최적해의 한계값(bound) 계산
  • 한계값이 현 최적해보다 좋지 않다면 유망하지 않은 노드
  • 유망한 노드 중에 한계값이 최고인 노드를 선택하여 방문(branch)하며 더 이상 선택할 노드가 존재하지 않을 때까지 선택과 계산을 반복
• 최적해가 있을 확률이 높은 노드 쪽으로 방문을 유도하여 가급적 빨리 최적해에 도달하게 함으로써 유망하지 않은 노드의 비율을 높이는 전략을 사용
• 노드 방문 순서가 정해져 있는 백트래킹과 차별
• BFS는 일반 큐를 사용하여 구현하지만 최고 우선 탐색은 우선순위 큐를 사용하여 구현