DCIT 313

Introduction to Artificial
Intelligence

Lecture 5 – Search, Games and Problem

Solving
Course Writer: Dr Kofi Sarpong Adu-Manu
Contact Information: ksadu-manu@[Link]

CBAS
School of Physical and Mathematical Sciences
1st Semester 2023
Subsets of Artificial Intelligence
 Motivation
• search strategies are important methods for many
approaches to problem-solving
• the use of search requires an abstract formulation of the
problem and the available steps to construct solutions
• search algorithms are the basis for many optimization and
planning methods
 Objectives
• formulate appropriate problems as search tasks
– states, initial state, goal state, successor functions (operators), cost
• know the fundamental search strategies and algorithms
– uninformed search
• breadth-first, depth-first, uniform-cost, iterative deepening, bi-directional
– informed search
• best-first (greedy, A*), heuristics, memory-bounded, iterative improvement
• evaluate the suitability of a search strategy for a problem
– completeness, time & space complexity, optimality
 What is Search?
• Search is a class of techniques for systematically finding
or constructing solutions to problems.

• Example technique: generate-and-test.

• Example problem: Combination lock.
1. Generate a possible solution.
2. Test the solution.
3. If solution found THEN done ELSE return to step 1.
 Why is search interesting?
• Many (all?) AI problems can be formulated as search
problems!

Examples:
• Path planning
• Games
• Natural Language Processing
• Machine learning
• Genetic algorithms
 Problem-Solving Agents
• agents whose task it is to solve a particular problem
– goal formulation
• what is the goal state
• what are important characteristics of the goal state
• how does the agent know that it has reached the goal
• are there several possible goal states
– are they equal or are some more preferable
– problem formulation
• what are the possible states of the world relevant for solving
the problem
• what information is accessible to the agent
• how can the agent progress from state to state
 Problem Formulation
• formal specification for the task of the agent
– goal specification
– states of the world
– actions of the agent
• identify the type of the problem
– what knowledge does the agent have about the state of the world
and the consequences of its own actions
– does the execution of the task require up-to-date information
• sensing is necessary during the execution
 Problem Types
– single-state problems
• accessible world and knowledge of its actions allow the agent
to know which state it will be in after a sequence of actions
– multiple-state problems
• the world is only partially accessible, and the agent has to
consider several possible states as the outcome of a sequence
of actions
– contingency problems
• at some points in the sequence of actions, sensing may be
required to decide which action to take; this leads to a tree of
sequences
– exploration problems
• the agent doesn’t know the outcome of its actions, and must
 Well-Defined Problems
• problems with a readily available formal specification
– initial state
• starting point from which the agent sets out
– actions (operators, successor functions)
• describe the set of possible actions
– state space
• set of all states reachable from the initial state by any
sequence of actions
– path
• sequence of actions leading from one state in the state space
to another
– goal test
• determines if a given state is the goal state
 Well-Defined Problems (cont.)
– solution
• path from the initial state to a goal state
– search cost
• time and memory required to calculate a solution
– path cost
• determines the expenses of the agent for executing the actions
in a path
• sum of the costs of the individual actions in a path
– total cost
• sum of search cost and path cost
• overall cost for finding a solution
 Selecting States and Actions
• states describe distinguishable stages during the problem-
solving process
– dependent on the task and domain
• actions move the agent from one state to another one by
applying an operator to a state
– dependent on states, capabilities of the agent, and properties of
the environment
• choice of suitable states and operators
– can make the difference between a problem that can or cannot
be solved (in principle, or in practice)
 Selecting States and Actions
• states describe distinguishable stages during the problem-
solving process
– dependent on the task and domain
• actions move the agent from one state to another one by
applying an operator to a state
– dependent on states, capabilities of the agent, and properties of
the environment
• choice of suitable states and operators
– can make the difference between a problem that can or cannot
be solved (in principle, or in practice)
 Example Problems
• toy problems  real-world problems
–  route finding
vacuum world
– 8-puzzle  touring problems
– 8-queens  traveling salesperson
 VLSI layout
– cryptarithmetic
–  robot navigation
vacuum agent
–  assembly sequencing
missionaries and cannibals
 Web search
 Search Algorithms in AI
• Artificial Intelligence is the study of building agents that act
rationally. Most of the time, these agents perform some kind of
search algorithm in the background in order to achieve their tasks.
• A search problem consists of:
– A State Space. Set of all possible states where you can be.
– A Start State. The state from where the search begins.
– A Goal Test. A function that looks at the current state returns whether or not
it is the goal state.
• The Solution to a search problem is a sequence of actions, called
the plan that transforms the start state to the goal state.
• This plan is achieved through search algorithms.
 Search Algorithms in AI
