인공지능 탐색 알고리즘 2-Uninformed Search

탐색알고리즘은 크게 2종류가 있습니다.

Uninformed Search와 Informed Search

먼저 알아볼 알고리즘은 Uninformed Search입니다.

f(n)=g(n)+h(n) 일때, h(n)=0인 탐색 알고리즘입니다.

Uninformed Search는 Blind Search라고도 합니다.

현재상태에서 goal까지 가는 스텝이나 경로비용(h(n))에 대한 정보가 없이,

이미 지나온 비용(g(n))에 대한 것으로만 평가하는 탐색 알고리즘입니다.

1.Breadth-first Search

이름에서 알수 있듯이 깊이가 얕은 것부터 전개해 나가는 탐색 알고리즘입니다.

Frontier는 FIFO queue로 구현되는데, 위 그림에서 아래 파란색이 현재 상태의 queue입니다.

처음 A를 전개하기전엔 queue에 A만 들어가 있는 상태이고, 

A를 전개하면 A는 queue에서 빠져나오고 B, C가 순서대로 들어갑니다.

B를 전개하면 B가 빠져나오고, D와 E가 C뒤로 들어갑니다.

이런식으로 하다보면 frontier의 queue 사이즈가 커지게 됩니다.

마침내 최적의 해는 찾지만 메모리 요구량이 많고, 시간이 오래걸리는 단점이 존재합니다.

Depth의 수에 따른 시간과 메모리 요구량입니다.

2. Uniform-cost Search

앞의 Breadth-first Search가 얕은 노드부터 전개하였다면, Uniform-cost Search는 

frontier중 비용이 가장 적은 노드부터 전개합니다.

S부터 G까지 가는 경로중 가장 저비용으로 가는 길을 찾는다고 할때, 노드간 숫자는 비용입니다.

S를 전개하면 A, B, C가 나타납니다.

이중 breadth first search처럼 A부터 전개하는게 아닌 비용을 보고 전개합니다.

A의 비용이 1, B의 비용이 5, C의 비용이 15이니 A부터 전개합니다.

A를 전개하니 G가 나왔습니다. 

G가 나왔지만, S-A-G까지의 COST인 11보다 적은 COST가 남아 있으니 그다음 낮은 B를 전개합니다.

B를 전개하니 G가 나왔습니다.

S-B-G의 코스트가 10이고 이보다 낮은 COST가 없으므로 탐색을 종료합니다.

그리고 최적의 해는 S-B-G가 됩니다.

Uniform-cost Search도 해의 위치에 따라 시간과 메모리 복잡도가 올라가는 것은 마찬가지입니다.

3. Depth-first Search

Depth-first Search는 Breadth first Search와 비슷하나 frontier를 LIFO queue(Stack)로 구현했습니다.

그리고 Tree-Search 기반이지만 frontier에 조상과 중복되는 노드가 나타나면 버림으로써, 

무한루프를 피했습니다.

A를 전개하면 B, C가 나오는데 A는 queue에서 빠지고 B, C가 들어갑니다.

B를 전개하면 D, E가 나오고, B가 빠져나오는데 그자리에 D, E가 들어갑니다.

오른쪽 파란색이 각 스텝별 queue(stack)의 상태입니다.

차례대로 전개하면 위의 그림과 같이 나오게 됩니다.

단점으로는 메모리의 요구량이 커집니다.

그리고 탐색 공간이 많아지게 되면 최적해를 찾는데 시간도 많이 걸리게 됩니다.

4. Depth-limited Search

Depth-first Search가 Depth가 커지게 되면 탐색시간이 오래걸리는 걸 개량한 알고리즘입니다.

Depth를 일정한 값으로 제한해 그 값만큼만 탐색을 하는 알고리즘입니다.

다만 Depth의 최적의 값을 찾기가 어려운 단점이 있습니다.

5. Iterative Deepening Search

Depth의 limit을 0부터 차례대로 증가시키며 Depth-limited Search를 하는 방식입니다.

처음은 limit=0으로 전개

다음은 limit=1로 전개하여 goal을 찾습니다.

이런식으로 계속해서 증가시키며 goal을 찾습니다.

limit을 증가시켜 다시 중복해서 전개할때 시간이 오래 걸릴꺼 같지만 노드가 엄청날때를 가정하면,

그리 오래걸리지도 않고 최적해를 찾을 수 있습니다.

F에서 O까지 가는 경로를 찾을때의 예입니다.

Limit=3일때 찾았습니다.

6. Bidirectional Search

초기상태에서 goal까지 탐색하고, goal부터 초기상태로 역방향으로 동시에 탐색하는 방법입니다.

이 방법역시 역방향 탐색이 어려울 수 있어 단점이 많습니다.

마지막으로 각 탐색알고리즘들에 대한 비교입니다.