UNINFORMED SEARCH

STRATEGIES
UNIT 2
 Contents
• Formulation of real-world problems
• Breadth First Search
• Depth First Search
• Depth Limited Search
• Iterative Deepening Depth First Search
• Bidirectional Search
• Comparison of Uninformed search Strategies
• Searching with partial information
• Sensor-less problems
• Contingency problems.
 Formulation of real-world problems
The problem-solving agent performs precisely by defining problems and several solutions. Artificial intelligence that
encompasses a number of techniques such as a tree, B-tree, heuristic algorithms to solve a problem.
Steps problem-solving in AI:
Goal Formulation: This one is the first and simple step in problem-solving. It organizes finite steps to formulate a
target/goals which require some action to achieve the goal. Today the formulation of the goal is based on AI agents.
Problem formulation: It is one of the core steps of problem-solving which decides what action should be taken to
achieve the formulated goal.
In AI this core part is dependent upon software agent which consisted of the following components to formulate the
associated problem.
• Initial State: This state requires an initial state for the problem which starts the AI agent towards a specified goal.
• Action: This stage of problem formulation works with function with a specific class taken from the initial state
and all possible actions done in this stage.
• Transition: This stage of problem formulation integrates the actual action done by the previous action stage and
collects the final stage to forward it to their next stage.
• Goal test: This stage determines that the specified goal achieved by the integrated transition model or not,
whenever the goal achieves stop the action and forward into the next stage to determines the cost to achieve the
goal.
• Path cost: This component of problem-solving numerical assigned what will be the cost to achieve the goal. It
requires all hardware software and human working cost.
 Search
Search
• The agents goal is to specifically search for best possible solution.
• The artificially intelligent agents that work towards a goal, identify the action or
series of actions that lead to the goal.
• The series of actions that lead to the goal becomes the solution for the given
problem.
• The agent should be clear about the goal.
• Since there are many ways to reach that goal, the agent should also be able to
evaluate a solution and determine its preference for a solution.
 Evaluation
Different search strategies are evaluated along :
completeness, time complexity, space complexity and optimality.

Most of the work in the area of search has gone into finding the right search strategy for
a problem.

1. Completeness: is the strategy guaranteed to find a solution when there is one?

2. Time complexity: how long does it take to find a solution?

3. Space complexity: how much memory does it need to perform the search?

4. Optimality: does the strategy find the highest-quality solution when there are
several different solutions?
 Search Algorithms in AI
Uninformed Search Algorithms:

• The term means that they have no information about the number of steps or the path cost
from the current state to the goal.
• Uninformed search is also sometimes called blind search.
• This type of search does not use any domain knowledge.

Informed Search Algorithms:

• Here, the algorithms have information on the

goal state, which helps in more efficient
searching.
• This information is obtained by something
called a heuristic.
• This type of search uses domain knowledge.
 What is graph traversal
• The process of visiting and exploring a graph for processing is called graph traversal.
• To be more specific it is all about visiting and exploring each vertex and edge in a graph
such that all the vertices are explored exactly once.
• Visiting a node: Just like the name suggests, visiting a node means to visit or select a node.
• Exploring a node: Exploring the adjacent nodes (child nodes) of a selected node.
 Breadth First
BFS(Breadth FirstSearch
Search):
• Breadth-First Search algorithm is a graph traversing technique, where you select a random initial node (source or
root node) and start traversing the graph layer-wise in such a way that all the nodes and their respective children
nodes are visited and explored.
• Queue is the main data structure involved in the Breadth-First Search algorithm.
• A queue is an abstract data structure that follows the First-In-First-Out methodology (data inserted first will be
accessed first). It is open on both ends, where one end is always used to insert data (enqueue) and the other is
used to remove data (dequeue).
 Steps:
The steps involved in traversing a graph by using
Breadth-First Search:
• Step 1: Take an Empty Queue.
• Step 2: Select a starting node (visiting a
node) and insert it into the Queue.
• Step 3: Provided that the Queue is not empty,
extract the node from the Queue and insert its
child nodes (exploring a node) into the Queue.
• Step 4: Print the extracted node.