• The search for a solution in an extremely large search tree
presents a problem for nearly all inference systems

• From the starting state there are many possibilities for the
first inference step.

• For each of these possibilities there are again many

possibilities in the next step, and so on
 Search Algorithms in AI
• Depth and branch factor are key to determine the solution
in trees
• Assume the branching factor is a constant equal to 30
and the first solution is at depth 50. The search tree has
3050 7.2 *1073 leaf nodes.
• The number of inference steps may become bigger (taking
into account the level of every leaf node, every inner node
of the tree)
• This corresponds to an inference step
• It requires addition of all nodes over all levels to obtain
the total number of nodes of the search tree
 Search Algorithms in AI
• Computing

• We may then have a search tree of 7.4 *1073 nodes.

Assume we had 10,000 computers capable of performing
a billion inferences per second, then the total computation
for all 7.4 *1073 inferences
 Searching by intuition

A heavily
trimmed search
tree—or: “Where
is my cat?”
 Possible starting
and goal states of the 8-puzzle
8-Puzzle Problem Space
 Example: The 8-puzzle

• states?
• actions?
• goal test?
• path cost?

[Note: optimal solution of n-Puzzle family is NP-hard]

 8-Puzzle
• states
– location of tiles (including blank tile)
• initial state
– any legitimate configuration
• successor function (operators)
– move tile
– alternatively: move blank
• goal test
– any legitimate configuration of tiles
• path cost
– one unit per move

Properties: abstraction leads to discrete configurations, discrete moves,

deterministic
9!/2 = 181,440 reachable states
 Example: n-queens
• Put n queens on an n × n board with no two queens on
the same row, column, or diagonal
 8-Queens
• incremental formulation  complete-state formulation
– states  states
• arrangement of up to 8 queens on the  arrangement of 8 queens on the board
board  initial state
– initial state  all 8 queens on board
• empty board  successor function (operators)
– successor function (operators)  move a queen to a different square
• add a queen to any square  goal test
– goal test  no queen attacked
• all queens on board  path cost
• no queen attacked  irrelevant (all solutions equally valid)
– path cost
• irrelevant (all solutions equally
valid)
 Properties: good strategies can
reduce the number of possible
sequences considerably
• Properties: 3*1014 possible
sequences; can be reduced to 2,057
 8-Queens Refined
• simple solutions may lead to very high search costs
– 64 fields, 8 queens ==> 648 possible sequences
• more refined solutions trim the search space, but may
introduce other constraints
– place queens on “unattacked” places
• much more efficient
• may not lead to a solutions depending on the initial moves
– move an attacked queen to another square in the same column, if
possible to an “unattacked” square
• much more efficient
 Crypt-arithmetic

• states
– puzzle with letters and digits
• initial state
– only letters present
• successor function (operators)
– replace all occurrences of a letter by a digit not used yet
• goal test
– only digits in the puzzle
– calculation is correct
• path cost
– all solutions are equally valid
 Missionaries and Cannibals
– states
• number of missionaries, cannibals, and boats on the banks of a river
• illegal states
– missionaries are outnumbered by cannibals on either bank
– initial states
• all missionaries, cannibals, and boats are on one bank
– successor function (operators)
• transport a set of up to two participants to the other bank
– {1 missionary} | { 1cannibal} | {2 missionaries} | {2 cannibals} |
{1 missionary and 1 cannibal}
– goal test
• nobody left on the initial river bank
– path cost
• number of crossings

also known as “goats and cabbage”, “wolves and sheep”, etc

 Route Finding
• states
– locations
• initial state
– starting point
• successor function (operators)
– move from one location to another
• goal test
– arrive at a certain location
• path cost
– may be quite complex
• money, time, travel comfort, scenery, ...
 Traveling Salesperson
• states
– locations / cities
– illegal states
• each city may be visited only once
• visited cities must be kept as state information
• initial state
– starting point
– no cities visited
• successor function (operators)
– move from one location to another one
• goal test
– all locations visited
– agent at the initial location
• path cost
– distance between locations
 VLSI Layout
• states
– positions of components, wires on a chip
• initial state
– incremental: no components placed
– complete-state: all components placed (e.g. randomly, manually)
• successor function (operators)
– incremental: place components, route wire
– complete-state: move component, move wire
• goal test
– all components placed
– components connected as specified
• path cost
– may be complex
• distance, capacity, number of connections per component
 Robot Navigation
