탐색 알고리즘 - 깊이우선탐색, 너비우선탐색 기본개념

OMSCS에서 수강중인 AI과목에서 정석적으로 서치 알고리즘에 대해 배우게 되었습니다. 그간 알고리즘 코딩테스트 공부할 때나 종종 봐왔던 BFS, DFS 였는데 이번 기회에 알게되어 정리해보고자 합니다.

 

Node와 Edge로 구성된 일종의 tree가 있었을 때를 가정하고 설명해보겠습니다.

위 사진은 Romania의 지도입니다. 각 도시(노드) 별로 선(엣지)을 긋고, 거리를 적어놓았습니다. 예를 들어 가장 좌측 상단에 위치한 Oradea 노드의 인접한 노드는 Zerind, Sibiu가 있고 각각의 거리는 71, 151이 되겠습니다.

 

Arad에서 시작해서 Bucharest까지 가는 최단 경로를 구하는 것을 목표로 서치 알고리즘을 비교해보고자 합니다. 

 

Breadth-First Search (BFS)

BFS는 너비우선 탐색입니다. Arad를 기준으로 가까운 도시를 순서대로 찾아나가는게 바로 너비우선 탐색이 되겠습니다. 좀 더 단순화한 형태로 노드를 표현해보자면 아래와 같습니다.

 

https://en.wikipedia.org/wiki/Breadth-first_search

• 출발 지점을 탐색합니다.
• 출발 지점과의 선 갯수가 1개인 노드를 탐색합니다.
• 출발 지점과의 선 갯수가 2개인 노드를 탐색합니다. (마지막 노드가 올때까지 진행함)

 

이런 방식으로 선의 갯수가 적은 노드부터 탐색하는 것이 바로 너비우선 탐색입니다. 말 그대로 한 층을 깊게 파기보다는, 전체적으로 고르게 탐색이 퍼져나가는 것을 알 수가 있는데요. BFS를 통해 목적 노드에 도달하게 되면, 목적 노드와의 최단거리(선 갯수)를 반드시 알 수가 있습니다. 그리고 설령 층이 무한대로 깊어진다고 해도, 반드시 해를 찾을 수 있습니다. 너비우선 탐색이기 때문입니다. 너비 우선탐색을 위한 Pseudocode는 아래와 같습니다.

 

function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure
 if problem's initial state is a goal then return empty path to initial state
 frontier ← a FIFO queue initially containing one path, for the problem's initial state
 reached ← a set of states; initially empty
 solution ← failure
 while  frontier is not empty do
   parent ← the first node in frontier
   for child in successors(parent) do
     s ← child.state
     if s is a goal  then
       return  child
     if s is not in reached then
       add s to reached
       add child to the end of frontier
 return  solution

 

(모든 Pseudocode는 Artificial Intelligence for Modern Approah 원서에서 옮겨왔음을 미리 밝힙니다.)

큐에 원소가 남아있는 한, 끊임없이 child node로 탐색을 이어가고, 만약 child가 탐색되지 않는, 즉 reached에 저장되지 않은 노드라면 frontier에 저장합니다.

frontier는 말그대로 탐색을 시작할 노드가 담긴 리스트라고 보면 되고, reached는 이미 탐색을 완료한 노드들입니다. 

 

 

 

Depth-First Search (DFS)

DFS는 깊이우선탐색을 의미합니다. 즉, BFS와 달리 한 층을 깊게 처음부터 끝까지 파고 들어가서 탐색하는 기법을 의미합니다. 단순화한 그림을 보면 다음과 같습니다.

 

https://en.wikipedia.org/wiki/Depth-first_search

BFS와의 차이점이 보이시나요? 번호 순서대로 탐색을 한다는 것을 다시 한번 상기시켜보면, 1번 노드부터 가장 깊숙한 4번노드까지 진행한 것을 알 수 있습니다. BFS와 달리, DFS는 최단거리(선의 갯수)를 보증하지 않습니다. 또한, 층이 무한대로 깊어질 경우 원하는 목적지에 도달하지 못할 가능성도 있습니다. 무한대의 늪에 빠져버리는 것 입니다. 따라서 Romania 맵과 같이 최단 거리를 찾는 문제에는 DFS보다는 BFS가 보다 적합해보이는데요. DFS가 필요한 상황도 있습니다. 바로 AI 알고리즘 중에 하나인 Minimax입니다.

 

Minimax Algorithm과 Alpha-beta pruning

소위 몇수 앞을 내다본다고들 합니다. 바둑이나 체스에서 많이 나오는데요. 미니맥스 알고리즘이 바로 그것입니다. 알고리즘적으로 몇수 앞을 내다보면서, 패배할 가능성을 최소화하는 방향으로 결정합니다. 자세한 설명은 추후에 다시하겠지만, 대충 아래와 같은 방식으로 작동합니다.

https://www.researchgate.net/figure/Game-tree-for-Tic-Tac-Toe-game-using-MiniMax-algorithm_fig1_262672371

위 게임은 틱탁토라는 게임입니다. 9개의 칸에서 O, X로 두 명의 플레이어가 참여하게 되는데, 마치 오목처럼 3개가 연속으로 배치가 되는 사람이 이기는 게임입니다. 보시는 것처럼 X와 O가 각각 어떤 선택을 할 수 있는지 완전 탐색을 실시합니다. 즉, 모든 수를 내다보는 것입니다. 이 때 주인공 플레이어의 수에 대해서는 Max를 택하고, 상대방 플레이어의 수에 대해서는 Min 값을 택하는 것을 반복하기 때문에 Minimax 알고리즘이라고 부르고 있는데요. 

