CS188 Introduction to Artificial Intelligence – (1-2) Search

Posted on by

이 문서는 Berkely University의 CS188 Introduction to Artificial Intelligence의 강의자료를 번역 및 정리한 것입니다. 본 자료는 오류 또는 오역을 포함할 수 있으며 보다 정확한 내용은 원문 출처를 참조하시기 바랍니다.

Depth First Search

DFS는 탐색 전략 중 확장을 위한 노드를 선택할 때, Fringe상에서 시작 노드로부터 가장 깊은 위치에 존재하는 노드를 선택한다.

Fringe에서 가장 깊은 노드를 꺼내고 그 자식 노드들을 추가하는 과정을 반복한다. 이 과정에서 현재 꺼낸 노드의 자식 노드들은 가장 깊은 노드가 된다. 자식 노드들의 깊이는 현재 꺼낸 노드보다 1크다. DFS를 구현하기 위해서는 가장 마지막에 추가된 원소를 맨 먼저 꺼내는 last-in, first-out (LIFO) 구조가 필요하므로 스택(Stack)을 사용한다.

Completeness

Depth First Search는 completeness를 만족시키지 않는다. 만약 상태 공간 그래프 상에 사이클이 존재한다면, 탐색 트리는 무한한 깊이를 가지게 될 것이다.
즉, DFS는 가장 깊은 노드를 무한한 크기의 탐색 트리에서 찾으려고 하므로, 탐색은 종료될 수 없다.

Optimality

DFS가 Solution을 찾는다고 하더라도 위 그래프처럼 솔루션 중에서 가장 왼쪽에 있는 것을 리턴한다. Path Cost(경로 비용)이 고려되지 않았으므로 Optimal한 Solution을 항상 보장하지 않는다.

Time Complexity

최악의 경우 DFS는 전체 탐색 트리를 탐색하기에 O(b^m)이다.

Space Complexity

최악의 경우 DFS는 m개의 depth에 대해 각각 b개의 노드를 저장한다. b개의 children이 fringe에 들어간 후에, 그 중 하나의 child만이 탐색되어 다시 b개의 children을 추가하고 다시 그 children 중 하나의 child를 탐색하는 방식으로 알고리즘이 수행되므로, 각 depth에서 동시에 하나의 child만 탐색될 수 있다. 따라서 공간 복잡도는 O(bm)이다.

Breadth First Search

BFS는 시작 노드에서 가장 얕은 노드를 확장을 위해 우선적으로 선택하는 전략이다.

가장 얕은 순서대로 노드를 방문하기 위해선, Fringe에 노드를 삽입한 순서대로 방문해야한다. 이를 위해선 FIFO 구조를 갖는 큐(Queue)를 자료구조로 택해야한다.

Completeness

만약 Solution이 존재한다면, 그 중에서 가장 얕은 노드의 깊이 s는 유한할 것이다. 따라서 BFS는 반드시 그 깊이를 탐색할 것이다. 따라서 BFS는 Complete하다.

Optimality

일반적으로 BFS는 fringe의 어떤 노드를 교체할지 결정할 때 cost를 고려하지 않기 때문에 optimal하지 않다. BFS가 optimal하다고 보증되는 특수한 경우는 모든 edge의 cost가 동등할 때이다. 이 경우 BFS는 uniform cost search의 특별한 사례가 된다.

Time Complexity

각 depth의 노드를 모두 탐색한 후에 다음 depth를 탐색하므로 1 + b + b^2 + … + b^s 노드를 최악의 경우에 탐색하게 된다. 따라서 시간 복잡도는 O(b^s)가 된다.

Space Complexity

최악의 경우 Fringe는 가장 얕은 Solution의 depth에 해당하는 모든 노드를 포함한다. 따라서 O(b^s) 노드가 해당 깊이에 있다.

Uniform Cost Search

Uniform Cost Search는 확장을 위해 Fringe에서 가장 적은 Cost를 갖는 노드를 선택하는 탐색 전략이다.

UCS를 위한 Fringe를 나타내기 위해서 heap 기반의 우선 순위 큐(Priority Queue)를 사용한다. 큐에 들어간 노드 v에 대한 가중치는 시작 노드로부터 v까지 향하는 경로 비용(Path Cost) 또는 backward cost다. 우선 순위 큐는 큐에서 최소 노드를 꺼내고 그 자식노드를 추가할 때, 경로 비용을 기준으로 한 정렬 순서가 유지되도록 설계되어 있다.

Completeness

만약 목표 상태가 존재한다면, 반드시 어떤 유한한 길이의 최소 경로를 갖게된다. 길이 순으로 탐방하는 UCS는 반드시 그 길이에 도달하며, Solution을 찾는다.

Optimality

UCS는 모든 edge cost가 음수가 아닐 때 optimal이다. 알고리즘에 따르면 노드는 경로 비용의 오름차순으로 탐색되므로, 목표 상태로의 최소 비용 경로를 찾아낼 수 있다는 것을 보증할 수 있다. UCS에 사용된 전략은 Dijkstra 알고리즘과 동일하다. UCS와 Dijkstra의 차이는 Dijkstra는 초기 상태에서 모든 상태까지의 최단 경로를 찾는 반면, UCS는 목표 상태까지의 최단 경로만을 찾고 종료된다는 점이다. 음수의 가중치를 갖는 그래프는 길이가 감소하는 경로를 만들 수 있다. 이 때 optimality가 성립하지 않을 수 있다.

Time Complexity

Optimal한 경로 비용을 C^*라고 정의하자. 상태 공간 그래프 상에서 두 노드들 간의 최소 비용을 \epsilon 이라고 하자. 그렇다면 우리는 대강 C^* / \epsilon 개의 깊이를 탐색할 것이며 시간 복잡도는 대략 O(b^{ C^* / \epsilon })를 가진다.

Space Complexitiy

대략적으로 Fringe는 최소 비용 solution의 깊이의 모든 노드들을 가질 것이다. 따라서 UCS의 공간 복잡도는 O(b^{ C^* / \epsilon }) 이다.

기본적으로 위 세 전략은 동일하며, 확장 전략에서만 차이를 보인다. 이들 모두 동일한 pseudocode를 가진다.

2019. 12. 9. CS188 Introduction to Artificial Intelligence – (1-2) Search