쉽게 배우는 알고리즘 12장. 상태공간 트리의 탐색 http://academy.hanb.co.kr

12장. 상태공간 트리의 탐색 인공지능은 미국인들 특유의 천진난만함의 표현이다. -에드거 다익스트라

학습목표 상태공간 트리가 무엇인지 이해한다. 백트래킹 기법의 작동 원리를 이해한다. 한정분기의 작동 원리를 이해하고, 백트래킹에 비해 장점이 무엇인지 이해하도록 한다. A* 알고리즘의 작동 원리를 이해하고, 어떤 문제들이 A* 알고리즘의 적용 대상인지 감지하도록 한다.

State-Space Tree State-space tree (상태공간트리) 이 장에서 배우는 세가지 상태공간 탐색 기법 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리 이 장에서 배우는 세가지 상태공간 탐색 기법 Backtracking Branch-and-bound A* algorithm

TSP의 예 1 1 1 2 2 2 4 4 4 3 3 3 5 6 5 6 5 6 TSP 예제 해의 예 최적해

TSP와 Adjacency Matrix의 예 1 2 3 4 5 1 3 4 2 5 10 25 14 21 11 30 8 9 7 18 10 30 25 14 21 18 7 9 8 11 3 1 2 3 4 5

사전적 탐색의 State-Space Tree 1 1 2 12 22 32 1-2 1-3 1-4 1-5 3 6 9 39 1-2-3 1-2-4 1-2-5 … … … 1-5-4 4 5 7 8 10 11 40 41 1-5-4-3 1-2-3-4 1-2-3-5 1-2-4-3 1-2-4-5 1-2-5-3 1-2-5-4 1-5-4-2 … 48 44 61 54 45 40 63 63 1-2-3-4-5-1 1-2-3-5-4-1 1-2-4-3-5-1 1-2-4-5-3-1 1-2-5-3-4-1 1-2-5-4-3-1 1-5-4-2-3-1 1-5-4-3-2-1

Backtracking DFS 또는 그와 유사한 스타일의 탐색을 총칭한다 Go as deeply as possible, backtrack if impossible 가능한 지점까지 탐색하다가 막히면 되돌아간다 예 Maze, 8-Queens problem, Map coloring, …

Maze maze Branching tree 그래프로 모델링한 미로 S T 1 2 3 S 4 4 5 3 5 T 6 T 1 2 7 8 9 7 9 S Branching tree 그래프로 모델링한 미로 8

