Day 7 Flashcards
Depth-first search is a recursive algorithm for traversing a tree or graph data structure
o It is called the depth-first search because it starts from the root node and follows each path to its greatest depth node before moving to the next path
o It is called the depth-first search because it starts from the root node and follows each path to its greatest depth node before moving to the next path
Advantages of DFS:
DFS requires very less memory as it only needs to store a stack of the nodes on the path from root node to the current node.
Advantages of DFS:
It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right path).
Disadvantages of DFS
There is the possibility that many states keep re-occurring, and there is no guarantee of finding the solution
Disadvantages of DFS
DFS algorithm goes for deep down searching and sometimes it may go to the infinite loop.
The process of the DFS algorithm is similar to the BFS algorithm.
صح
DFS uses a stack data structure for its implementation
DFS uses a stack data structure for its implementation
A variant of depth-first search called backtracking search uses even less memory.
A variant of depth-first search called backtracking search uses even less memory.
Time Complexity: Time complexity of DFS will be equivalent to the node traversed by the algorithm. It is given by:
T(n)= 1+ n2+ n3 +………+ n^m=O(n^m)
Where, m= maximum depth of any node and this can be much larger than d (Shallowest solution depth)
Space Complexity: DFS algorithm needs to store only single path from the root node, hence space complexity of DFS is equivalent to the size of the fringe set, which is O(bm)
Space Complexity: DFS algorithm needs to store only single path from the root node, hence space complexity of DFS is equivalent to the size of the fringe set, which is O(bm)
Completeness: DFS search algorithm is complete within finite state space as it will expand every node within a limited search tree. In infinite state spaces, depth-first search is not systematic: it can get stuck going down an infinite path, even if there are no cycles. Thus, depth-first search is incomplete.
Completeness: DFS search algorithm is complete within finite state space as it will expand every node within a limited search tree. In infinite state spaces, depth-first search is not systematic: it can get stuck going down an infinite path, even if there are no cycles. Thus, depth-first search is incomplete.
Optimality: DFS search algorithm is non-optimal, as it may generate a large number of steps or high cost to reach to the goal node
Optimality: DFS search algorithm is non-optimal, as it may generate a large number of steps or high cost to reach to the goal node
o A depth-limited search algorithm is similar to depth-first search with a predetermined limit ℓ. Depth-limited search can solve the drawback of the infinite path in the Depth-first search. In this algorithm, the node at the depth limit will treat as it has no successor nodes further
o A depth-limited search algorithm is similar to depth-first search with a predetermined limit ℓ. Depth-limited search can solve the drawback of the infinite path in the Depth-first search. In this algorithm, the node at the depth limit will treat as it has no successor nodes further
Depth-limited search can be terminated with two Conditions of failure:
➢Standard failure value: It indicates that problem does not have any solution.
➢Cutoff failure value: It defines no solution for the problem within a given depth limit
Advantages of depth-limited search
o Depth-limited search is Memory efficient.
Time Complexity: Time complexity of DLS algorithm is O(bℓ).
Time Complexity: Time complexity of DLS algorithm is O(bℓ).
Space Complexity: Space complexity of DLS algorithm is O(b×ℓ).
Space Complexity: Space complexity of DLS algorithm is O(b×ℓ).
Completeness: DLS search algorithm is complete if the solution is above the depth-limit
Completeness: DLS search algorithm is complete if the solution is above the depth-limit
The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search algorithm finds out the best depth limit and does it by gradually increasing the limit until a goal is found.
The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search algorithm finds out the best depth limit and does it by gradually increasing the limit until a goal is found.
This algorithm performs depth-first search up to a certain “depth limit”, and it keeps increasing the depth limit after each iteration until the goal node is found.
The iterative search algorithm is useful uninformed search when search space is large, and depth of goal node is unknown.
It combines the benefits of BFS and DFS search algorithm in terms of fast search and memory efficiency
The main drawback of IDDFS is that it repeats all the work of the previous phase.
