Iterative deepening DFS, Bidirectional Search

Iterative Deppening DFS (IDS)

Depth limit 를 조금 씩 늘려나가는 Depth limited Search 방식으로, goal state를 찾을 때까지 반복해나갑니다.

 

function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or failure
  for depth = 0 to INFINITE do
  result ← DEPTH-LIMITED-SEARCH(problem, depth)
  if result != cutoff then return result

 

평가

• Complete : yes ( BFS 와 같은 원리 )

• Optimal : yes ( BFS 와 같은 원리 )

• Time complexity : O(b^d) (BFS와 같은 원리)
  N(IDS) = db + (d - 1)b^2 + (d - 2)b^3 + … 1b^d

• Space complexity : O(bd)

 

동작방식

IDS 효율성

같은 노드가 여러번 생성되어 약간의 중복은 생기지만 대부분의 노드는 bottom level에 존재하기에 중복의 수가 큰 의미를 갖진 않습니다.

bottom level의 leaf 노드는 한 번만 생성되기 때문입니다.

 

Bidirectional Search 양방향 탐색

start, goal state 각각에서 search 를 동시에 진행하면서 만나는 순간이 답을 찾은 순간임을 이용한 검색 방법입니다.

 

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

 

다만 양방향 탐색은 goal 을 미리 알고 있는 상태에서 그 route 를 찾는 탐색 방법으로, goal을 모르는 상태인 N-queen 문제에는 사용할 수 없습니다.