Chapter 3: Problem Solving Agent

JSS MAHAVIDYAPEETHA

JSS ACADEMY OF TECHNICAL EDUCATION, Bengaluru

Department of Computer Science &Engineering

Chapter 3 – Problem- Solving Agent

Solving problems by searching
 Intelligent agents are supposed to maximize their performance measure.
 This is sometimes if the agent can adopt a goal and aim at satisfying it.
Problem – solving agent
 Is kind of goal –based agent.
 It solves problems by finding sequence of action that lead to desirable states (goals).
 to solve a problem ,
o The first ‘step is the goal formulation, based on the current situation.
o Goals help organize behaviour by limiting the objectives that the agent is
trying to achieve and hence the actions it needs to consider.
o Goal formulation- the goal is formulated as set of word states in which the
goal is satisfied.
o The agent’s task is to find out how to act, now and in the future, so that it
reaches a goal state.
o Actions are the operators.
o Causing transitions between world states.
o Action should be abstract instead of very detailed.
 Problem formulation is the process of deciding what actions and states to consider.
 Search - Because there are many ways to achieve the same goal.
o Those ways are together expressed as a tree.
o Multiple options of unknown value at a point. The agent can examine
different possible sequence of actions and choose the best.
o The process of looking for best sequence is called search.
o The best sequence is then a list of actions called solutions.
 Searching algorithm: - a searching algorithm takes a problem as input and returns
a solution in the form of an action sequence.
 Once a solve is formed, the actions it recommends can be carried out. This is called
executions on phase.

1|Page
 Chapter 3: Problem Solving Agent

 Design of an agent –formulate, search, execute. A simple “formulate, search,

execute” design for the agent,

 The algorithm above is a simple problem-solving agent. It first formulates a goal and
a problem, searches for a sequence of actions that would solve the problem, and
then executes the actions one at a time. When this is complete, it formulates another
goal and starts over.
 After formulating a goal and a problem to solve, the agent calls a search procedure
to solve it. It then uses the solution to guide its actions, doing whatever the solution
recommends as the next thing to do.
Well-defined problems and solutions :-
 A problem can be defined formally by five components:
 Initial State : The initial state that the agent starts in.
 Actions- description of possible actions actions available to the agent. Given a
particular state S, Action(s) returns the set of actions that can be executed in s.
 Transition model – A description of what each action does. Result(s,a) – returns the
state that results from doing action a in state s. Successor function – refers to any
state reachable from given state by a single action.
 Initial state, actions and transition model define state space of the problem i.e set of
all states reachable from initial state by any sequence of actions.
 The state space forms a directed network or graph in which the nodes are states
and the links between the nodes are actions.
 A path in the state space is a sequence of states connected by a sequence of actions.
 Goal Test: It determines whether the given state is a goal state. It is applied to the
current state to test if the agent is in its goal state. There may be possible set of goal
states. The goal is specified by an abstract property rather than an explicitly
enumerated set of states. For example, in chess, the goal is to reach a state called
“checkmate,” where the opponent’s king is under attack and can’t escape.
 A path cost function that assigns a numeric cost to each path. The problem-solving
agent chooses a cost function that reflects its own performance measure. . For the
agent trying to get to particular city, time is of the essence, so the cost of a path
might be its length in kilometers.

2|Page
 Chapter 3: Problem Solving Agent

 The cost of a path can be described as the sum of the costs of the individual actions
along the path. The step cost of taking action a in state s to reach state s ′ is denoted
by c(s, a, s′ ).
 A solution to a problem is an action sequence that leads from the initial state to a
goal state.
 Solution quality is measured by the path cost function, and an optimal solution has
the lowest path cost among all solutions.
 The process of removing detail from a representation is called abstraction. In
addition to abstracting the state description, we must abstract the actions
themselves. Eg: turning on the radio, looking out of the window, slowing down for
law enforcement officers, turn steering wheel to the left by one degree.
Example Problems:
 The problem-solving approach has been applied to a vast array of task
environments like the best known, distinguishing between toy and real-world
problems.
 A toy problem is intended to illustrate or exercise various problem-solving
methods. It can be given a concise, exact description and hence is usable by different
researchers to compare the performance of algorithms.
 A real-world problem is one whose solutions people actually care about. Such
problems tend not to have a single agreed-upon description, but can give the
general flavor of their formulations.
Toy Problems:
 The first example is the vacuum world.
 Vacuum world problems can be formulates as:
