쉽게배우는알고리즘 ( 한빛미디어 ) 2 장. 상태공간트리의탐색
State-Space Tree State-space tree ( 상태공간트리 ) 문제해결과정의중간상태를각각한노드로나타낸트리 이장에서배우는세가지상태공간탐색기법 Backtracking Branch-and-bound A * algorithm - 2 - 한빛미디어
Travelling Salesman Problem 의예 물건을판매하기위해여행하는세일즈맨의문제 물건을팔기위해서어떤도시를먼저방문해서최소한의비용으로도시들을모두순회하고돌아올수있는지를구하는것 TSP 는가장대표적인 NP-Hard 문제 NP-Hard 란 Nondeterministic Polynomial - Hard 의약자 다항식으로표현될수있을지의여부가아직알려지지않았다는의미 NP-Hard 란 TSP 문제와같이모든경우의수를일일히확인해보는방법이외에는다항식처럼답을풀이할수없는문제들을말함 2 2 2 4 4 4 3 3 3 5 6 5 6 5 6 TSP 예제해의예최적해 - 3 - 한빛미디어
TSP 와 Adjacency Matrix 의예 2 3 4 5 0 0 2 0 0 0 30 25 25 4 5 0 9 0 0 3 3 3 0 0 7 7 4 8 30 8 2 4 2 3 4 5 0 0 4 2 0 0 8 0 7 9 8 7 0 3 4 0 0 3 0-4 - 한빛미디어
사전적탐색의 State-Space Tree 2-2 2 22 32-3 -4-5 3 6-2-3-2-4 9-2-5 39-5-4 4 5 7 8 0 4-2-3-4 -2-3-5-2-4-3 -2-4-5-2-5-3 -2-5-4-5-4-2 -5-4-3 48 44 6 54 45 63 63-2-3-4-5- -2-3-5-4- -2-4-3-5- -2-4-5-3- -2-5-3-4- -2-5-4-3- -5-4-2-3- -5-4-3-2- - 5 - 한빛미디어
Backtracking DFS 또는그와유사한스타일의탐색을총칭한다 Go as deeply as possible, backtrack if impossible 예 가능한지점까지탐색하다가막히면되돌아간다 Maze, 8-Queens problem, Map coloring, - 6 - 한빛미디어
Maze maze T S S 4 3 5 2 6 7 S 그래프로모델링한미로 8 2 3 4 5 T 6 T 9 7 8 9 Branching tree - 7 - 한빛미디어
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); } - 8 - 한빛미디어
Coloring Problem Graph 에서 인접한 vertex 는같은색을칠할수없다 k 개의색상을사용해서전체 graph 를칠할수있는가? - 9 - 한빛미디어
Coloring Problem 의예 : Map Coloring (a) 지도 (b) 구역간의인접관계 2 3 4 2 3 4 5 6 5 6 (c) 연결관계를정점과간선으로나타낸것 (d) (c) 와동일한그래프 - 0 - 한빛미디어
kcoloring(i, c) i: 정점, c: color 질문 : 정점 i-까지는제대로칠이된상태에서정점 i를색 c로칠하려면 k 개의색으로충분한가? { if (valid(i, c)) then { color[i] c; if (i = n) then {return TRUE;} else { result FALSE; } } return result; } else {return FALSE;} d ; d: color while (result = FALSE and d k) { result kcoloring(i+, d); i+: 다음정점 d++; } - - 한빛미디어
valid(i, c) i: 정점, c: color 질문 : 정점 i- 까지는제대로칠이된상태에서정점 i 를색 c 로칠하려면이들과색이겹치지않는가? { for j to i- { 정점 i 와 j 사이에간선이있고, 두정점이같은색이면안된다 if ((i, j) E and color[j] = c) then return FALSE; } return TRUE; } - 2 - 한빛미디어
State-Space Tree, 2 2, 3 2, 2 4 5 3, 3, 2 6 7 4, 4, 2 2 3 4 5 6 8 5, 9 0 6, 6, 2 6, 3-3 - 한빛미디어
Branch-and-Bound 분기 branch 와한정 bound 의결합 분기를한정시켜쓸데없는시간낭비를줄이는방법 Backtracking 과공통점, 차이점 공통점 경우들을차례로나열하는방법필요 차이점 Backtracking 가보고더이상진행이되지않으면돌아온다 Branch-&-Bound 최적해를찾을가능성이없으면분기는하지않는다 - 4 - 한빛미디어
P P 6 P P 6 P 5 P 5 P 2 P 2 P 4 P 4 P 3 P 3 어느시점에가능한선택들 최적해를포함하지않아제외하는선택들 - 5 - 한빛미디어
TSP 예제를대상으로한 Branch-and-Bound 탐색의예 (State-Space Tree) (33) 0+33 2-2 (33) 0+23 0 9 8-3 (33) 0+23-4 (53) 30+23-5 (48) 25+23 (37) 24+3 6 9-2-3-2-4 (44) 3+3 3 7 4-2-5 (33) 20+3 (44) 28+6-3-2-3-4 (33) 7+6-3-5 (35) 9+6 7 8 4 5 2 3 5 6-2-3-4 -2-3-5-2-5-3 -2-5-4-3-4-2 -3-4-5-3-5-2 -3-5-4-2-3-4-5- -2-3-5-4- -2-5-3-4- -2-5-4-3- -3-4-2-5- -3-4-5-2- -3-5-2-4- -3-5-4-2- 48 44 45 52 58 43-6 - 한빛미디어
A * Algorithm Best-First-Search 각정점이매력함수값 g(x) 를갖고있다 방문하지않은정점들중 g(x) 값이가장매력적인것부터방문한다 A * algorithm 은 best-first search 에목적점에이르는잔여추정거리를고려하는알고리즘이다 Vertex x 로부터목적점에이르는잔여거리의추정치 h(x) 는실제치보다크면안된다 f(n): 평가함수 f(n) = g(n) + h(n) g(n): 출발노드로부터노드 n 까지의경로비용 h(n): 노드 n 으로부터목표노드까지의추정경로비용 - 7 - 한빛미디어
Shortest Path 문제 Remind: Dijkstra algorithm 시작점은하나 시작점으로부터다른모든 vertex 에이르는최단경로를구한다 ( 목적점이하나가아니다 ) A * algorithm 에서는목적점이하나다 - 8 - 한빛미디어
Dijkstra Algorithm 의작동예 20 0 7 25 7 s 9 30 6 23 24 8 28 20 39 25 29 28 20 t 20 0 7 0 7 25 9 30 23 25 24 8 28 20 39 6 29 28 20 0 9 30 24 20 0 30 7 0 6 23 8 7 25 23 28 20 7 25 39 25 29 28 20 0 9 30 24 20 0 30 7 0 6 23 8 7 25 23 28 20 7 25 39 25 29 28 20-9 - 한빛미디어
0 9 30 24 20 0 30 7 0 6 23 8 7 25 23 28 20 7 25 39 25 29 28 20 0 9 30 24 20 0 30 7 0 6 23 8 7 25 23 28 20 7 25 39 25 29 4 28 20 0 9 30 24 20 0 30 7 0 6 23 8 7 25 23 28 20 7 25 39 25 29 50 4 20 28 64 6 0 9 30 24 20 0 30 7 0 6 23 8 7 25 23 28 20 7 25 39 25 29 50 4 28 20-20 - 한빛미디어
0 9 30 24 20 0 30 7 0 6 23 8 7 25 23 28 20 7 25 39 25 29 50 4 64 28 20 6 0 9 30 24 20 0 30 7 0 6 23 8 7 25 23 28 20 7 25 39 25 29 50 4 64 28 20 6-2 - 한빛미디어
A * Algorithm 의작동예 20 0 7 25 7 9 24 30 6 23 8 28 20 39 25 29 28 20 68 6 52 52 34 39 추정잔여거리 9 9 9 24 20 0 30 7 0 6 23 8 25 28 20 7 39 25 29 20 28 (7) (70) 0 9 30 24 20 0 30 7 0 6 23 8 7 25 23 28 20 (85) (57) 7 25 39 (77) 25 29 28 20-22 - 한빛미디어
(7) 9 (70) 0 30 24 20 0 30 (60) 7 0 6 4 20 23 8 7 25 23 28 20 28 (85) (57) 7 25 39 (77) 25 29 50 (89) 6 (7) 9 (70) 0 30 24 20 0 30 7 0 6 23 8 7 25 23 28 20 (85) (57) 7 25 39 (77) 25 29 50 (89) (60) 4 20 28 6 추정잔여거리를사용함으로써탐색의단계가현저히줄었다 - 23 - 한빛미디어
TSP 예제를대상으로한 A * Algorithm 탐색의예 (State-Space Tree) (33) 0+33 2 3-2 (33) 0+23-3 (33) 0+23-4 (53) 30+23-5 (48) 25+23 (37) 24+3 7 4 5 6-2-3-2-4 (44) 3+3-2-5 (33) 20+3 (44) 28+6-3-2-3-4 (33) 7+6-3-5 (35) 9+6 8-2-3-4 -2-3-5-2-5-3 -2-5-4-3-4-2 -3-4-5-3-5-2 -3-5-4-2-3-4-5- -2-3-5-4- -2-5-3-4- -2-5-4-3- -3-4-2-5- -3-4-5-2- -3-5-2-4- -3-5-4-2- 48 44 45 52 58 43-24 - 한빛미디어
예제 : 8- 퍼즐문제 (A*) f(n) = g(n) + h(n) - 25 - 한빛미디어
A* search for finding path from a start node to a goal node in a robot motion planning problem. http://upload.wikimedia.org/wikipedia/commons/5/5d/astar_progress_animation.gif - 26 - 한빛미디어
A* Pathfinding Algorithm Visualization http://www.youtube.com/watch?v=9hg22hby8-27 - 한빛미디어
Local Beam Search Best-First search 에서기억노드의수를제한하는방법 기억공간이축소되지만너무빠른가지치기를초래 BFS search로다음상태의해집합을구함 해집합을 Goal에가까운순으로정렬 사전설정된수만큼의해집합만을유지하고나머지는잘라냄 - 28 - 한빛미디어
Hill Climbing 기법 hill climbing 기법은 DFS(depth-first search) 를기초로하여 heuristic 을적용한탐색기법으로현재상태와자식노드와의거리 ( 혹은비용 ) 에따라정렬 (sort) 한후각단계 (step) 의선택이이전단계의상태보다나은지를평가함 지역최대치 (local maxima) 문제 ( 작은언덕 ; foothills) 정상주변에정상보다낮은봉우리들이있을때, 그주변봉우리에오를경우그곳이정상인것으로판단할수있다. - 29 - 한빛미디어
Genetic Algorithm ( 유전알고리즘 ) 자연계생물의유전과진화의메카니즘을공학적으로모델화하는일종의확률탐색방법으로, 생물의유전자모양으로탐색을진행하며, 탐색 (search), 최적화 (optimization), 기계학습 (machine learning) 의도구로서많이사용됨 근접한최적해를찾기쉽고병렬적탐색이가능하며지역최적해 (local maximum) 에빠지지않음 그러나만약탐색이해의사이로진행되는경우결과를찾지못할가능성이있으며, 해를찾는다하더라도찾는과정을알수없음. 적합한분야 TSP, 고차함수의근사최적해문제, 신경망최적화, 기타 NP-Hard 문제중일부 적합하지않은분야 :N Shortest path 문제, Sorting, Finding 유전알고리즘의응용예들 함수근사, 신경망최적화, 퍼지시스템최적화, 엘리베이터그룹스케줄링, TSP, 네트웍배치, 그래프분할, 회로라우팅 - 30 - 한빛미디어