Let us understand with an example……

 Example
Take a look at the below graph, we will use the Breadth-First Search algorithm to traverse through the graph.

In this case, we’ll assign node ‘a’as the root node and start traversing downward and follow the steps mentioned
above.
 .

BFS
 Why do we need BFS Algorithm?
• BFS is useful for analyzing the nodes in a graph and constructing the shortest
path of traversing through these.
• BFS can traverse through a graph in the smallest number of iterations.
• The architecture of the BFS algorithm is simple and robust.
• The result of the BFS algorithm holds a high level of accuracy in comparison to
other algorithms.
• BFS iterations are seamless, and there is no possibility of this algorithm getting
caught up in an infinite loop problem.
 BFS Pros and Cons
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.
Disadvantages:
• 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.
 Example
• In the below tree structure, we have shown the traversing of
the tree using BFS algorithm from the root node S to goal
node K. BFS search algorithm traverse in layers, so it will
follow the path which is shown by the dotted arrow, and the
traversed path will be:
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
• Time Complexity: Time Complexity of BFS algorithm can
be obtained by the number of nodes traversed in BFS until
the shallowest Node. Where the d= depth of shallowest
solution and b is a node at every state.

• Space Complexity: The space complexity for BFS is O(bd)

where d is the maximum width of the tree
• Completeness: BFS is complete, which means if the
shallowest goal node is at some finite depth, then BFS will
find a solution.
• Optimality: BFS is optimal.
Applications Of Breadth-First Search Algorithm
 Depth First
Depth First Search(DFS) Search
• Depth-first search (DFS) is an algorithm for a graph traversing
technique.
• The algorithm starts at the root node and explores as far as possible along
each branch before backtracking.
• DFS uses a stack data structure for its implementation.
 Algorithm steps

[Link] the root node on a stack.

[Link](stack is not empty)
a) Pop a node
✓ Push all the children of node into the
stack.

Note: Add always in reverse order

because the top of the element should
be left of root node.
 Depth First
Depth First Search(DFS) Search Steps
Depth First Search Example
 DFS
• 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.
 Example
• Completeness: DFS search algorithm is complete within
finite state space as it will expand every node within a
limited search tree.
• 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 +.........+ nm=O(nm)
• 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, which is O(bm).
• Optimal: DFS search algorithm is non-optimal, as it may
generate a large number of steps or high cost to reach to
the goal node.
 Applications
[Link] puzzles.
[Link] games.
[Link] path.
[Link] Graph: DFS can be used to find if a graph is bipartite or not.
[Link] detection: Since we are maintaining the list of visited nodes, it can be
used to detect if a cycle is present in the graph or not.
[Link] Sorting: Topological Sorting can be done with the help of DFS.
[Link] Connected Graph: Using DFS, we can find if a graph is strongly
connected or not i.e. is there any path from one node to other nodes of the graph.
BFS Vs DFS
 Depth Limited Search
• 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:
1. Standard failure value: It indicates that problem does not have any solution.
2. 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.
 Depth Limited Search(DLS) Process
If we fix the depth limit to 2, DLS can be carried out similarly to the
DFS until the goal node is found to exist in the tree’s search domain.
Algorithm of the example
[Link] start with finding and fixing a start node.
[Link] we search along with the depth using the DFS algorithm.
[Link] we keep checking if the current node is the goal node or not.
If the answer is no: then we do nothing.
If the answer is yes: then we return.
[Link] we will check whether the current node is lying under the depth
limit specified earlier or not.
If the answer is not: then we do nothing.
If the answer is yes, we will explore the node further and save all of
its successors into a stack.
[Link] we call the function of DLS iteratively or recursively for all the
nodes of the stack and go back to step 2.
[Link] we have successfully explored all the nodes in the given depth
limit and found the goal node if it exists within a specified depth limit.
 Depth Limited Search Step by Step Example
Consider the given graph with Depth Limit(l)=2, Step 2:A being the top element is now popped from the stack and the
Target Node=H and the given source node=A neighbouring nodes B and C at depth=1(<l) of A are pushed onto the
stack.
Traversal: A