• states
– locations
– position of actuators
• initial state
– start position (dependent on the task)
• successor function (operators)
– movement, actions of actuators
• goal test
– task-dependent
• path cost
– may be very complex
• distance, energy consumption
 Assembly Sequencing
• states
– location of components
• initial state
– no components assembled
• successor function (operators)
– place component
• goal test
– system fully assembled
• path cost
– number of moves
 Example: robotic assembly

• states?: real-valued coordinates of robot joint angles parts of

the object to be assembled

• actions?: continuous motions of robot joints

• goal test?: complete assembly

• path cost?: time to execute

 Searching for Solutions
• traversal of the search space
– from the initial state to a goal state
– legal sequence of actions as defined by successor function (operators)
• general procedure
– check for goal state
– expand the current state
• determine the set of reachable states
• return “failure” if the set is empty
– select one from the set of reachable states
– move to the selected state
• a search tree is generated
– nodes are added as more states are visited
 Search Terminology
• search tree
– generated as the search space is traversed
• the search space itself is not necessarily a tree, frequently it is a graph
• the tree specifies possible paths through the search space
– expansion of nodes
• as states are explored, the corresponding nodes are expanded by applying the
successor function
– this generates a new set of (child) nodes
• the fringe (frontier) is the set of nodes not yet visited
– newly generated nodes are added to the fringe
– search strategy
• determines the selection of the next node to be expanded
• can be achieved by ordering the nodes in the fringe
– e.g. queue (FIFO), stack (LIFO), “best” node w.r.t. some measure (cost)
 Example: Graph Search
A 1 D
4 3

1 1 1 3

S 5 C 2 G
3 2 0

1 3 3 4
B E
2 1
2

• the graph describes the search (state) space

– each node in the graph represents one state in the search space
• e.g. a city to be visited in a routing or touring problem
• this graph has additional information
– names and properties for the states (e.g. S, 3)
– links between nodes, specified by the successor function
• properties for links (distance, cost, name, ...)
 Terminology - State
• Being in state s, an action a1 leads to a new state s′. Thus s
′ = a1(s). A different action may lead to state s″, in other
words: s″ = a2(s).
• Recursive application of all possible actions to all states,
beginning with the starting state, yields the search tree
Recap – going forward
 The 8-puzzel recap
Applied to the 8-puzzle, we get
• State: 3X3 matrix S with the values 1, 2, 3, 4, 5, 6, 7, 8
(once each) and one empty square.
• Starting state: An arbitrary state.
• Goal state: An arbitrary state
• Actions: Movement of the empty square Sij to the left (if j
1), right (if j 3), up (if i 1), down (if i 3).
• Cost function: The constant function 1, since all actions
have equal cost.
• State space: The state space is degenerate in domains that
are mutually unreachable
Terms defined..
 Branching factor
• For a given depth d and node count n, the effective
branching factor can be calculated by solving the
equation:

• for b because a tree with constant branching factor and

depth d has a total of nodes
 Branching Factor - 2

We are given a map as a

graph with cities as nodes
and highway connections
between the cities as
weighted edges with
distances. We are looking
for an optimal route from
city A to city B. The
description of the
corresponding schema
reads
The graph of southern Germany as an example
of a search task with a cost function
 Branching factor -3
• State: A city as the current location of the traveler.
• Starting state: An arbitrary city.
• Goal state: An arbitrary city.
• Actions: Travel from the current city to a neighboring
city.
• Cost function: The distance between the cities. Each
action corresponds to an edge in the graph with the
distance as the weight.
• State space: All cities, that is, nodes of the graph.
 Optimal Search

• The 8-puzzle problem is deterministic, which means that every action leads
from a state to a unique successor state.
• It is furthermore observable, that is, the agent always knows which state it is
in.
• In route planning in real applications both characteristics are not always
given.
• The action “Drive from Munich to Ulm” may—for example because of an
accident—lead to the successor state “Munich”.
• It can also occur that the traveler no longer knows where he is because he got
lost.
 Search Cost and Path Cost
• the search cost indicates how expensive it is to
generate a solution
– time complexity (e.g. number of nodes generated) is usually the
main factor
– sometimes space complexity (memory usage) is considered as
well
• path cost indicates how expensive it is to execute the
solution found in the search
– distinct from the search cost, but often related
• total cost is the sum of search and path costs
 Selection of a Search Strategy
