• 다음 내용은 [CS-188] Introduction to Aritificial Intelligence, UC Berkeley, Fall 2018의 Readings-Note1을 정리하였음을 밝힙니다.
• 스스로 이해하기에 영문 용어가 이해하기 직관적이면 그대로 사용했습니다.

Uninformed Search

path finding 문제를 풀려면 탐색 트리에서 만들어진 partial plan의 fringe(expand를 기다리고 있는 노드 집합)를 계속 지니고 있어야 한다. 특정 straegy로 택한 노드를 제거하고 그 노드를 fringe 상에서 자식 노드 모두로 대체하면서 fringe를 계속해서 expand할 수 있다. 이 과정을 통해 길이 n의 경로가 n+1 길이로 대체된다. fringe에서 목적 상태를 없앨 때까지 이 과정은 반복된다.

탐색 트리 내 goal state가 어디 있는지 알 수 없다는 점에서 위 탐색 방법은 uninformed search라 불리고, 깊이 우선 탐색, 너비 우선 탐색, 균일 비용 탐색이 존재한다.

1. DFS

깊이 우선 탐색은 언제나 시작 노드에서 가장 깊은 fringe를 고르는 탐색 알고리즘이다. 깊이가 가장 깊은 노드를 없애고 그 노드를 그 자식 노드로 대체하는 방식을 통해 깊이가 이전보다 1씩 증가한다.
DFS를 통해 언제나 가장 최근에서 더해진 대상에게 가장 높은 우선순위를 줄 수 있다. 즉 LIFO의 스택이 적합한 DFS 구현 자료구조이다.

• Completeness: 상태 공간 그래프 내 사이클이 존재하면 깊이가 무한한 탐색을 계속 해야 하기 때문에 complete하지 않을 수 있다.
• Optimality: DFS는 "가장 왼쪽"에 존재하는 경로를 반환하기 때문에 optimal하지 않다.
• Time Complexity: 모든 탐색 트리를 찾을 때 최대 깊이 m 트리에서 실행 시간은 $O(b^m)$
• Space Complexity: 깊이 m 레벨에서 b개의 노드를 가지고 있기 때문에 $O(bm)$

2. BFS

너비 우선 탐색은 탐색 트리에서 가장 '얕은' fringe를 고르는 탐색 알고리즘이다. 한 층 더 깊은 레벨에 존재하는 노드를 탐색하기 전, 지금 레벨에 존재하는 모든 노드를 살펴봐야 한다. 즉 FIFO의 큐가 적합한 BFS 구현 자료구조이다.

• Completeness: solution이 존재할 때 가장 얕은 단계의 노드 s 깊이는 유한하므로 compelte
• Optimality: 모든 탐색 비용이 동일할 때 optimal. 일반적으로 fringe 상에서 노드를 교체할 때 비용을 고려하지 않기 때문에 not optimal
• Time Complexity: solution이 최대 깊이 s에 존재할 때, 깊이 s까지 모든 노드를 탐색해야 한다. 따라서 $1+b+b^2+b^3...+b^s=O(b^s)$
• Space Complexity: fringe가 가장 얕은 solution 레벨 상 모든 노드를 포함하므로 O(b^s)

BFS는 대개 path finding 문제에서 DFS보다 월등히 뛰어난 성능을 보인다. 반면 문제 설정이 identification으로 달라지면 DFS가 더 뛰어나다.

3. UCS

균일 비용 탐색은 가장 낮은 비용의 경로를 반환하는 탐색 알고리즘이다. 경로 내 존재하는 모든 successor function의 비용을 더한 값을 비교해야 하기 때문에 우선순위 큐가 적절한 UCS 구현 자료구조이다.

• Completeness: goal state가 존재한다면 UCS는 최단 경로를 반환하므로 complete
• Optimality: 모든 간선 비용이 음수가 아닐 때 optimal하다.
• Time Complexity: 최적 경로 비용을 $C^*$, 상태 공간 그래프 상 두 노드 사이에서의 최소 비용을 $ε$라 할 때 깊이 1부터 깊이 $C^* / ε$까지 존재하는 노드를 탐색해야 한다. 따라서 branching factor를 b라 하면 시간 복잡도는 $O(b^{C^* / ε})$
• Space Complexity: solution 레벨의 모든 노드를 fringe가 가지고 있어야 하기 때문에 $O(b^{C^* / ε})$

BFS는 UCS 중 모든 간선 비용이 동일한 특별한 경우이다. 또한 optimal path를 반환할 때 사용하는 탐색 알고리즘은 다익스트라 알고리즘과 동일하다('모든' 노드에서의 최단 경로가 아니라 '시작' 노드에서의 최단 경로를 구하는 것이 차이).