[인공지능] Uninformed Search Strategies

Solving Problems by Searching

---

frontier(프론티어) : 확장되어지기를 기다리는 leaf node 들의 집합을 일컫는 말, open list 라고도 불린다. 

Tree-Search 방식(가장 일반적인 방식)을 이용해보자.

위의 그림의 경우 (b) 의 기준에서 현재 Arad 에 있고 이 상태에서의 frontier 는 Arad 의 child nodes(3개)가 된다.

(c) 의 경우 Sibiu 가 선택되었으므로 frontier에서 Sibiu 를 제거하고 그 child nodes(4개) 가 frontier 로 추가 된다.

frontier 는 Timisoara, Zerind, Arad, Fagaras, Oradea, Rimnicu Vilcea 로 총 6개가 된다.

만약 다음 state 로 Arad 가 선택된다면 무한 루프가 발생할 수 있게 된다.

이를 예방하기 위해 Graph-Search 를 이용하면 된다.

Graph-Search 방식(Tree-search 방식 + explored set 도입)

이미 탐험했던 노드들을 explored set(aka closed list)을 통해 확인함으로서 중복을 피하는 방식이다.  위의 예처럼 Arad 가 다시 child로 나온다면 explored set 이나 frontier 을 확인해보고 중복이 되면 frontier 에 추가하지 않는다.이 방식은 최대 각 state 의 one copy 정도를 포함한다.

이러한 경로를 찾는 문제들에는 평가 기준이 있다.

Completeness : solution 경로를 찾을 수 있는가

Optimality : path cost 가 가장 낮은 경로 찾는 것을 보장해주는가

Time complexity : node 를 얼마나 생성하는지

Space complexity :  메모리에 얼만큼의 노드가 저장되는지

그래프에서는 보통 함축적으로 표현되어서 복잡도를 아래와 같은 요소들로 표현한다.

b : branch factor or maximum number of successors of any node

d : depth of the shallowest goal node

m : maximum length of any path in the state space  (무한이 될 때가 많다.)

BFS 알고리즘

frontier 가 FIFO queue 형태로 되어있다. 

공간은  Graph-search 로 해도 Tree-search 의 공간복잡도의 2배보다는 작기 때문에(frontier 수>=2*explored set 수) Graph-search 방식을 쓴다.  

Tree-Search 방식을 사용하면 비효율적이게 된다.(탐색 시간 길어짐)

 1. 새로운 node를 탐색하고 2. frontier 에  넣는다.(generated)   2번 과정이 수행되기 직전에 goal-test 를 수행한다는 것이 특징이다. 

평가 : Complete and optimal(모든 node의 경로의 cost 가 같은 경우에만 optimal)

시간복잡도

b : branching factor

d : solution path length

 O(b^d) 위에서 말했던 것 처럼 새로운 node 가 frontier 에 들어가기 직전에 goal-test를 했을 때의 시간복잡도 이고

만약 frontier에 들어간 후 goal-test를 수행하면 시간이 더 소요되기 때문에  O(b^(d+1)) 이라는 시간복잡도가 나오게 된다.

Uniform-cost Search

frontier 가 Priority queue 형태로 되어있다 (cost가 적은것이 queue 의 맨 앞에 오도록)

이미 확장 된 node 라 해도 비용이 더 적은 경로가 나올 수 있기 때문에 같은 node 를 다른 위치에서 확장시킬 수 있고 비용이 더 작은 경로에 대해서만 확장한다. -->Modified Graph-search (BFS 보다 한 단계 더 수행한다.)

비용이 더 적게 나온 중복된 node 만 확장시키고 frontier 에 넣는다.

Tree-search 로 수행하게 되면 비효율적이다,

평가 : 모든 경로에서의 cost가 0보다 크면 Complete and optimal 하다.

시간복잡도

모든 cost가 동일하다면 O(b^(d+1)) 이 된다.

DFS 알고리즘

frontier 가 stack 이다.

Tree-Search 기반으로 동작하는데 추가적인 기능이 있다.(Modified Tree-search)

--> 새로운 node가 선조 node 와 같다면 그 즉시 버린다.(무한루프를 피하기 위해, but redundant path 는 발생) 

메모리 요구량은 보통이다.(하나의 탐색 경로가 끝나면 그에 해당하는 explored set 공간 초기화 해도 상관없을 것 같다?)

Graph-Search 기반으로 동작된다면 의미없는 explored set 의 지수적 메모리 요구량 때문에 비효율적이다. 

평가:

공간복잡도 : O(bm)   (b : branching factor, m : maximum depth)

시간복잡도 : O(b^m)

유한한 공간에서는 Complete 는 성립되지만 불필요한 경로때문에 Optimal 하지는 않다.(최적 경로를 찾기 전에 goal state 를 만날 수 있으므로)

Depth-limited Search

DFS 와 같은 방식(Tree-Search 기반)이지만 depth-limit 가 존재한다.

Iterative Deepening Search

Depth-limited Search 가 depth-limit 을 특정값으로 고정한다면 Iterative Deepening Search 은 depth-limit을 점차적으로 증가시키는 방식이다.

optimal and complete 하다.

메모리 요구량이 적다.

시간복잡도 : O(b^d)

공간복잡도 : O(bd)    d : depth limit

Bidirectional Search

start node 와 goal node 에서 node 를 확장하여 경로를 구축하는 방식이다. 시간복잡도는 O(b^(d/2)) 이다.

아래의 두 사진은 위에서 다뤘던 Search 방식들을 비교, 정리 해 놓은 것이다.

**이슈사항 : Depth-limited search 에서는 strict Tree search vs modified Tree Search 중 어떤 것이 더 효율적인가?

depth 가 제한되어 있기 때문에 무한루프를 피할 수 있어서 일반적인 Tree search 를 사용하는 것이 더 효율적일 것이다.