• most of the effort is often spent on the selection of an
appropriate search strategy for a given problem
– uninformed search (blind search)
• number of steps, path cost unknown
• agent knows when it reaches a goal
– informed search (heuristic search)
• agent has background information about the problem
– map, costs of actions
 Search Strategies
 Local Search and
• Uninformed Search
– breadth-first Optimization
–
 hill-climbing
depth-first
 simulated annealing
– uniform-cost search  local beam search
– depth-limited search  genetic algorithms
– iterative deepening  constraint satisfaction
– bi-directional search  Search in Continuous
• Informed Search Spaces
– best-first search  Non-deterministic Actions
– search with heuristics  Partial Observations
– memory-bounded search  Online Search
– iterative improvement search
 Breadth-first search
• breadth-first search (BFS): Finds a path between two nodes by
taking one step down all paths and then immediately backtracking.
– Often implemented by maintaining a queue of vertices to visit.

• BFS always returns the shortest path (the one with the fewest
edges) between the start and the end vertices.
– to b: {a, b}
a b c
– to c: {a, e, f, c}
– to d: {a, d}
– to e: {a, e} d e f
– to f: {a, e, f}
– to g: {a, d, g} g h
– to h: {a, d, h}
 Breadth-First Search
• all the nodes reachable from the current node are explored
first
– achieved by the TREE-SEARCH method by appending newly
generated nodes at the end of the search queue

function BREADTH-FIRST-SEARCH(problem) returns solution

return TREE-SEARCH(problem, FIFO-QUEUE())

Time Complexity bd+1

Space Complexity bd+1 b branching factor

Completeness yes (for finite b) d depth of the tree

Optimality yes (for non-negative

path costs)
© 2000-2012 Franz Kurfess Search
Breadth-First Search
 BFS pseudocode (Alternative)
function bfs(v1, v2):
queue := {v1}.
mark v1 as visited. a b c

while queue is not empty: d e f

v := [Link]().
if v is v2:
a path is found! g h

for each unvisited neighbor n of v:

mark n as visited.
[Link](n).
// path is not found.

• Trace bfs(a, f) in the above graph.

 BSF – third level nodes

“GoalReached” calculates whether the argument is a goal node, and “Successors”

calculates the list of all successor nodes of its argument.
 BSF Analysis
• Breadth-first search completely searches through every depth and
reaches every depth in finite time, it is complete if the branching
factor b is finite.
• The optimal (that is, the shortest) solution is found if the costs of all
actions are the same. Computation time and memory space grow
exponentially with the depth of the tree. For a tree with constant
branching factor b and depth d, the total compute time is thus given
by

• Although only the last level is saved in memory, the memory space
requirement is also O(bd)
 BFS Problem
Which solution would DFS find to move from node S to node
G if run on the graph below?
 Sample Solution

Path: S -> A -> B -> C -> G

 BFS observations
• optimality: a b c
– always finds the shortest path (fewest edges).
– in unweighted graphs, finds optimal cost path. d e f
– In weighted graphs, not always optimal cost.
g h
• retrieval: harder to reconstruct the actual sequence of vertices or
edges in the path once you find it
– conceptually, BFS is exploring many possible paths in parallel, so it's not easy
to store a path array/list in progress
– solution: We can keep track of the path by storing predecessors for each vertex
(each vertex can store a reference to a previous vertex).

• DFS uses less memory than BFS, easier to reconstruct the path once
found; but DFS does not always find shortest path. BFS does.
 Depth-first search
• depth-first search (DFS): Finds a path between two vertices by
exploring each possible path as far as possible before backtracking.
– Often implemented recursively.
– Many graph algorithms involve visiting or marking vertices.

• Depth-first paths from a to all vertices (assuming ABC edge order):

– to b: {a, b}
– to c: {a, b, e, f, c} a b c
– to d: {a, d}
– to e: {a, b, e} d e f
– to f: {a, b, e, f}
– to g: {a, d, g} g h
– to h: {a, d, g, h}
 Depth-First Search
• In depth-first search only a few nodes are stored in
memory at one time.
• After the expansion of a node only its successors are
saved, and the first successor node is immediately
expanded.
• Thus the search quickly becomes very deep.
• Only when a node has no successors and the search fails
at that depth is the next open node expanded via
backtracking to the last branch.
 DFS Analysis