Step 3:C being the topmost element is popped from the stack and the
Step 1:Now, the first element of the source node is neighbouring node F at depth=2(=l) is pushed onto the stack.
pushed onto the stack. Traversal: AC
 Depth Limited Search Step by Step Example
Step 4:F being the topmost element is popped from the stack and Step 6:E being the topmost element is popped from the stack
the neighbouring nodes I and K at depth=3(>l) will not be and since E has no neighbouring nodes, no nodes are pushed
pushed onto the stack. onto the stack.
Traversal: ACF Traversal: ACFBE

Step 7:D being the topmost element is popped from the stack
Step 5:B being the topmost element is popped from the stack and the neighbouring nodes G and H at depth=3(>l) will not be
and the neighbouring nodes D and E at depth=2(=l) are pushed pushed onto the stack.
onto the stack. Traversal: ACFBED
Traversal: ACFB
Since the stack is now
empty, all nodes
within the depth limit
have been visited, but
the target node H has
not been reached.
 Example
• Completeness: DLS search algorithm is
complete if the solution is above the depth-
limit.
• Time Complexity: Time complexity of DLS
algorithm is O(bℓ).
• Space Complexity: Space complexity of
DLS algorithm is O(b×ℓ).
• Optimal: Depth-limited search can be viewed
as a special case of DFS, and it is also not
optimal even if ℓ>d.
Solve for DL=4 find the path to reach goal R
 Applications
[Link] puzzles.
[Link] games.
[Link] detection
[Link] Sorting
BFS Vs DFS Vs DLS
 Iterative Deepening Depth First Search
• 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.
• This Search algorithm combines the benefits of Breadth-first search's fast search and depth-
first search's memory efficiency.
• The iterative search algorithm is useful uninformed search when search space is large, and
depth of goal node is unknown.
• Advantages:
• It combines the benefits of BFS and DFS search algorithm in terms of fast search and
memory efficiency.
• Disadvantages:
• The main drawback of IDDFS is that it repeats all the work of the previous phase.
 Iterative Deepening Depth First Search
Completeness:
This algorithm is complete is if the branching
factor is finite.
Time Complexity:
Let's suppose b is the branching factor:
(b: The average number of children of each
node).
and depth is d then the time complexity
is O(bd).
Space Complexity:
The space complexity of IDDFS will be O(bd)
Optimal:
IDDFS algorithm is optimal.
 Bidirectional Search Algorithm:
• Bidirectional search algorithm runs two simultaneous searches, one form initial state called as
forward-search and other from goal node called as backward-search, to find the goal node.
• Bidirectional search replaces one single search graph with two small subgraphs in which one
starts the search from an initial vertex and other starts from goal vertex. The search stops
when these two graphs intersect each other.
• Bidirectional search can use search techniques such as BFS, DFS, DLS, etc.
Advantages:

• Bidirectional search is fast.

• Bidirectional search requires less memory

Disadvantages:

• Implementation of the bidirectional search tree is difficult.

• In bidirectional search, one should know the goal state in advance.
 Bidirectional Search Example:
The start node is 5 and the end node is 4. Step 1:Start moving forward from start node (Green) and
Aim: To find the shortest path from 5 to 4 using bidirectional backwards from end node (Orange).
search.

Step 2:Similar to BFS, at every point explore the next level of

nodes till you find an intersecting node
 Bidirectional Search Example:
Step 4:Trace back to find the path
Step 3: Stop on finding the intersecting node.
 Bidirectional Search Algorithm Example:
In the below search tree, bidirectional search algorithm is
applied. This algorithm divides one graph/tree into two
sub-graphs. It starts traversing from node 1 in the
forward direction and starts from goal node 16 in the
backward direction.
The algorithm terminates at node 9 where two searches
meet.
Completeness: Bidirectional Search is complete if we
use BFS in both searches.
Time Complexity: Time complexity of bidirectional
search using BFS is O(bd).
Space Complexity: Space complexity of bidirectional
search is O(bd).
Optimal: Bidirectional search is Optimal.
 Comparison of Uninformed search Strategies
