Title Lorem
Ipsum
Sit Dolor Amet
Search Techniques
1. Uninformed search techniques: depth first search, breadth first search, depth limit search,
Iterative deepening search,
2. Heuristics search techniques: Greedy Best first search, A* search, Hill Climbing, Game
playing, Adversarial search techniques-mini-max procedure, alpha beta pruning
Uninformed search techniques: depth first search, breadth first search, depth
limit search, Iterative deepening search
• Breadth-first Search:
• Breadth-first search is the most common search strategy for traversing a tree or graph. This
algorithm searches breadthwise in a tree or graph, so it is called breadth-first search.
• BFS algorithm starts searching from the root node of the tree and expands all successor node at
the current level before moving to nodes of next level.
• The breadth-first search algorithm is an example of a general-graph search algorithm.
• Breadth-first search implemented using FIFO queue data structure.
• Advantages:
BFS will provide a solution if any solution exists.
If there are more than one solutions for a given problem, then BFS will provide
the minimal solution which requires the least number of steps.
• Disadvantage
• It requires lots of memory since each level of the tree must be saved into
memory to expand the next level.
• BFS needs lots of time if the solution is far away from the root node.
• Depth-first Search
• Depth-first search isa recursive algorithm for traversing a tree or graph data structure.
• 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.
• DFS uses a stack data structure for its implementation.
• The process of the DFS algorithm is similar to the BFS algorithm.
• Advantage:
• 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.
• It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right
path).
• Disadvantage:
• There is the possibility that many states keep re-occurring, and there is no guarantee of
finding the solution.
• DFS algorithm goes for deep down searching and sometime it may go to the infinite loop.
Depth-Limited Search Algorithm:
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:
Depth-limited search is Memory efficient.
Disadvantages:
•Depth-limited search also has a disadvantage of incompleteness.
•It may not be optimal if the problem has more than one solution.