• Depth-first search requires much less memory than
breadth-first search because at most b nodes are saved at
each depth.
• Thus we need at most b*d memory cells.
• However, depth-first search is not complete for infinitely
deep trees because depth-first search runs into an infinite
loop when there is no solution in the far left branch.
• In the case of a finitely deep search tree with depth d, a
total of about bd nodes are generated – computational time
grows
Algorithm for depth-first search
 DFS pseudocode (Alternative)
function dfs(v1, v2):
dfs(v1, v2, { }).
a b c
function dfs(v1, v2, path):
path += v1. d e f
mark v1 as visited.
if v1 is v2: g h
a path is found!
for each unvisited neighbor n of v1:
if dfs(n, v2, path) finds a path: a path is found!
path -= v1. // path is not found.

• The path param above is used if you want to have the

path available as a list once you are done.
– Trace dfs(a, f) in the above graph.
Execution of depth-first search
Traversing DFS
 DFS observations
• discovery: DFS is guaranteed to a b c
find a path if one exists.
d e f

• retrieval: It is easy to retrieve exactly g h

what the path is (the sequence of
edges taken) if we find it

• optimality: not optimal. DFS is guaranteed to find a

path, not necessarily the best/shortest path
– Example: dfs(a, f) returns {a, d, c, f} rather than {a, d, f}.
 Iterative Deepening
• We begin the depth-first search with a depth limit of 1. If
no solution is found, we raise the limit by 1 and start
searching from the beginning

Schematic representation of the development of the search

tree in iterative deepening with limits from 1 to 7. The
breadth of the tree corresponds to a branching factor of 2
 Iterative Deepening
• Iterative raising of the depth limit is called iterative
deepening

Analysis:
• The memory requirement is the same as in depth-first
search.
• One could argue that repeatedly re-starting depth-first
search at depth zero causes a lot of redundant work.
• For large branching factors this is not the case.
IDDFS
IDDFS
 Determing Number of Nodes
Let Nb(d) be the number of nodes of a search tree with branching
factor b and depth d and dmax be the last depth searched. The last
tree searched contains:
Searching all trees
 Cycle Check
Comparison of the uninformed search algorithms. (*) means that the
statement is only true given a constant action cost. ds is the maximal
depth for a finite search tree
 Heuristic Search
• Heuristics are problem-solving strategies which in many
cases find a solution faster than uninformed search.

• Heuristic decisions are closely linked with the need to

make real-time decisions with limited resources.

• A heuristic evaluation function f(s) for states is used to

mathematically model a heuristic.
Heuristics Search Algorithm
 HSA
• The best heuristic would be a function that calculates the
actual costs from each node to the goal.
• To do that, however, would require a traversal of the
entire search space, which is exactly what the heuristic is
supposed to prevent.
• An interesting idea for finding a heuristic is simplification
of the problem.
• The original task is simplified enough that it can be solved
with little computational cost.
• Cost estimate function we denote h
 Greedy Search (Best-first Search)
• Greedy best-first search algorithm always selects the path which
appears best at that moment.
• It is the combination of depth-first search and breadth-first search
algorithms. It uses the heuristic function and search.
• Best-first search allows us to take the advantages of both
algorithms. With the help of best-first search, at each step, we can
choose the most promising node.
• In the best first search algorithm, we expand the node which is
closest to the goal node and the closest cost is estimated by
heuristic function, i.e. f(n) = g(n), were, h(n) = estimated cost from
node n to the goal.
• The greedy best first algorithm is implemented by the priority
queue.
 Best first search algorithm
Step 1: Place the starting node into the OPEN list.
Step 2: If the OPEN list is empty, Stop and return failure.
Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n),
and places it in the CLOSED list.
Step 4: Expand the node n, and generate the successors of node n.
Step 5: Check each successor of node n, and find whether any node is a goal node or
not. If any successor node is goal node, then return success and terminate the search,
else proceed to Step 6.
Step 6: For each successor node, algorithm checks for evaluation function f(n), and
then check if the node has been in either OPEN or CLOSED list. If the node has not
been in both list, then add it to the OPEN list.
Step 7: Return to Step 2.
 Advantages/Disadvantages
Advantages
• Best first search can switch between BFS and DFS by
gaining the advantages of both the algorithms.
• This algorithm is more efficient than BFS and DFS
algorithms.
Disadvantages
• It can behave as an unguided depth-first search in the
worst case scenario.
• It can get stuck in a loop as DFS.
• This algorithm is not optimal.
 Example
Consider the below search
problem, and we will
traverse it using greedy
best-first search.
At each iteration, each
node is expanded using
evaluation function
f(n)=h(n), which is given
in the below table.
 Solution