o States: The state is determined by both the agent location and the dirt locations.
The agent is in one of two locations, each of which might or might not contain dirt.
Thus, there are 2 × 2 2 = 8 possible world states. A larger environment with n
locations has n · 2 n states.
o Initial state: Any state can be designated as the initial state.
o Actions: In this simple environment, each state has just three actions: Left, Right,
and Suck. Larger environments might also include Up and Down.
o Transition model: The actions have their expected effects, except that moving Left
in the leftmost square, moving Right in the rightmost square, and Sucking in a
clean square have no effect. The complete state space is shown in Figure.
o Goal test: This checks whether all the squares are clean.

3|Page
 Chapter 3: Problem Solving Agent

o Path cost: Each step costs 1, so the path cost is the number of steps in the path.

The state space for the vacuum world. Links denote actions: L = Left, R = Right, S = Suck.

 The 8-puzzle, an instance of which is shown in Figure, consists of a 3×3 board with
eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into
the space. The object is to reach a specified goal state, such as the one shown on the
right of the figure.
 The standard formulation is as follows:

 States: A state description specifies the location of each of the eight tiles and the blank
in one of the nine squares.
 Initial state: Any state can be designated as the initial state. Note that any given goal
can be reached from exactly half of the possible initial states.
 Actions: The simplest formulation defines the actions as movements of the blank space
Left, Right, Up, or Down. Different subsets of these are possible depending on where
the blank is.
 Transition model: Given a state and action, this returns the resulting state; for example,
if we apply Left to the start state in Figure, the resulting state has the 5 and the blank
switched.
 Goal test: This checks whether the state matches the goal configuration shown in
Figure. (Other goal configurations are possible.)
 Path cost: Each step costs 1, so the path cost is the number of steps in the path.
8-queens problem

4|Page
 Chapter 3: Problem Solving Agent

 The goal of the 8-queens problem is to place eight queens on a chessboard such that
no queen attacks any other.
 There are two main kinds of formulation.
o An incremental formulation involves operators that augment the state
description, starting with an empty state; for the 8-queens problem, this means
that each action adds a queen to the state.
o A complete-state formulation starts with all 8 queens on the board and moves
them around.
 In either case, the path cost is of no interest because only the final state counts.
 The first incremental formulation:
o States: Any arrangement of 0 to 8 queens on the board is a state.
o Initial state: No queens on the board.
o Actions: Add a queen to any empty square.
o Transition model: Returns the board with a queen added to the specified square.
o Goal test: 8 queens are on the board, none attacked.
Real-world problems
 Route-finding problems – websites, in-car systems, routing video streams in CN,
military operations planning, airline travel planning.
 Touring problems
 Traveling Salesperson problem: is a touring problem in which each city must be visited
exactly once. The aim is to find the shortest tour. The problem is known to be NP-hard,
but an enormous amount of effort has been expended to improve the capabilities of
TSP algorithms.
 VLSI Layout – positioning millions of components and connections on a chip to
minimize area, circuit delays, stray capacitance and maximize manufacturing yield.
 Robot Navigation – can move in continuous space with an infinite set of possible
actions and states.
 Automatic assembly sequencing: The aim is to find an order in which to assemble the
parts of some object. If the wrong order is chosen, there will be no way to add some
part later in the sequence without undoing some of the work already done. Checking a
step in the sequence for feasibility is a difficult geometrical search problem closely
related to robot navigation. Thus, the generation of legal actions is the expensive part
of assembly sequencing.
 Another important assembly problem is protein design, in which the goal is to find a
sequence of amino acids that will fold into a three-dimensional protein with the right
properties to cure some disease.
Searching for Solutions:
 After formulating the problem, need to solve them.
 A solution is an action sequence, so search algorithms work by considering various
possible action sequences.
 The possible action sequences starting at the initial state form a search tree with
the initial state at the root.

5|Page
 Chapter 3: Problem Solving Agent

 The branches are actions and the nodes correspond to states in the state space of
the problem.
Route map of Romania, a person travelling from Arad to Bucharest

6|Page
 Chapter 3: Problem Solving Agent

 Figure shows the Partial search trees for finding a route from Arad to Bucharest.
Nodes that have been expanded are shaded; nodes that have been generated but
not yet expanded are outlined in bold; nodes that have not yet been generated are
shown in faint dashed lines.
 The root node of the tree corresponds to the initial state, In(Arad). The first step
is to test whether this is a goal state.
 We need to expand the trees from current state. Applying each legal action to the
