Uninformed Search란
여러가지 문제를 해결하기 위한 탐색 기법 중 하나로 사전정보를 갖지 않고 탐색하는 알고리즘 기법이다. Uninformed Search는 Blind search라고 불리며 Informed Search랑 비교된다.
Blind Search라고 불리는 이유는 현재 node에서 Goal node까지의 거리(heuristic value)를 알지 못하기 때문에 Blind Search라고 불린다. 만약 현재 위치에서 Goal node까지의 거리 혹은 heuristic value를 안다면 Informed search라고 한다.
Uninformed Search에는 다음과 같은 알고리즘이 있다.
- Breadth-first Search
- Depth-first Search
- Iterative deepening depth-first Search
- Uniform cost Search
위의 알고리즘을 네가지 관점에서 살펴볼 것이다.
- Completeness : solution이 존재한다면, 항상 solution을 찾아주는것인가?
- Time complexity : 탐색한 노드의 수. 즉 탐색하는데 얼마나 걸리는가. (worst case)
- Space complexity : 메모리에 저장된 node의 최대 수. 즉 메모리를 얼마나 요구하는가? (worst case)
- Optimality( Quality of solution ) : 항상 최소비용(least-cost)으로 solution을 찾아주는가? (여기서 least-cost는 min depth를 의미하기도 한다)
Tree-based Search
탐색할 때는 기본적으로 Tree 구조를 가지고 많이 탐색하게 된다.
Tree-based Search의 기본 아이디어는 이미 탐색된 state(여기서는 현재 node라고 할 수 있다)에서 갈 수 있는 state로 움직이면서 공간을 탐색하는 것이다 (이 기본 아이디어를 expanding state 라고 부름). 여기서 state는 node와 같은 말로 쓰인다.
그리고 매 state에 도달할때 마다 goal state인지 확인해주어야한다.
다음은 8 puzzle problem을 tree 형태로 나타낸것이다. 다음과 같이 확장(expanding state)해나가면 Goal state에 도달 할 수 있다.
Search Strategies
Search Strategy는 node를 확장하는 순서를 선택하는것에 따라 달라질 수 있다. 예를 들어 bfs, dfs 알고리즘은 똑같이 탐색하지만 node 탐색 순서가 다르다.
따라서 우리는 위에서 말한 네가지 평가기준을 가지고 탐색 알고리즘들을 평가할 것이고 특히 Time complexity와 Space Complexity는 다음을 이용해 수식으로 나타낼 것이다.
- b : search tree에서 branching factor의 최대 값. 예를 들어, 루트노드에서 갈 수 있는 다음 노드가 3개라면 b = 3이 된다.
- d : 최소 비용으로 해를 찾았을 떄의 깊이(depth). 예를 들어 루트에서부터 Goal 노드까지의 깊이가 4라면 d = 4가 된다.
- m : 루트 노드에서 들어갈 수 있는 최대 깊이. d와 구분을 잘 해야한다. 무한도 가능하다
Breadth-first Search(BFS)
BFS 기본원리 : 가장 가까운 unexpanded node(아직 방문하지 않은 node를 뜻함)를 먼저 방문하는 것이다.
Fringe는 queue안에서 탐색되도록 기다리는 node를 의미하며 OPEN이라고도 불린다.
Fringe에 대한 자세한 설명은 다음과 같다.
- A fringe is just a term we use for the data structure we are using to store the nodes on the frontier of our traversal's discovery process (the next nodes it is waiting to look at). For BFS, we use a queue for our fringe.
BFS의 구현 : BFS에서 fringe는 FIFO queue이고 현재 node에서 탐색할 다음 node(new successor라고 함)는 queue의 마지막으로 insert된다.
tree뿐만 아니라 graph에서 BFS를 사용할 수 있는데 다음 두가지를 주의하면 된다. 추가적으로 현재 node에서 인접한 node를 모두 queue에 넣는다고 가정할 때 다음 조건을 주의한다.
- 이미 방문한(expand) node는 queue에 다시 넣지 않는다.
- 이미 방문되어진 node가 queue에서 나와 선택되었다면 실행하지 않고 다음 node를 수행한다.
BFS 속성
- Complete : Yes
- Optimal : Yes -> level order로 가까운 순서대로 찾음.
- Time complexity : O(b^d)
- Space complexity : O(b^d)
exponential하게 space complexity가 증가하는 것이 단점.
BFS의 Time Complexity
worst case일때,
depth d이고 Right Hand Side(RHS)에 1개의 goal node가 leaf에 있을 때 BFS는 다음과 같이 탐색할 노드가 생성되며 Time complexity는 다음과 같다.
= b + b^2 + .... + b^(d+1) - b
= O( b^( d + 1 ) )= O( b^d )
BFS의 Space Complexity
worst case 일때, 얼마나 많은 노드들이 queue안에 있는가를 측정해주면 된다. depth가 d일때 b^(d+1) 만큼의 탐색되지 않은 노드들이 queue안에 있다.
= b^(d+1) - b (Goal node일때만 branching factor: b가 queue에 들어가지 않기 때문에 다음과 같은식 만들어짐)
= O( b^( d + 1 ) )
다음은 b = 10, 초당 10000개의 노드를 처리할 수 있는 speed, node size는 node당 1kbyte라고 가정했을 때의 표이다.
depth가 증가 함으로써 time과 memory가 지수적으로 증가한다.
Depth-first Search(DFS)
DFS 기본원리 : 가장 깊은 unexpanded node(아직 방문하지 않은 node를 뜻함)를 방문하는 것이다.
DFS의 구현 : DFS에서 fringe는 LIFO stack이고 현재 node에서 탐색할 다음 node(new successor라고 함)는 stack의 처음으로 push된다.
tree뿐만 아니라 graph에서 DFS를 사용할 수 있는데 다음 두가지를 주의하면 된다. 추가적으로 현재 node에서 인접한 node를 모두 stack에 넣는다고 가정한다.
- 이미 방문한(expand) node는 stack에 다시 넣지 않는다.
- 이미 방문되어진 node가 stack에서 pop되어 선택되었다면 실행하지 않고 다음 node를 수행한다.
DFS 속성
- Complete : No (depth가 무한대이면 무한 깊이로 들어가기 때문에 solution을 찾을 수 없음. )
- Optimal : No (최소 비용 혹은 최소 깊이로 찾아야 하는데 깊이 우선탐색이므로 멀리있는것이 찾아질수있음.)
- Time complexity : O(b^d) (bfs랑 비슷하거나 조금 안좋다)
- Space complexity : O( b * d )
exponential하게 space complexity가 증가하는 것이 단점.
DFS의 Time Complexity
worst case일때,
depth d이고 Right Hand Side(RHS)에 1개의 goal node가 leaf에 있을 때
DFS는 다음과 같이 탐색할 노드가 생성되며 Time complexity는 다음과 같다.
= O( b^m )
DFS의 Space Complexity
worst case 일때, 얼마나 많은 노드들이 stack안에 있는가를 측정해주면 된다. depth가 d, branching factor가 b일때,
stack안에 있는 노드들이 다음과 같이 있다.
Total = b + (m-1) * (b-1) = O( b * m )
위의 그림에서 마지막 leaf node b개는 stack에 있고 그 위에 node들은 한개만 stack에 있는것으로 보인다.
즉 m-1개의 깊이에서 b-1개의 node들이 stack에 존재한다. 추가적으로 마지막 leaf node b개만큼 더해주면 위의 식을 유도할 수 잇다.
다음은 b = 10, m = 12, 초당 10000개의 노드를 처리할 수 있는 speed, node size는 node당 1kbyte라고 가정했을 때의 표이다.
여기서 주목해야할 것은 memory 복잡도는 linear하기 때문에 memory 소모가 적다는 것이다.
DFS와 BFS 비교
시간복잡도
worst case일때, BFS는 일반적으로 DFS보다 좋다. (DFS는 m의 크기가 무한까지 커질 수 있기 때문에)
그러나 goal이 많고 loop가 없고, infinite 경로가 없다면 DFS가 평균적으로 좋을 수 도 있다.
memory
BFS가 memory 측면에서 더 나쁘다.
DFS는 linear 하지만 BFS는 탐색공간 전체를 저장해놓는다.
일반적으로
- goal의 depth가 깊이 있지않고 infinite 경로가 존재하고 loop가 존재하고 탐색공간이 적다면 BFS가 더 좋다.
- goal이 많고 infinite 경로가 존재하지 않고 loop가 존재하지 않고 DFS가 더 좋다.
- DFS는 메모리측면에서 훨씬 낫다.
DFS with a depth-limit L
기본적인 DFS와 같이 동작하지만 depth를 L로 제한해서 그 밑으로는 탐색하지 못하도록 하는 알고리즘이다.
해를 같지 않는 무한경로의 문제도 해결할 수 있다. 하지만 goal이 depth limit L아래로 있으면 해를 찾을 수 없다.
하지만 이것만 가지고는 Goal이 어느 깊이에 있는지 모르기 때문에 IDS 방식으로 많이 사용한다.
Iterative Deepening Search(IDS)
IDS는 depth limit을 증가시키면서 DFS를 여러번 실행하는 방법이다.
알고리즘의 동작과정은 다음과 같다.
- L = 1일 때, DFS로 탐색
- 만약 Goal이 없다면 depth limit L을 증가시킨다.
- 만약 Goal을 찾았다면 Goal을 return하고 멈춘다.
- Goal이 나올때 까지 이 과정을 반복해서 수행한다.
IDS 속성
b는 branching factor 이고 d는 solution depth이다.
- Complete : Yes
- Optimal : Yes
- Time complexity : O(b^d) = b + (b + b^2) + .... (b +... b^d) => L의 값에 따라 반복적으로 node가 만들어져서 Time complexity에 영향을 준다.
- Space complexity : O( b * d )
space complexity가 linear하다. BFS처럼 memory가 exponential하지 않음.
BFS의 장점처럼 optimal 하게 Goal을 찾음(깊이를 조금씩 늘려가기 때문에)
Goal이 유한거리에 존재한다면 유효하게 찾음(1, 2, 3, ... L과 같이 limit을 만들어 찾기 때문에)
IDS의 단점 : Limit을 늘릴때마다 찾은것을 중복해서 찾기때문에 낭비가 있을 수 있다.
정리하자면 IDS는 DFS의 적은 메모리 사용과 BFS의 solution을 찾아주는 것을 보장한다.
IDS의 실용성
IDS는 L이 증가하면서 중복핵서 같은 node를 탐색하기 떄문에 낭비적이라는 생각이 들 수 있다.
따라서 IDS와 BFS를 비교해보려고 한다.
b = 10, d = 5라고 가정하고 만들어지는 노드의 개수를 계산해본다.
IDS에서 생성되는 노드의 개수 : db + (d-1) * (b^2) + .... b^d = 123,450 (d를 앞에 곱해주는 것은 그만큼 반복해서 node가 만들어진다는 뜻이다)
BFS에서 생성되는 노드의 개수 : b + b^2 + ......b^d = 111,1110
IDS는 BFS의 개수보다 약 b/(b-1)배 만큼 큰 것을 알 수 있다.
대부분의 시간은 depth d에서 소모되기 때문에 두 알고리즘은 같은 time complexity를 가진다.
Uniform Cost Search
이 알고리즘의 optimality는 가장 적은 비용을 찾는 것이다.
동작방식
- start state S에서 node n까지의 비용을 g(n) 이라고 하자.
- fringe 안에서 minimum cost g(n)이 되도록 node를 expand 하고 cost가 동일하다면 BFS와 비슷하게 동작할 것이다.
edge의 cost가 1이면 BFS와 같다.
Uniform Cost Search는 Min Heap을 사용한다.
Optimality of Uniform Cost Search
Uniform Cost Search는 optimality를 보장하는가?
결론부터 말하자면 BFS의 일반화이기 때문에 보장한다.
증명은 다음과 같다.
Completeness 증명
모든 edge의 비용이 0보다 크고 유한한 branching factor를 가정한다. 총 경로 비용은 goal state의 경로 비용과 같아지기 전에 유한한 수의 확장(expansion)이 필요하다. 따라서 유한한 step을 거쳐 goal에 도달한다.
Optimality 증명
Uniform Cost Search는 optimal 하지 않다고 가정한다.
그러면 우리가 찾은 goal state 경로보다 더 비용이 적은 경로가 존재한다는 말이된다.
그러나 UCS는 정의에 의해 가장 비용이 적은 노드부터 expand 되기 때문에 위의 말은 불가능하다.
따라서 모순이므로 UCS는 Optimal하다
Uniform Cost의 Complexity
C*는 optimal solution의 비용이라 하자.
매 step의 비용(e)은 0보다 크다.
worst case 일 때, space complexity는 다음과 같다.
O(b^ [1+ floor( C* / e ) ])
Summary
탐색공간은 state와 operator로 구성되어 있다.(즉 graph 형태로 탐색한다) 아마 operator는 edge를 뜻하는 말인것 같다.
uninformed search의 전략은 다음과 같다.
- breadth-first
- depth-first
- iterative deepening
- Uniform cost search
위의 알고리즘 사이에는 장단점이 존재하며 탐색문제에 따라 best 알고리즘이 다르다.