• In this search example,
we are using two lists
which are OPEN and
CLOSED Lists.

• Following are the

iteration for traversing
the above example.
 Solution
Expand the nodes of S and put in the CLOSED list
• Initialization: Open [A, B], Closed [S]
• Iteration 1: Open [A], Closed [S, B]
• Iteration 2: Open [E, F, A], Closed [S, B]
: Open [E, A], Closed [S, B, F]
• Iteration 3: Open [I, G, E, A], Closed [S, B, F]
: Open [I, E, A], Closed [S, B, F, G]
• Hence, the final solution path will be: S----> B----->F----> G
• Time Complexity: The worst case time complexity of Greedy best first search is
O(bm).
• Space Complexity: The worst case space complexity of Greedy best first search
is O(bm). Where, m is the maximum depth of the search space.
• Complete: Greedy best-first search is also incomplete, even if the given state
space is finite.
• Optimal: Greedy best first search algorithm is not optimal.
 A* Search Algorithm
• A* search is the most commonly known form of best-first
search.
• It uses heuristic function h(n), and cost to reach the node n
from the start state g(n).
• A* search algorithm finds the shortest path through the
search space using the heuristic function.
• In A* search algorithm, we use search heuristic as well as
the cost to reach the node.
A -Search
★
 Algorithm of A* search
• Step1: Place the starting node in the OPEN list.
• Step 2: Check if the OPEN list is empty or not, if the list is empty then return
failure and stops.
• Step 3: Select the node from the OPEN list which has the smallest value of
evaluation function (g+h), if node n is goal node then return success and stop,
otherwise
• Step 4: Expand node n and generate all of its successors, and put n into the
closed list. For each successor n', check whether n' is already in the OPEN or
CLOSED list, if not then compute evaluation function for n' and place into Open
list.
• Step 5: Else if node n' is already in OPEN and CLOSED, then it should be
attached to the back pointer which reflects the lowest g(n') value.
• Step 6: Return to Step 2.
 Dis-(ad)vantages
Advantages
• A* search algorithm is the best algorithm than other search
algorithms.
• A* search algorithm is optimal and complete.
• This algorithm can solve very complex problems.
Disadvantages
• It does not always produce the shortest path as it mostly based on
heuristics and approximation.
• A* search algorithm has some complexity issues.
• The main drawback of A* is memory requirement as it keeps all
generated nodes in the memory, so it is not practical for various
large-scale problems.
Example
In this example, we will
traverse the given graph
using the A* algorithm.
The heuristic value of all
states is given in the below
table so we will calculate
the f(n) of each state using
the formula f(n)= g(n) +
h(n), where g(n) is the cost
to reach any node from
start state.
Solution
• Initialization: {(S, 5)}
• Iteration1: {(S--> A, 4), (S-->G, 10)}

• Iteration2: {(S--> A-->C, 4), (S--> A-->B,

7), (S-->G, 10)}

• Iteration3: {(S--> A-->C--->G, 6), (S-->

A-->C--->D, 11), (S--> A-->B, 7), (S-->G,
10)}

• Iteration 4 will give the final result, as

S--->A--->C--->G it provides the optimal
path with cost 6.
 Points to Remember
• A* algorithm returns the path which occurred first, and it
does not search for all remaining paths.
• The efficiency of A* algorithm depends on the quality of
heuristic.
• A* algorithm expands all nodes which satisfy the
condition f(n)
• A* algorithm is complete as long as:
– Branching factor is finite.
– Cost at every action is fixed.
 Points to remember
A* search algorithm is optimal if it follows below two conditions:

– Admissible: the first condition requires for optimality is that h(n) should be
an admissible heuristic for A* tree search. An admissible heuristic is
optimistic in nature.
– Consistency: Second required condition is consistency for only A* graph-
search.
• If the heuristic function is admissible, then A* tree search will always find the
least cost path.

• Time Complexity: The time complexity of A* search algorithm depends on

heuristic function, and the number of nodes expanded is exponential to the depth
of solution d. So the time complexity is O(bd), where b is the branching factor.
• Space Complexity: The space complexity of A* search algorithm is O(bd)
 Group Activity
• Write a Java Program that asks the user to select of any of
these search algorithms: BFS, DFS, Iterative depeening,
and A* Search

• Perform searching of items selected by the user using any

of the above search algorithms and the response time it
takes any of the above algorithms to locate the search
item.
 Reference
Ertel, W., & Black, N. T. (2011). Introduction to
Artificial Intelligence. Berlin: Springer.
Acknowledgement