U18PCCS501 Artificial Intellingence Uninformed Search

U18PCCS501
ARTIFICIAL
INTELLINGENCE
Uninformed Search
Searching Strategies
Search is the systematic examination of states to find

path from the start/root state to the goal state.
Many traditional search algorithms are used in AI

applications. For complex problems, the traditional
algorithms are unable to find the solution within some
practical time and space limits.
 UNINFORMED SEARCH
 INFORMED SEARCH
Uninformed Search Algorithms
 Uninformed search is a class of general-purpose

search algorithms which operates in brute force-way.
 Uninformed search algorithms do not have additional

information about state or search space other than
how to traverse the tree, so it is also called blind
search.
Following are the various types of uninformed
search algorithms:
• Breadth-first Search
• Depth-first Search
• Depth-limited Search
• Uniform cost search
• Iterative deepening depth-first search
• Bidirectional Search
Breadth- First -Search:
Consider the state space of a problem that takes the form of a tree. Now, if
we search the goal along each breadth of the tree, starting from the root and
continuing up to the largest depth, we call it breadth first search
Algorithm:
1. Create a variable called NODE-LIST and set it to initial state
2. Until a goal state is found or NODE-LIST is empty do
a. Remove the first element from NODE-LIST and call it E. If NODE-LIST

was empty, quit
b. For each way that each rule can match the state described in E do:
 Apply the rule to generate a new state
 If the new state is a goal state, quit and return this state
 Otherwise, add the new state to the end of NODE-LIST
Step 1: Initially fringe contains only one node corresponding to the source
state A.
Step 2: A is removed from fringe. The node is expanded, and its children B
and C are generated. They are placed at the back of fringe
Step 3: Node B is removed from fringe and is expanded. Its children D, E
are generated and put at the back of fringe.
Step 4: Node C is removed from fringe and is expanded. Its children

D and G are added to the back of fringe.
Step 5: Node D is removed from fringe. Its children C and F are generated
and added to the back of fringe
Step 6: Node E is removed from fringe. It has no children

Step 7: D is expanded; B and F are put in OPEN.
Step 8: G is selected for expansion. It is found to be a goal node. So

the algorithm returns the path A C G by following the parent
pointers of the node corresponding to G. The algorithm terminates.
Breadth first search is:
• One of the simplest search strategies
• Complete. If there is a solution, BFS is guaranteed to find it.
• If there are multiple solutions, then a minimal solution will be
found
• The algorithm is optimal (i.e., admissible) if all operators have the
same cost.
• Otherwise, breadth first search finds a solution with the shortest
path length.
Time complexity : O(bd )
Space complexity : O(bd )
Optimality :Yes b - branching factor(maximum no of successors of
any node),
BFS
Advantages:
• Finds the path of minimal length to the goal.
Disadvantages:
• Requires the generation and storage of a tree
whose size is exponential the depth of the
shallowest goal node.
• The breadth first search algorithm cannot be
effectively used unless the search space is quite
small
DEPTH FIRST SEARCH
• We may sometimes search the goal along the largest depth
of the tree, and move up only when further traversal along
the depth is not possible.
• We then attempt to find alternative offspring of the parent

of the node (state) last visited.
• If we visit the nodes of a tree using the above principles to

search the goal, the traversal made is called depth first
traversal and consequently the search strategy is called
depth first search
Algorithm:
1. Create a variable called NODE-LIST and set it to initial state
2. Until a goal state is found or NODE-LIST is empty do
a. Remove the first element from NODE-LIST and call it E. If NODE-LIST

was empty, quit
b. For each way that each rule can match the state described in E do:
 Apply the rule to generate a new state
 If the new state is a goal state, quit and return this state
 Otherwise, add the new state to the end of NODE-LIST
Step 1: Initially fringe contains only the node for A.
Step 2: A is removed from fringe. A is expanded and its children B and C are put in
front of fringe.
Step 3: Node B is removed from fringe, and its children D and E are pushed in
front of fringe.
Step 4: Node D is removed from fringe. C and F are pushed in front of
fringe.
Step 5: Node C is removed from fringe. Its child G is pushed in front of fringe.
Step 6: Node G is expanded and found to be a goal node.
The solution path A-B-D-C-G is returned and the algorithm

terminates.
DFS
• The algorithm takes exponential time.
• If N is the maximum depth of a node in the search space, in

the worst case the algorithm will take time O(bd).
• The space taken is linear in the depth of the search tree,

O(bN).
• Note that the time taken by the algorithm is related to the

maximum depth of the search tree. If the search tree has
infinite depth, the algorithm may not terminate. Thus Depth
First Search is not complete

U18PCCS501 Artificial Intellingence Uninformed Search

Uploaded by

Copyright:

Available Formats

U18PCCS501 Artificial Intellingence Uninformed Search

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

U18PCCS501 Artificial Intellingence Uninformed Search

Uploaded by

Copyright:

Available Formats

U18PCCS501

Search is the systematic examination of states to find

Many traditional search algorithms are used in AI

 Uninformed search is a class of general-purpose

 Uninformed search algorithms do not have additional

• Uniform cost search

• Iterative deepening depth-first search

a. Remove the first element from NODE-LIST and call it E. If NODE-LIST

Step 4: Node C is removed from fringe and is expanded. Its children

Step 6: Node E is removed from fringe. It has no children

Step 8: G is selected for expansion. It is found to be a goal node. So

• We then attempt to find alternative offspring of the parent

• If we visit the nodes of a tree using the above principles to

a. Remove the first element from NODE-LIST and call it E. If NODE-LIST

The solution path A-B-D-C-G is returned and the algorithm

• The algorithm takes exponential time.

• If N is the maximum depth of a node in the search space, in

• The space taken is linear in the depth of the search tree,

• Note that the time taken by the algorithm is related to the

You might also like