maze(v) { visited[v] ← YES; if (v = T) then {print “성공!”; exit( );} for each x ∈ L(v) ▷ L(v) : 정점 v의 인접 정점 집합 if (visited[x] = NO) then { prev[x] ← v; maze(x); }

Coloring Problem Graph에서 인접한 vertex는 같은 색을 칠할 수 없다 k 개의 색상을 사용해서 전체 graph를 칠할 수 있는가?

Coloring Problem의 예: Map Coloring 1 1 4 2 2 3 4 3 6 5 6 5 (c) 연결관계를 정점과 간선으로 나타낸 것 (d) (c)와 동일한 그래프

if (i = n) then {return TRUE;} else { result ← FALSE; kColoring(i , c) ▷ i: 정점, c: color ▷ 질문: 정점 i-1까지는 제대로 칠이 된 상태에서 정점 i를 색 c로 칠하려면 k 개의 색으로 충분한가? {   if (valid(i, c)) then { color[i] ← c; if (i = n) then {return TRUE;} else { result ← FALSE; d ← 1;  ▷ d: color while (result = FALSE and d ≤ k) { result ← kColoring(i+1, d);   ▷ i+1: 다음 정점   d++; } return result; } else {return FALSE;}

▷ 정점 i와 j 사이에 간선이 있고, 두 정점이 같은 색이면 안된다 valid(i, c) ▷ i: 정점, c: color ▷ 질문: 정점 i-1까지는 제대로 칠이 된 상태에서 정점 i를 색 c로 칠하려면 이들과 색이 겹치지 않는가? { for j ← 1 to i-1 { ▷ 정점 i와 j 사이에 간선이 있고, 두 정점이 같은 색이면 안된다 if ((i, j) ∈ E and color[j] = c) then return FALSE; } return TRUE;

State-Space Tree 1 1, 1 2 3 2, 1 2, 2 4 5 3, 1 3, 2 TSP-사전식탐색.wmf 1 6 7 4, 1 4, 2 2 3 4 8 5, 1 5 6 9 10 11 6, 1 6, 2 6, 3

Branch-and-Bound 분기branch와 한정bound의 결합 Backtracking과 공통점, 차이점 분기를 한정시켜 쓸데없는 시간 낭비를 줄이는 방법 Backtracking과 공통점, 차이점 공통점 경우들을 차례로 나열하는 방법 필요 차이점 Backtracking – 가보고 더 이상 진행이 되지 않으면 돌아온다 Branch-&-Bound – 최적해를 찾을 가능성이 없으면 분기는 하지 않는다

P6 P1 P6 P1 P5 P5 P2 P2 P4 P4 P3 P3 어느 시점에 가능한 선택들 최적해를 포함하지 않아 제외하는 선택들

TSP 예제를 대상으로 한 Branch-and-Bound 탐색의 예 (State-Space Tree) 1 1 (33) 0+33 10 19 18 2 1-2 1-3 1-4 1-5 (33) 10+23 (33) 10+23 TSP-한정트리.wmf (53) 30+23 (48) 25+23 6 9 3 17 11 14 1-2-3 1-2-4 1-2-5 1-3-2 1-3-4 1-3-5 (35) 19+16 (37) 24+13 (44) 31+13 (33) 20+13 (33) 17+16 (44) 28+16 7 8 4 5 12 13 15 16 1-2-3-4 1-2-3-5 1-2-5-3 1-2-5-4 1-3-4-2 1-3-4-5 1-3-5-2 1-3-5-4 1-2-3-4-5-1 1-2-3-5-4-1 1-2-5-3-4-1 1-2-5-4-3-1 1-3-4-2-5-1 1-3-4-5-2-1 1-3-5-2-4-1 1-3-5-4-2-1 48 44 45 40 52 40 58 43

A* Algorithm Best-First-Search 각 정점이 매력함수값 g(x)를 갖고 있다 방문하지 않은 정점들 중 g(x) 값이 가장 매력적인 것부터 방문한다 A* algorithm은 best-first search에 목적점에 이르는 잔여추정거리를 고려하는 알고리즘이다 Vertex x로부터 목적점에 이르는 잔여거리의 추정치 h(x)는 실제치보다 크면 안된다

Shortest Path 문제 Remind: Dijkstra algorithm A* algorithm에서는 목적점이 하나다 시작점은 하나 시작점으로부터 다른 모든 vertex에 이르는 최단경로를 구한다 (목적점이 하나가 아니다) A* algorithm에서는 목적점이 하나다

Dijkstra Algorithm의 작동 예 30 23 25 24 18 28 20 29 39 40 16 10 19 17 30 23 25 24 18 28 20 29 39 40 16 10 19 17 ∞ s t 다익스트라1.wmf 30 23 25 24 18 28 20 29 39 ∞ 40 16 10 19 17 30 23 25 24 18 28 20 29 39 ∞ 40 16 10 19 17

30 23 25 24 18 28 20 29 39 ∞ 40 16 10 19 17 30 23 25 24 18 28 20 29 39 ∞ 40 16 10 19 17 41 다익스트라2.wmf 30 23 25 24 18 28 20 29 39 61 40 16 10 19 17 41 64 50 30 23 25 24 18 28 20 29 39 ∞ 40 16 10 19 17 41 50

다익스트라2.wmf 19 19 10 10 30 24 30 24 20 10 30 20 10 30 17 16 41 41 20 17 16 20 23 18 23 18 17 25 23 61 17 25 23 28 61 28 20 28 20 28 17 64 17 64 25 39 25 39 25 29 40 25 29 40 50 50

A* Algorithm의 작동 예 ∞ ∞ 추정 잔여거리 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 19 24 20 10 61 24 40 20 10 30 16 17 20 52 19 23 18 25 28 20 28 68 34 17 39 19 52 25 29 A-star1.wmf 40 39 (71) ∞ 19 19 (70) 10 ∞ ∞ 24 30 24 20 10 30 20 10 30 ∞ 16 ∞ 16 ∞ 17 20 17 20 23 18 23 18 ∞ 25 ∞ ∞ 17 25 23 ∞ 28 20 28 28 20 28 (85) 17 ∞ (57) ∞ 17 ∞ 25 39 39 25 29 40 (77) 25 29 40 ∞ ∞

추정잔여거리를 사용함으로써 탐색의 단계가 현저히 줄었다 (71) (71) 19 (70) 19 (70) 10 10 30 24 30 24 20 10 30 (60) 20 10 30 (60) A-star2.wmf 16 41 41 17 20 17 16 20 23 18 23 18 17 25 23 28 61 17 25 23 61 28 20 28 20 28 (85) (57) (85) (57) 17 ∞ 17 ∞ 25 25 39 39 (77) 25 29 40 (77) 25 29 40 50 50 (89) (89) 추정잔여거리를 사용함으로써 탐색의 단계가 현저히 줄었다

TSP 예제를 대상으로 한 A* Algorithm 탐색의 예 (State-Space Tree) 1 1 (33) 0+33 2 3 1-2 1-3 1-4 1-5 (33) 10+23 TSP-A-Star.wmf (33) 10+23 (53) 30+23 (48) 25+23 7 4 5 6 1-2-3 1-2-4 1-2-5 1-3-2 1-3-4 1-3-5 (35) 19+16 (37) 24+13 (44) 31+13 (33) 20+13 (44) 28+16 (33) 17+16 8 1-2-3-4 1-2-3-5 1-2-5-3 1-2-5-4 1-3-4-2 1-3-4-5 1-3-5-2 1-3-5-4 1-2-3-4-5-1 1-2-3-5-4-1 1-2-5-3-4-1 1-2-5-4-3-1 1-3-4-2-5-1 1-3-4-5-2-1 1-3-5-2-4-1 1-3-5-4-2-1 48 44 45 40 52 40 58 43

A* Algorithm이 첫 Leaf Node를 방문하는 순간 종료되는 이유 영역과 영역의 leaf node들이 모두 40 보다 커질 수 없는 이유를 이해할 것 1-5 (48) 25+23 A-Star-따지기 1-2-5 1-3-5 (33) 20+13 (35) 19+16 … 1-2-5-3 1-2-5-4 … 1-3-5-2 1-3-5-4 … 125341 125431 125341 125431 152351 152431 153241 153421 154231 154321 45 40 58 41 방문된 leaf node 계산된 leaf node들 계산되지 않은 leaf node들

Thank you