current state, thereby generating a new set of states.
 In this case, add three branches from the parent node In(Arad) leading to three
new child nodes: In(Sibiu), In(Timisoara), and In(Zerind). Next choose which of
these three possibilities to consider further.
 Until the goal state is reached, expand the search tree.
 A leaf node, that is, a node with no children in the tree.
 The set of all leaf nodes available for expansion at any given point is called the
frontier.
 The process of expanding nodes on the frontier continues until either a solution is
found or there are no more states to expand.
 Search algorithms all share this basic structure; they vary primarily according to
how they choose which state to expand next—the so-called search strategy.
 In the figure, there is a loopy path that is from Arad-Sibiu-Arad.

7|Page
 Chapter 3: Problem Solving Agent

 Loopy paths are a special case of the more general concept of redundant paths,
which exist whenever there is more than one way to get from one state to another
 The redundant paths can cause a tractable problem to become intractable.

 This happens because the algorithms that forget their history are doomed to
repeat it.
 The way to avoid exploring redundant paths is to remember where one has been.
 Add an additional data structure called explored set to tree-search algorithm,
which remembers every expanded node.
 Newly generated nodes that match previously generated nodes—ones in the
explored set or the frontier—can be discarded instead of being added to the
frontier. The new algorithm, called GRAPH-Search includes the data structure
explored set.
 The search tree constructed by the GRAPH-SEARCH algorithm contains at most
one copy of each state.
 The frontier separates the state-space graph into the explored region and the
unexplored region, so that every path from the initial state to an unexplored state
has to pass through a state in the frontier.
 The separation property of GRAPH-SEARCH, illustrated on a rectangular-grid
problem. The frontier (white nodes) always separates the explored region of the
state space (black nodes) from the unexplored region (gray nodes). In (a), just the
root has been ex panded. In (b), one leaf node has been expanded. In (c), the
remaining successors of the root have been expanded in clockwise order.

Infrastructure for search algorithms

8|Page
 Chapter 3: Problem Solving Agent

 Search algorithms require a data structure to keep track of the search tree that is
being constructed.
 For each node n of the tree, we have a structure that contains four components:
o [Link]: the state in the state space to which the node corresponds;
o [Link]: the node in the search tree that generated this node;
o [Link]: the action that was applied to the parent to generate the node
o [Link]-COST: the cost, traditionally denoted by g(n), of the path from the
initial state to the node, as indicated by the parent pointers

Nodes are the data structures from which the search tree is constructed. Each has a
parent, a state, and various bookkeeping fields. Arrows point from child to parent.

 Given the components for a parent node, it is easy to see how to compute the necessary
components for a child node. The function CHILD-NODE takes a parent node and an
action and returns the resulting child node:

 Difference between a node and the state: A node is a bookkeeping data structure used
to represent the search tree. A state corresponds to a configuration of the world. Thus,
nodes are on particular paths, as defined by PARENT pointers, whereas states are not.
Furthermore, two different nodes can contain the same world state if that state is
generated via two different search paths.
 The frontier needs to be stored in such a way that the search algorithm can easily
choose the next node to expand according to its preferred strategy. The appropriate
data structure for this is a queue. The operations on a queue are as follows:
o EMPTY? (queue) returns true only if there are no more elements in the queue.
o POP(queue) removes the first element of the queue and returns it.
o INSERT(element, queue) inserts an element and returns the resulting queue

 Queues are characterized by the order in which they store the inserted nodes.
 Three common variants are the first-in, first-out or FIFO queue, which pops the oldest
element of the queue;
 the last-in, first-out or LIFO queue (also known as a stack), which pops the newest
element of the queue;

9|Page
 Chapter 3: Problem Solving Agent

 the priority queue, which pops the element of the queue with the highest priority
according to some ordering function.
 The explored set can be implemented with a hash table to allow efficient checking for
repeated states.

Measuring problem-solving performance

To evaluate an algorithm’s performance in four ways:
• Completeness: Is the algorithm guaranteed to find a solution when there is one?
• Optimality: Does the strategy find the optimal solution,
• Time complexity: How long does it take to find a solution?
• Space complexity: How much memory is needed to perform the search?
 In AI, the graph is often represented implicitly by the initial state, actions, and transition
model and is frequently infinite.
 For these reasons, complexity is expressed in terms of three quantities:
