Depth-First Search, Depth-Limited Search

Depth-First Search

- 항상 가장 깊은 노드부터 expand 하는 기법이다.

- Graph search 의 frontier 를 LIFO 로 구현한 방식이다.

 

 

Performance of Depth-First Search

- Completeness : 

• Graph search version : Yes, 단 state space 가 유한한 크기일 때
• Tree search version : No, 방문했던 노드를 재방문 가능하므로 cycle 이 생길 수 있다.
• -> graph 버전은 explored set 으로 노드의 중복을 막고, tree 버전은 루프가 생길 수 있다.

- Optimality : No, 항상 최적은 아니다. 최적의 답보다 더 깊이 있는 노드를 먼저 찾을 수 있기 때문

- Time complexity : 

• Graph search version : state space 의 최대 사이즈
• Tree search version : O(b^m) / 여기서 m은 가장 길게 뻗을 수 있는 경로 길이를 뜻하고, 항상 m>=d 를 만족한다.   d는 goal 의 경로 길이를 뜻함.

- Space complexity : 

• Graph search version : state space 의 최대 사이즈 (Explored set + frontier)
• Tree search version : O(bm)
  • 오직 root부터 leaf 까지의 하나의 path 만 저장하면 된다.
  • explored set 을 저장할 필요가 없어서, frontier 만 저장하면 된다.
  • 매우 작은 공간이 요구되기 때문에 과거 AI 개발자들이 많이 사용했던 search 방법이다.

 

⭐Depth-Limited Search

- DFS 는 무한한 상태 공간에서는 정답을 발견하지 못할 경우 tree 의 밑부분까지 계속해서 파고들어, 시간복잡도가 매우 증가하였다.

- 따라서 DFS 에서 파고들 수 있는 depth 에 제한을 두어 시간복잡도를 개선한 알고리즘이다.

- 탐색할 깊이 제한인 L 을 둔다.

 

 

 

- 위의 코드를 살펴보면, DLS 를 재귀적으로 구현하였다.

- 자식 노드들에 대하여, RECURSIVE_DLS 의 인자값으로 liimt -1 을 줘서 탐색한다.

- 자식들에 대해 탐색한 결과값이 cutoff 라면, 길이 제한으로 인해 더 이상 탐색하지 못함을 의미한다.

- 자식들에 대해 탐색한 결과값이 failure 라면, solution 을 발견하지 못한 것으로 계속 탐색을 진행한다.

 

 

 

Performance of Depth-Limited Search

- Completeness : L < d 라면 NO, 즉 limit depth 보다 깊은 곳에 최초의 답이 있다면 답을 찾지 못하기 때문이다.

- Optimal : No (DFS 와 동일하다)

- Time complexity : O(b^L)

- Space complexity : O(bL)

 

- L값을 정하는 법

• L 이 너무 얕으면 답을 찾지 못하고 종료될 것이고, 너무 깊으면 시간이 오래걸리기 때문에 적당한 값을 잘 설정해야 한다.
• 상태 공간의 지름을 알고 있다면 L을 설정하기 좋을 것이다. -> 사전 지식 필요