얼핏보면 BFS처럼 동작하는 것 같지만 DFS 를 사용하는 것이 더 효율적입니다. 위 틱탁토는 사실 경우의 수가 그리 많지 않기 때문에 BFS나 DFS나 동일해보이지만, 체스처럼 경우의 수가 정말 많은 케이스를 생각해봅시다.

 

층의 깊이가 수없이 깊어질텐데, BFS로 하다가는 몇 수 앞을 내다보지도 못한 채 계산 시간이 너무 오래 걸리게 될 것입니다. 따라서 Alpha-beta pruning이라는 방식을 사용합니다. DFS처럼 깊이부터 우선 탐색하고, min-max 값을 사용하기 때문에 계산해야하는 노드의 수를 최소화하는 기법입니다. 

https://micropilot.tistory.com/2973

알파베타 가지치기 방법을 사용하면, 좌측하단의 노드부터 탐색을 시작하면서 사진에 표기된 빗금 부분은 생략하게 됩니다. 즉, 전체를 다 계산할 필요가 없어지고, 계산 효율은 더 개선됩니다. 상세한 설명은 생략하겠지만, 아무튼 여기서 중요한 것은 BFS로 하면 생략과정 없이 전 과정을 다 해야하는 반면, DFS를 사용하면 생략할 수 있기 때문에 효율이 높아진다는 점입니다. 여기서 Iterative Deepening 이라고 하여, exponential하게 늘어나는 연산의 부하를 줄이기 위해 점차 레이어를 깊게 가져가는 방법도 있습니다만... 너무 설명이 길어지므로 생략하겠습니다.

 

 

 

다시 최단거리 문제로 돌아와서...

아무튼 DFS는 위와 같이 게임 AI를 만드는데 사용할 수 있습니다. 다만, Romania 맵처럼 최단거리를 구하는 문제에 있어서는, min max와 같은 특징이 없기 때문에 최적 루트를 아예 찾지 못할 수도 있다는 단점이 있었습니다. 따라서 BFS가 많이 사용된다고 보시면 됩니다.

 

BFS의 대표적인 방법중에 하나가 바로 Dijkstra Algorithm을 이용한 Uniform Cost Search (UCS) 입니다.

 

 

 

Uniform Cost Search (균일 비용 탐색)

다시 로마니아 맵을 가지고 와서 생각해봅니다.

Arad에서 Bucharest까지 가는 방법의 수는 다양합니다. 우리는 최단거리(엣지마다 표기된 거리)로 목적지에 가는 것이 목적입니다. 이 때 단순히 BFS를 통해서 접근하다보면, 최단거리라기보다는, 최소 선의 갯수로 이동할 경로를 찾을 수 있을 것입니다. BFS 설명에도 썼듯이, Edge의 수가 최소인 노드를 발견할 수 있으니까요. 다만 엣지가 최소라고 해서 꼭 최단거리라는 것은 아닙니다.

 

위 사진에서 2가지 경로를 비교해보겠습니다.

• Arad - Sibiu - Fagaras - Bucharest : 노드 4개, 거리 450
• Arad - Sibiu - Rimnicu Vilcea - Pitesti - Bucharest : 노드 5개, 거리 418

보시다시피, 두번째 경로가 거치는 노드의 수는 더 많지만 거리로는 더 짧습니다. 이러한 케이스를 비교할 수 있게 도와주는 게 바로 UCS입니다. UCS의 Pseudocode는 아래와 같습니다. 사실 DFS나 BFS나 pseudocode 자체는 유사합니다. 다만 BFS 중에서도 UCS는 최단거리를 비교해야한다는 차이점이 있습니다.

 

function UNIFORM-COST-SEARCH(problem) returns a solution, or failure
 if problem's initial state is a goal then return empty path to initial state
 frontier ← a priority queue ordered by pathCost, with a node for the initial state
 reached ← a table of {state: the best path that reached state}; initially empty
 solution ← failure
 while  frontier is not empty and top(frontier) is cheaper than solution do
   parent ← pop(frontier)
   for child in successors(parent) do
     s ← child.state
     if s is not in reached  or child is a cheaper path than reached[s] then
       reached[s] ← child
       add child to the frontier
       if child is a goal and is cheaper than solution then
         solution =  child
 return solution

BFS가 child 노드들을 바로 탐색하는 것과 다르게, UCS는 노드 간 거리를 사용합니다. child 노드가 아직 탐색되지 않은 지역이거나, 혹은 이미 탐색된 지역이더라도 최단 거리가 더 짧을 경우 거리를 업데이트하는 방식입니다. BFS는 목적 노드에 도달하는 순간 로직이 종료될 수 있지만, UCS는 도달하더라도 모든 탐색 노드가 마무리될 때까지 반복합니다. 최단 경로가 더 짧아질 수 있으니까요. (사실 위 수도 코드는 모든 내용을 담고 있진 않은 것 같습니다. )

 

 

A Star Search

여기에서 한발 더 나아간 탐색 알고리즘이 있습니다. 바로 A Star Search 알고리즘입니다. 위의 최단 경로만 단순히 비교하는게 아니라, heuristic funtion을 통해서 탐색할 노드의 수를 최소화하는 장점을 가지는데요. UCS와 더불어 A star 알고리즘은 다음 포스팅에서 또 더 깊게, 파이썬 코드도 포함해서 다뤄보도록 하겠습니다.