o b, the branching factor or maximum number of successors of any node;
o d, the depth of the shallowest goal DEPTH node (i.e., the number of steps along
the path from the root);
o m, the maximum length of any path in the state space.
o Time is often measured in terms of the number of nodes generated during the
search,
o space in terms of the maximum number of nodes stored in memory.
 For the most part, we describe time and space complexity for search on a tree; for a
graph, the answer depends on how “redundant” the paths in the state space are.
 To assess the effectiveness of a search algorithm, consider
o the search cost— which typically depends on the time complexity but can
also include a term for memory usage—or
o The total cost, which combines the search cost and the path cost of the
solution found. For the problem of finding a route from Arad to Bucharest,
the search cost is the amount of time taken by the search and the solution
cost is the total length of the path in kilometers.

10 | P a g e
 Chapter 3: Problem Solving Agent

Types of search algorithms:

Based on the search problems we can classify the search algorithms into uninformed

(Blind search) search and informed search (Heuristic search) algorithms.

Uninformed search strategies (Blind search or Brute-force approach)

 The strategies have no additional information about states beyond that provided in
the problem definition.
 All they can do is generate successors and distinguish a goal state from a non-goal
state.
 All search strategies are distinguished by the order in which nodes are expanded.
 It is time consuming and more complex.
 Example Breadth First Search, Depth First search.
 The uninformed search does not contain any domain knowledge such as closeness, the
location of the goal.
 It operates in a brute-force way as it only includes information about how to traverse
the tree and how to identify leaf and goal nodes.
 Uninformed search applies a way in which search tree is searched without any
information about the search space like initial state operators and test for the goal, so
it is also called blind search.
 It examines each node of the tree until it achieves the goal node.
 It can be divided into five main types:
o Breadth-first search
o Uniform cost search
o Depth-first search
o Iterative deepening depth-first search
o Bidirectional Search

11 | P a g e
 Chapter 3: Problem Solving Agent

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.
 Breadth-first search is an instance of the general graph-search algorithm (Figure 3.7)
in which the shallowest unexpanded node is chosen for expansion.
 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.

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

12 | P a g e
 Chapter 3: Problem Solving Agent

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.

T (b) = 1+b2+b3+. + bd= O (bd)

Space Complexity: Space complexity of BFS algorithm is given by the Memory size of
frontier which is O(bd).

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 if path cost is a non-decreasing function of the depth of the
node.

Depth-first Search

 Depth-first search always expands the deepest node in the current frontier of the
search tree.
 The search proceeds immediately to the deepest level of the search tree, where the
nodes have no successors. As those nodes are expanded, they are dropped from the
frontier, so then the search “backs up” to the next deepest node that still has
unexplored successors.
 The depth-first search algorithm is an instance of the graph-search algorithm.
 Depth-first search uses a LIFO queue. DFS uses a stack data structure for its
implementation.

13 | P a g e
 Chapter 3: Problem Solving Agent

 A LIFO queue means that the most recently generated node is chosen for expansion.
This must be the deepest unexpanded node because it is one deeper than its parent—
which, in turn, was the deepest unexpanded node when it was selected.
 The properties of depth-first search depend strongly on whether the graph-search or
tree-search version is used.
 The graph-search version, which avoids repeated states and redundant paths, is
complete in finite state spaces because it will eventually expand every node.
 The tree-search version, on the other hand, is not complete.

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:
In the below search tree, we have shown the flow of depth-first search, and it will follow the
order as:

Root node--->Left node > right node.

It will start searching from root node S, and traverse A, then B, then D and E, after traversing
E, it will backtrack the tree as E has no other successor and still goal node is not found. After
backtracking it will traverse node C and then G, and here it will terminate as it found goal node.

14 | P a g e
 Chapter 3: Problem Solving Agent

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,
hence space complexity of DFS is equivalent to the size of the fringe set, 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.

Uniform-cost Search Algorithm:

 Uniform-cost search is a searching algorithm used for traversing a weighted tree or
graph.
 This algorithm comes into play when a different cost is available for each edge.
 The primary goal of the uniform-cost search is to find a path to the goal node which
has the lowest cumulative cost.
 Uniform-cost search expands nodes according to their path costs form the root node.
 It can be used to solve any graph/tree where the optimal cost is in demand.
 A uniform-cost search algorithm is implemented by the priority queue.
 It gives maximum priority to the lowest cumulative cost.
 Uniform cost search is equivalent to BFS algorithm if the path cost of all edges is the
same.
 Uniform-cost search does not care about the number of steps a path has, but only about their
