[알고리즘] 5장. Backtracking

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 5-1

* 트리 방문(tree traversal)
1. preorder : 자신->좌측->우측
2. inorder : 좌측->자신->우측
3. postorder : 좌측->우측->자신
4. level order : 깊이 순서

* <A> 깊이 우선 검색 (depth-first search)
- 뿌리마디(root)가 되는 마디(node)를 먼저 방문한 뒤, 그 마디의 모든 후손마디(descendant)들을 차례로 (보통 왼쪽에서 오른쪽으로) 방문한다. (= preorder tree traversal)

void depth_first_tree_search(node v) {
	node u;
	visit v;
	for (each child u of v)
		depth_first_tree_search(u);
}

* 4-Queens 문제
* 상태 공간 트리 (state space tree)

* 되추적 기술: 마디의 유망성
- 전혀 해답이 나올 가능성이 없는 마디는 유망하지 않다.(non-promising)
- 그렇지 않으면 유망하다.(promising)

* 되추적 기술: 되추적
- 어떤 마디의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 마디의 부모마디(parent)로 돌아가서("backtrack") 다음 후손마디에 대한 검색을 계속하게 되는 절차.
- 부모마디로 돌아가는 것 -> 가지치기(pruning)
- 이 과정에서 방문한 마디만으로 구성된 부분트리 -> 가지친 상태공간 트리(pruned state space tree)

* 되추적 기술 절차
1. 상태공간트리의 깊이우선검색을 실시한다.
2. 각 마디가 유망한지를 점검한다.
3. 만일 그 마디가 유망하지 않으면, 그 마디의 부모마디로 돌아가서 검색을 계속한다.

* <A> 되추적 알고리즘

void checknode(node v) {
	node u;
	if (promising(v))
		if (there is a solution at v)
			write the solution;
		else
			for (each child u of v)
				checknode(u);
}

* 깊이우선검색 vs 되추적
- 실제적으로 트리를 생성하지 않고 묵시적으로(implicitly) 존재
- 검색하는 마디 개수의 비교
- 순수한 깊이우선검색 = 155 마디
- 되추적 = 27 마디

* <A> 되추적 알고리즘 (개량)

void expand(node v) {
	node u;
	for (each child u of v)
		if (promising(u))
			if (there is a solution at u)
				write the solution;
			else
				expand(u);
}

---

📌 5-2

* <A> n-Queens 문제 되추적 알고리즘
- 유망한 마디의 개수를 정확하게 구하기 위한 유일한 방법은 실제로 알고리즘을 수행하여 구축된 상태공간트리의 마디의 개수를 세어보는 수 밖에 없다.

void queens(index i) {
	index j;
	if (promising(i))
		if (i == n)
			cout << col[1] through col[n];
		else
			for (j = 1; j <= n; j++) {
				col[i + 1] = j;
				queens(i + 1);
			}
}

bool promising(index i) {
	index k;
	bool switch;
	k = 1;
	switch = true;
	while (k < i && switch) {
		if (col[i] == col[k] || abs(col[i]-col[k]) == i-k)
			switch = false;
		k++;
	}
	return switch;
}

* 바둑
- 돌을 놓을 수 있는 조건을 적용하여 상태공간을 줄인다.
- 그렇다고 하여도 어마어마한 상태공간의 트리가 된다.
- 돌을 놓을 수 있는 수에 대해서 기대값을 계산하여 좋은 안을 채택한다.
- 인공지능 : 기존의 수를 학습해서 최적의 수를 찾는다.

---

📌 5-3

* <A> 부분집합의 합 구하기 (sum of subsets problem)

- 문제 : n개의 item을 이용해서 item 들의 무게의 합이 W가 되는 부분집합을 구한다.
- 마디의 개수 : 2^(n+1) - 1

void sum_of_subsets(index i, int weight, int total) {
	if (promising(i))
		if (weight == W)
			cout << include[1] through include[i];
		else {
			include[i+1] = "yes";
			sum_of_subsets(i+1, weight + w[i+1], total - w[i+1]);
			include[i+1] = "no";
			sum_of_subsets(i+1, weight, total - w[i+1]);
			}
}

bool promising(index i) {
	return (weight + total >= W) && (weight == W || weight + w[i+1] <= W);
}

---

📌 5-4

* <A> 그래프 색칠하기 (graph coloring)

- 문제 : 지도 칠하기(map coloring), 인접하는 지역을 구분하기 위해 색깔을 할당한다. 4개면 충분
- 마디의 총수 : (m^(n+1) - 1) / (m - 1)

void m_coloring(index i) {
	int color;
	if (promising(i))
		if (i == n)
			cout << vcolor[1] through vcolor[n];
		else
			for (color = 1; color <= m; color++) {
				vcolor[i + 1] = color;
				m_coloring(i + 1);
			}
}

bool promising(index i) {
	index j;
	bool switch;
	switch = true;
	j = 1;
	while (j < i && switch) {
		if (W[i][j] && vcolor[i] == vcolor[j])
			switch = false;
		j++;
	}
	return switch;
}

* 평면 그래프 (planar graph)
- 평면 상에서 이음선(edge)들이 서로 엇갈리지 않게 그릴 수 있는 그래프.

* m coloring problem
- 지도에 m가지 색으로 색칠하는 문제

---