Iterative Deepening Depth-First Search, Bidirectional Search

Iterative Deepening Depth-First Search

- Depth limit 를 점진적으로 늘려가나는 DLS 방식으로, goal state 를 찾을 때까지 반복해나간다.

- Space complexity : Depth-first search 와 같이 O(bd) 이다.

- Completeness & Optimal : Yes, Breadth-first search 처럼 branching factor b가 유한하다면 complete 하고, path cost 화 depth 가 비례하다면 optimal 하다.

 

- 예시

- Goal 을 찾을 때까지 depth limit 를 늘려가는 과정이다.

 

 

 

Efficiency of IDS

- 같은 노드가 여러번 생성되어 성능이 좋지 않을 것으로 보이지만,

대부분의 노드들은 bottom level 에 존재하기 때문에 중복의 수가 크지 않다.

bottom level 의 leaf 노드들은 한 번만 생성되기 때문이다.

IDS 의 Time complexity 는 Breadth-First Search 와 같다.

 

 

Time Complexity of IDS

-생성된 노드의 수 N(IDS) : (d)b + (d-1)b^2 + (d-2)b^3 + ... + (1)b^d -> O(b^d)

- b = 10, d = 5 일 때, N(IDS) = 123450, N(BFS) = 111110 이다.

즉, BFS 와 비교했을 때도 그리 크지 않다는 것을 알 수 있다.

즉, DFS 와 BFS 의 장점을 조합한 알고리즘이라고 생각할 수 있다.

 

 

 

Bidrectional Search

- initial state 와 goal state 각각에서 search 를 동시에 진행하면서 만나는 순간이 solution 을 찾은 순간이다.

- complexity : b^(d/2) + b^(d/2) 로, b^d 에 비하면 매우 작은 수치이다.

- 다만, 양방향 탐색은 goal 을 미리 알아야 사용할 수 있으므로 goal 을 모르는 N-queen 같은 문제에선 사용할 수 없다.

 

 

 

⭐Comparing Uninformed Search Strategies