Uniformed Search, BFS, UCS

Uninformed Search 

-문제의 정의 외에는 다른 정보가 주어지지 않는 검색 알고리즘이다.

- blind search 라고 불리기도 한다.

- 이 알고리즘은 현재 상태에서 목표 상태까지의 path cost 를 모른다.

- 따라서 오직 다음 후임자(successor) 를 expand 하고, 목표 상태인지 목표 상태가 아닌지를 구분만이 가능하다.

- 후임자(successor) 들을 expand한 순서는 매우 중요한 key 가 될 것이다.

 

- Uninformed Search 종류

• Breadth-First Search (너비 우선 탐색)
• Uniform-Cost Search (일정량 탐색)
• Depth-First Search (깊이 우선 탐색)
• Depth-Limited Search (깊이 제한 탐색)
• Iterative Deepening Search (점차적 깊이 제한 탐색)
• Bidrectional Search (양방향 탐색)

 

 

Breadth-First Search

- 루트 노드를 EXPAND -> 모든 후임자들 EXPAND -> 또 모든 후임자들 EXPAND -> .... 

- Frontier 에서 가장 얕고, 탐험되지 않은 노드를 먼저 확장하는 방법이다.

 

- Graph Search 에서 Expand 는 밑의 코드와 같다.

Graph Search 에서, explored 될 수 있는 노드는 frontier 에 있던 노드들이였다.

또한, 방문한 (expand) 한 노드들을 모두 explored set 에 저장해 두었다.

 

- BFS 에서는 frontier 를 FIFO queue 를 이용해서 구현하면 된다.

- Graph search 와 다른 점이 초기상태에 goal test를 하고, frontier 에 들어가기 전에 goal test 를 한다는 점이다.

graph search 에서는 frontier 에서 노드를 꺼낸후 goal test 를 하였다.

그러나 BFS 에서 모든 노드들은 frontier 에 들어가기 전에 goal test 하고, GOAL 을 찾을 때까지 반복한다.

 

 

- BFS 의 예를 보자.

1. 맨 처음 노드인 A 에 대해서 goal test 를 한다. 

그리고 frontier 에 A를 넣은 FIFO Queue 로 초기화한다.

또한 explored set 은 empty set으로 초기한다.

2. A를 frontier 에서 빼내고, expand 한다.

3. A의 자식노드들을 탐색하면서 Goal test 를 진행한다. 만약 Goal 이 아니라면 frontier 에 삽입한다.

4. 다시 반복문을 시작한다. frontier 에서 가장 얕은 노드인 B를 꺼내고 expand 한다.

그리고 B의 자식 노드들을 탐색하며 goal test 를 진행하고, frontier 에 삽입한다.

5. 다시 반복문을 시작한다. frontier 에서 가장 얕은 노드인 C를 꺼내고 expand 하며 계속해서 앞과 같이 진행한다.

 

 

 

Performance of the Breadth-First Search

- Complete : Branching factor b가 유한하다면 yes

- Optimal : path cost 가 node의 깊이에 따라 비례한다면 yes. (BFS 는 깊이와 비용이 항상 비례하는게 아니기 때문에)

- Time complexity : 총 생성된 노드는 b + b^2 + b^3 + ... + b^d = O(b^d) 이다. (Worst case)

depth 한 개 마다 최대 b개의 노드가 생겨나기 때문이다.

여기서 d는 가장 얕은 goal node 의 깊이이다.

 

만약 frontier 에 넣을 때 goal test 를 하지 않고, frontier 에서 빼낸 후 한다면 시간 복잡도는

가 될 것이다. 

 

- Space complexity : 생성된 모든 노드가 메모리에 올라왔을 때를 살펴보자.

Expored set : O(b^(d-1)) + frontier : O(b^d) = O(b^d) 가 될 것이다.

여기서 A,B,C는 explored set, D,E,F,G 는 frontier 이다.

 

 

 

Exponentiatl Time and Space Complexity

- BFS 의 치명적인 단점은 바로 메모리 요구가 아주 거대하다는 것이다. 

Blind Search 는 Exponential (지수적인) 문제를 해결할 수 없다는 것이다.

따라서 메모리 문제로 실제 사용이 어렵다.

 

 

 

Uniform-Cost Search

- BFS 에서는 depth 와 path cost 가 비례해야지만 최상이였다. 따라서 그 문제를 해결하기 위해 사용하는 알고리즘이다.

- FIFO queue 가 아닌 priority queue 를 frontier 로 사용함으로서, path cost 가 낮은 노드를 먼저 EXPAND 한다.

- 현재 Frontier 에서 확장되지 않은 노드 중에서 가장 비용이 적은 노드부터 확장

 

- BFS 와 다른 두 가지 점이 있다.

• Goal test 를 frontier 에 넣을 때가 아니라, expand 할 때 한다는 것이다. 
• frontier 에 있는 노드가 교체될 수 있다. 

 

- 위 코드에서와 같이, frontier 에서 꺼낸 후 expand 하면서 Goal Test 를 한다.

- 또한, fronter 에 이미 있는 노드보다 현재 자식 노드의 cost 가 더 작다면 교체될 수 있다.

 

 

- 예시를 보자.

 

1. Sibiu는 expand, Fagaras 와 Rimmicu 는 frontier 에 존재한다.

F(80) 와 R(99) 중 비용이 작은 R 을 frontier 에서 꺼내고, goal test 후, expand 한다. -> 현재 frontier : [Fagaras(99)]

2. R 의 자식인 Pitesti 를 frontier 에 넣는다. -> 현재 fronteir : [Fagaras(99), Pitesti(177)]

3. frontier 에서 Fagaras 를 꺼내고, goal test 후 expand 한다. 또한, 자식인 Bucharest 를 frontier 에 넣는다.

-> 현재 fronteir : [Pitesti(177), Bucharest(310)]

4. frontier 에서 Pitesti 를 꺼내고, goal test 후 expand 한다. 또한, 자식인 Burcharest 이 이미 frontier 에 있지만 들어있는 비용보다 더 작기 때문에 교체해준다. -> 현재 fronteir : [Bucharest(278)]

5. Bucharest 를 꺼내고 goal test 후 종료한다.

 

-> 위 과정에서 볼 수 있듯이, Burcharest 는 3번에서 이미 frontier 에 들어갔지만 알고리즘이 종료되지 않았다.

만약 frontier 에 넣기 전에 goal test 를 했더라면 310 의 비용으로 알고리즘이 끝났겠지만,

Uniform-Cost 는 frontier 에서 나올 때 goal test 를 하기 때문에 310이 아닌 278 의 비용으로 종료할 수 있었다.

 

 

Performance of Uniform-Cost Search

- Completeness : 모든 step의 cost 가 양수라면 yes, 0이나 음수라면 complete 하지 않다.

- Optimality : yes (항상 경로 비용이 제일 작은 것을 선택하기 때문에)

- Time and space complexity

C 는 최적 해의 cost이고, e는 cost 가 가장 적은 action 의 cost 이다.

e = 1, c = d 라면 , O(b^(1+d)) -> O(b^d) 이다. // 여기서 d+1 인 이유는 frontier 에서 나올 때 goal test 를 하기 때문.