The following parameters are used to evaluate the performance of the searching algorithms.
A. Time Complexity
• The time complexity of an algorithm is an expression for the
amount of time it will take to run
B. Space Complexity
• The space complexity of an algorithm is an expression for the amount of memory that the algorithm will use (number of
nodes).
C. Optimality
• A search algorithm is optimal if, when it finds a solution it is the best solution.
D. Completeness
• A search algorithm is complete if, whenever at least one solution exists, the algorithm is guaranteed to find a solution within a
finite amount of time.
• Simple BFS and BDS are complete and optimal but expensive with respect to space and time. DFS requires much less
memory if the maximum tree depth is limited, but has no guarantee of finding any solution, let alone an optimal one.
• DLS offers an improvement over DFS if we have some idea how deep the goal is. The best overall is DFID which is complete,
optimal and has low memory requirements, but still exponential time.
 Searching with partial information
Problem types:
[Link],fully observable--→ single state problem
Agent knows exactly which state it will be in;solution is a sequence.
[Link] knowledge of state and actions:
Agents percepts cannot pin down the exact state the agent is in
Let Agents have Belief states
• Search for a sequence of belief states that leads to a goal
• Search for a plan that leads to a goal
If the environment is not fully observable or deterministic, then the following types of problems occur:
[Link] observable: Sensorless or conformant problems
[Link] deterministic and/or partially observable: Contingency problems
[Link] state space: Exploration problems: This can be considered an extreme case of contingency problems,
when the states and actions of the environment is unknown, the agent must act to discover them.
 Sensor-less problems
• If the agent has no sensors, then the agent cannot know it’s current state, and hence would have to
make many repeated action paths to ensure that the goal state is reached regardless of it’s initial state.
• The agent doesn’t know where it is. We can use belief states (sets of states that the agent might be in).
Example: Vacuum World
Goal formulation: intuitively, we want all the dirt cleaned up. Formally, the goal is { state 7, state 8 }.
Problem formulation(Actions):Left, Right, Suck, NoOp
Agent: Vacuum cleaner
States: Two locations with or without dirt:2*2=8 states
Initial state: Any state can be initial
Actions: Left, Right, Suck
Goal test: Check whether squares are clean
Path cost: number of actions to reach goal
 Sensor-less problems
Offline Example: Vacuum World with two rooms, cleaning always works, a square once
cleaned stays clean. States are 1 – 8, goal states are 7 and 8.

State Space Graph

 Contingency problems
• This is when the environment is partially observable or when actions are uncertain. Then
after each action the agent needs to verify what effects that action has caused. Rather than
planning for every possible contingency after an action, it is usually better to start acting and
see which contingencies do arise.
• This is called interleaving of search and execution.
• exact prediction is impossible
state unknown in advance, may depend on the outcome of actions and changes in the environment
accessibility of the world some essential information may be obtained through sensors only at execution time
consequences of action may not be known at planning time
goal instead of single action sequences, there are trees of actions
contingency branching point in the tree of actions
agent design different from the previous two cases:the agent must act on incomplete plans
search and execution phases are interleaved
 Contingency problems
• Contingency Problem: The agent doesn’t know what effect its actions will have. This could
be due to the environment being partially observable, or because of another agent. Ways to
handle this:
• Solution is a list of conditional actions
• Example: Partially observable vacuum world (meaning you don’t know the status of the other
square) in which sucking in a clean square may make it dirty.
• No way to preplan a solution!!
• A solution starting in a state where you’re in the left room and it’s dirty is:
• Suck
• Right
• if dirty then Suck
Can also model contingency problems is with "AND-OR graphs“[An AND/OR graph is a
graph which represents a problem-solving process. A solution graph is a subgraph of the
AND/OR graph which represents a derivation for a solution of the problem].
 Contingency problems
• Example: find a winning strategy for Nim if there
are only five stones in one row left. You are player
square. You win if it is player circle’s turn with
zero stones left.
• In general then, a solution is a subtree in which
• The root node is in the subtree
• For every OR node in the subree, at least one child
is in the subtree
• For every AND node in the subtree, all children
are in the subtree
• All leaves are goal states
• If the tree has only OR nodes, then the solution is
just a path.
End of Unit 2