total cost.
 Difference between the Uniform cost search and BFS are
o the ordering of the queue by path cost,
o the goal test is applied to a node when it is selected for expansion rather than
when it is first generated. The reason is that the first goal node that is generated
may be on a suboptimal path.
o a test is added in case a better path is found to a node currently on the frontier.

15 | P a g e
 Chapter 3: Problem Solving Agent

For example:

Consider the problem is to get from Sibiu to Bucharest. The successors of Sibiu are Rimnicu
Vilcea and Fagaras, with costs 80 and 99, respectively. The least-cost node, Rimnicu Vilcea,
is expanded next, adding Pitesti with cost 80 + 97 = 177. The least-cost node is now Fagaras,
so it is expanded, adding Bucharest with cost 99 + 211 = 310. Now a goal node has been
generated, but uniform-cost search keeps going, choosing Pitesti for expansion and adding a
second path to Bucharest with cost 80+ 97+ 101 = 278. Now the algorithm checks to see if this
new path is better than the old one; it is, so the old one is discarded. Bucharest, now with g-
cost 278, is selected for expansion and the solution is returned

Advantages:
 Uniform cost search is optimal because at every state the path with the least cost is
chosen.
Disadvantages:
 It does not care about the number of steps involve in searching and only concerned
about path cost. Due to which this algorithm may be stuck in an infinite loop.

 Completeness: Uniform-cost search is complete, such as if there is a solution, UCS

will find it.
 Time Complexity:

Let C* is Cost of the optimal solution, and ε is each step to get closer to the goal node.
Then the number of steps is = C*/ε+1. Here we have taken +1, as we start from state 0
and end to C*/ε.

16 | P a g e
 Chapter 3: Problem Solving Agent

Hence, the worst-case time complexity of Uniform-cost search is O(b1 + [C*/ε])/.

 Space Complexity: The same logic is for space complexity so, the worst-case
space complexity of Uniform-cost search is O(b1 + [C*/ε]).
 Optimal: Uniform-cost search is always optimal as it only selects a path with the
lowest path cost.

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:
o Standard failure value: It indicates that problem does not have any solution.
o Cut-off failure value: It defines no solution for the problem within a given depth limit.

Advantages:
Depth-limited search is Memory efficient.

Disadvantages:
o Depth-limited search also has a disadvantage of incompleteness.
o It may not be optimal if the problem has more than one solution.

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.

Iterative deepening depth-first Search:

17 | P a g e
 Chapter 3: Problem Solving Agent

 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.

Example: Following tree structure is showing the iterative deepening depth-first search.
IDDFS algorithm performs various iterations until it does not find the goal node. The
iteration performed by the algorithm is given as:
Completeness:

This algorithm is complete is if the branching factor is finite.

Time Complexity:

18 | P a g e
 Chapter 3: Problem Solving Agent

Let's suppose b is the branching factor and depth is d then the worst-case time complexity
is O(bd).

Space Complexity:
The space complexity of IDDFS will be O(bd).

Optimal:
IDDFS algorithm is optimal if path cost is a non- decreasing function of the depth of the
node.

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.
 The motivation is that b d/2 + b d/2 is much less than b d.
 Bidirectional search is implemented by replacing the goal test with a check to see whether
the frontiers of the two searches intersect; if they do, a solution has been found.
 The check can be done when each node is generated or selected for expansion and, with a
hash table, will take constant time.

19 | P a g e
 Chapter 3: Problem Solving Agent

 Bidirectional search requires a method for computing predecessors. When all the actions in
the state space are reversible.

Bidirectional search can use search techniques such as BFS, DFS, DLS, etc.
Advantages:
o Bidirectional search is fast.
o Bidirectional search requires less memory

Disadvantages:
o Implementation of the bidirectional search tree is difficult.
o In bidirectional search, one should know the goal state in advance.

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/2).

Space Complexity: Space complexity of bidirectional search is O(bd/2).

Optimal: Bidirectional search is Optimal.

Comparing uninformed search strategies

20 | P a g e
 Chapter 3: Problem Solving Agent

Evaluation of tree-search strategies. b is the branching factor; d is the depth of the shallowest
solution; m is the maximum depth of the search tree; l is the depth limit. Superscript caveats
are as follows: a complete if b is finite; b complete if step costs ≥ ǫ for positive ǫ; c optimal if
step costs are all identical; d if both directions use breadth-first search.

21 | P a g e