Summary
Highlights
Depth-Limited Search (DLS) is an extension of Depth-First Search (DFS) designed to prevent getting stuck in infinite search spaces. DFS can continuously go deeper into a path, overlooking the goal state if it exists on a different, shallower path, or getting stuck if the search space is infinite. DLS introduces a limit on the depth of the search, ensuring that the algorithm does not go too deep.
The main problem with DFS is its inability to handle infinite search spaces. If the graph or tree has an infinite length, DFS can get stuck in a loop, continuously exploring one deep path and never returning to find the goal state, even if it's much shallower on another branch. DLS solves this by setting a predefined depth limit, preventing infinite exploration.
DLS works by setting a maximum depth 'L' for the search. If the goal state is found within this limit, it's successful. Otherwise, once the limit is reached on a particular path, the algorithm backtracks. For example, if the limit is 3, the search explores nodes up to the third level. If a node at level 3 has children, they are not explored, and the search backtracks to find other paths within the limit.
Using a sample tree, the video demonstrates DLS with a depth limit of 3. Starting from node 'A', the algorithm explores 'A' -> 'B' -> 'D' -> 'F'. Since 'F' is at depth 3, it backtracks. Then it explores 'A' -> 'B' -> 'D' -> 'G'. Again, 'G' is at depth 3, so it backtracks. It continues this process, exploring paths like 'A' -> 'B' -> 'E', then 'A' -> 'C' -> 'H' -> 'K', until a goal state 'K' is found within the set depth limit.
DLS is not complete because if the goal state exists beyond the specified depth limit, the algorithm will never find it. It is also not optimal because it doesn't guarantee finding the shortest or best path to the goal, even if it finds one within the limit. There might be multiple paths to the goal, and DLS might find a longer one first.
The time complexity of DLS is O(b^L), where 'b' is the branching factor (average number of children per node) and 'L' is the depth limit. This is because, in the worst case, it might have to explore all nodes up to the depth limit. The space complexity is O(b*L), as it only needs to store the current path from the root to the current node, which is limited by 'L'.
DLS is particularly useful in scenarios where the search space is vast or potentially infinite. By imposing a depth limit, it prevents the algorithm from getting stuck in an indefinite loop, making it more practical for such problems where unrestricted DFS would fail. While DFS can be used in many places, DLS is preferred when there's a risk of infinite search.