[인공지능] Uninformed Search 알고리즘 비교

[이 글은 고려대학교 윤수식 교수님 COSE361 강의 중간고사 내용 정리를 위해 작성한 글입니다.]

 

Uninformed Search란 Heuristic하지 않은, 즉 goal로부터 현재 state가 얼마나 가까운지를 고려하지 않은 모든 Search 알고리즘을 의미한다.

 

 

1. Depth-First Search

흔히 알려진 DFS는 깊이를 우선적으로 탐색하며, 스택 구조를 통해 구현된다.

Time complexity

DFS에서 최악의 경우는 가장 오른쪽 아래의 leaf node에 Goal State가 있는 경우이다.

이때는 모든 노드를 탐색해야 하므로 시간 복잡도는 $O\left ( b^{m} \right ) $가 된다.

 

 

Space complexity

반면 Space Complexity의 경우 현재 탐색중인 path만을 담으면 된다. 현재의 path에 goal이 없다면 다시 path를 검색해야 하고

이를 위해서는 탐색한 노드의 형제 노드를 저장하고 있어야 한다. 가장 leaf node까지의 형제 노드를 모두 저장하고 있을 때는 $bm$개의 노드를 저장해야 하므로 $O\left ( bm \right ) $ 공간 복잡도로 나타낼 수 있다.

 

 

Complete

DFS의 경우 끝이 없는 무한 path에 빠질 수 있으므로 Complete 하지 않다.

 

Optimal

DFS의 경우 cost를 전혀 고려하지 않으므로 optimal하지 않다.

 

2. Bread-First Search

BFS는 너비 우선 검색으로 큐를 사용하여 구현 된다.

Time complexity

BFS에서 최악의 경우는 DFS와 동일하게 가장 오른쪽 아래의 leaf node에 Goal State가 있는 경우이다.

이때는 모든 노드를 탐색해야 하므로 시간 복잡도는 $O\left ( b^{m} \right ) $가 된다.

 

 

Space complexity

BFS는 한 번 path를 검색하고 이를 폐기하는 것이 아닌 위에서부터 순차적으로 모든 tier를 검색하면서 내려오므로 Space complexity는 $O\left ( b^{m} \right ) $이다. 

 

Complete

DFS와 달리 끝이 없는 무한 path에 빠질 위험이 없으므로 Complete 하다.

 

Optimal

BFS의 경우도 cost를 전혀 고려하지 않으므로 optimal하지 않다.

 

3. Iterative-Deepening Search

Iterative deepening search는 DFS를 수행하되, 깊이 제한을 두고 이를 반복해서 늘려가는 방식이다.

깊이가 1이 될 때까지 dfs 수행, 그 다음에는 2가 될 때까지 dfs 수행,.....goal 발견하면 중단하는 방식이다.

아래에서 특성을 보면 알 수 있듯이 두 탐색 알고리즘의 장점을 따온 방식이다.

 

Time complexity

Iterative deepening search에서 최악의 경우는 DFS,BFS와 동일하게 가장 오른쪽 아래의 leaf node에 Goal State가 있는 경우이다.

이때는 모든 노드를 탐색해야 하므로 시간 복잡도는 $O\left ( b^{m} \right ) $가 된다.

 

 

Space complexity

DFS의 방식을 차용하므로 Space Complexity는 $O\left ( bm \right ) $ 를 따른다.

 

Complete

BFS와 같이 무한 path에 빠질 일이 없으므로 complete하다.

 

Optimal

Cost를 고려하지 않은 방법으로 optimal하지 않다.

 

 

4. Uniform cost search

cost를 고려한 탐색 알고리즘으로 가장 cost가 낮은 노드부터 탐색하는 알고리즘이다. 우선순위 큐를 통해 구현이 되며 다익스트라 알고리즘을 생각하면 된다.

 

Time complexity

모든 경로의 cost가 같다면 uniform cost search는 최악의 상태이며 BFS와 같이 동작하게 된다.

최적의 해가 $C^{*}$의 값을 가지고 최소 간선 cost가 $\varepsilon $라면  $O\left(b^{\frac{C^*}{\epsilon}}\right)$ 이 시간 복잡도가 된다.

 

 

 

Space complexity

최악의 경우 BFS와 동일하므로 Space Complexity는 $O\left(b^{\frac{C^*}{\epsilon}}\right)$ 를 따른다.

 

Complete

finite한 cost를 같고 있고, 최소 간선의 비용이 양수라면 complete하다.

 

Optimal

가장 최소인 cost 값을 먼저 탐색하므로 optimal 하다.