Depth-Limited Search (깊이 제한 탐색, DLS)은 Depth-First Search (깊이 우선 탐색)의 한 변형으로, 깊이 제한을 설정하여 상태 공간을 탐색하는 알고리즘이다. 깊이 제한은 탐색이 진행되는 깊이의 한도를 나타내며, 이 한도 내에서만 탐색을 수행한다.

깊이 제한 탐색은 주로 제한된 자원(메모리 또는 시간)을 가지고 있는 경우 또는 목표가 상대적으로 얕은 깊이에 있는 경우에 사용된다. 그러나 목표 상태가 깊은 곳에 있거나 깊이 제한을 적절히 설정하지 못하면 목표를 찾지 못할 수 있다. 또한 Iterative Deepending Search (점차적 깊이 제한 탐색)과 결합하여 깊이 제한을 점진적으로 증가 시키면 완전성(Completeness)을 보장하면서 효율적으로 탐색을 수행할 수 있다.

특징

• 깊이 제한 설정
  • DLS는 시작 상태에서 부터 특정 깊이(depth)까지만 탐색을 수행한다.
  • 즉, 한도 내에서만 상태를 확장하고 목표 상태를 찾으려고 시도한다.
• 완전성(Completeness)를 보장하지 않음
  • DLS는 깊이 제한을 설정하므로 완전성을 보장하지 않는다.
  • 목표 상태가 깊이 제한 내에 있지 않은 경우에는 목표를 찾지 못할 수 있다.
• 낮은 공간 복잡도(Space Complexity)
  • DLS는 일반적으로 깊이에 비례하는 메모리를 사용하므로 깊이 우선 탐색과 비교하여 메모리 사용량을 감소 시킬 수 있다.
• 낮은 시간 복잡도(Time Complexity)
  • 깊이 제한을 설정함으로서 탐색 깊이를 줄이고 상태 공간의 일부를 탐색하므로 시간 복잡도가 감소할 수 있다.
  • 그러나 깊이 제한이 너무 낮으면 목표 상태를 찾지 못할 수 있다.