Chapter 3: Problem Solving and

Search

1
Problem = (S, s, A, f, g, c)
 Problem = (S, s, A, f, g, c)
S = state space( i.e.., all states reachable from the initial state.)
s = initial state
A = actions
f = state change function(successor function) f: S x A -> S
g = goal test function g: S -> { true, false}
c = cost function c: S x A x S -> R

Note:
• Successor function: description of possible actions; a set of
operators.
•Search space or State space(path) forms a graph in which the
nodes are states and the arcs between nodes are actions.
•In state space, a path is a sequence of states connected by a
sequence of actions.
2
 Problem Solving and Search
 Problems are typically defined in terms of state, and
solution corresponds to goal states.
 Problem solving agent:
– Agent knows world dynamics
– World state is finite, small enough to enumerate
– World is deterministic
– Utility for a sequence of states is a sum over path.
– Agent knows current state

3
 Problem Solving and Search
 Example of Problem: Route Planning in A Map
– A map is a graph where nodes are cities and links
are roads. This is an abstraction of the real world.
– Map gives world dynamics: starting at city X on the
map and taking some road gets to you to city Y.
– World(e.g., set of cities) is finite and enumerable.
– World is deterministic: taking a given road from a
given city leads to only one possible destination.
– Utility for a sequence of states is usually either total
distance traveled on the path or total time for the
path.
– We assume current state is known. 4
 Problem Solving and Search
Problem solving using search technique performs two sequence of
steps:

I) Define the problem - Given problem is identified with its

required initial and goal state.

II)Analyze the problem - The best search technique for the given
problem is chosen from different AI search technique which
derives one or more goal state in minimum number of states.

5
 Problem Solving and Search

 Problem solving steps: the sequence of steps done by the intelligent agent
to maximize the performance measure:
a) Goal formulation - based on current situation it is the first step in
problem solving.
b) Problem formulation - is the process of deciding what actions and
states to consider and follows goal formulation(given a goal).
c) Search - is the process of finding different possible sequence of
actions that lead to state of known value, and choosing
the best one from the states. (sequence of actions/path
to reach the goal i.e., solution to the problem.) 6
 Problem Solving and Search
Problem solving steps …:
d) Solution - a search algorithm takes a problem as input and
returns a solution in the form of action sequence.
e)Execution phase - if the solution exists, the action it
recommends can be carried out.

7
 A simple problem solving agent
Function SIMPLE-PROBLEM-SOLVING-AGENT(p) returns action
input : p, a percept
static: s, an action sequence, initially empty
state, some description of the current world state
g, a goal initially null
problem, a problem formulation
state <- UPDATE-STATE(state, p)
if s is empty then
g <- FORMULATE-GOAL(state)
problem <-FORMULATE-PROBLEM(state, g)
s <- SEARCH(problem)
action <- RECOMMENDATION(s, state)
s <- REMAINDER(s, state) 8

return action
 Problem Solving and Search

• Example: Goal formulation :

•Often the first step in problem solving is to simplify the
performance measure that the agent is trying to maximize.
•A "goal" is a set of desirable world-states.
•"Goal formulation" means ignoring all other
Goal formulation
aspects of the
current state and the performance measure, and choosing a
goal.
Example: if you are in Arad (Romania) and your visa will expire
tomorrow, your goal is to reach Bucharest airport.
10
Problem Solving and Search

11
 State-Space Problem Formulation
Example: Traveling in Romania: On holiday in Romania; currently in
Arad. Flight leaves tomorrow from Bucharest.
•Initial State: "at Arad“
• Formulate goal: be in Bucharest
• Formulate problem:
• states: various cities Goal formulation
• actions: drive between cities [S(x) = set of action–state pairs
e.g., S(Arad) = {<Arad  Zerind, Zerind>, … }
• Find solution: A solution is a sequence of actions leading from the
initial state to a goal state. E.g. sequence of cities,i.e. Arad, Sibiu,
Fagaras, Bucharest. 12
 State-Space Problem Formulation
Example: Traveling in Romania-Tree search

Goal formulation

13
• Problem formulation :means choosing a relevant set of states,
operators for moving from one state to another, the goal test
function and the path cost function.
• The relevant set of states should include the current state,
which is the initial state, and (at least one!) goal state.

• The operators correspond to "imaginary" actions that the

agent might take.

• The goal test function is a function which determines if a

single state is a goal state.

• The path cost is the sum of the cost of individual actions

along a path from one state to another. 14
• Types of problem: problem can be classified under anyone of the
following four types which depend on two important properties. They are:
(i) Amount of knowledge, of the agent on the state and action description.
(ii) How the agent is connected to its environment through its percepts
and actions?
• In conclusive, not all problems are created equally.
•The four types of problem:
(i) Single state problem:
Consider the vacuum cleaner world.
•Let's suppose that the world has just
two rooms. The robot can be in either
room and there can be dirt in zero(or
none), one, or two rooms.
•Goal formulation: intuitively, we want
all the dirt cleaned up. Formally, the goal 15

is { state 7, state 8 }.
• Problem formulation: we already know what the set of all
possible states is. The operators are "move left", "move right",
and “suck".
E.g., Single-state, start in #5.
Solution: [Right, Suck]

16
In general, the single state problem is:
• Exact prediction is possible.
• State is known exactly after any sequence of actions.
• Accessibility of the world all essential information can be
obtained through sensors.
• Consequences of actions are known to the agent.
• Goal for each known initial state, there is a unique goal state that
is guaranteed to be reachable via an action sequence.
• Simplest case, but severely restricted.
(ii) Multiple state problem
Suppose that the robot has no sensor that can tell it which room it is
in and it doesn't know where it is initially.
17
 •Sensorless (multi-state):deterministic, inaccessible
start in {1,2,3,4,5,6,7,8}
e.g. Right goes to {2,4,6,8}
Solution?
[Right,Suck,Left,Suck]

E.g., walking in a dark room

•If you are at the door, going straight
will lead you to the kitchen.
•If you are at the kitchen, turning left
leads you to the bedroom.

18
• In general, the multi state problem is:
•Semi-exact prediction is possible.
•State is not known exactly, but limited to a set of possible states
after each action.
•Accessibility of the world
• not all essential information can be obtained through sensors.
• reasoning can be used to determine the set of possible states.
•Consequences of actions are not always or completely known to
the agent; actions or the environment might exhibit randomness.
•Goal due to ignorance, there may be no fixed action sequence that
leads to the goal.
19
•Less restricted, but more complex.
(iii)Contingency problem
•Nondeterministic, inaccessible:
Suck may
dirty a clean carpet.
• Partially observable (local
sensing): Location, dirt or clean at
current location.
• Percept: [L, Clean], i.e., start in
#5 or #7
Solution
• No fixed action sequence that
guarantees solution to this problem
• Solving this problem requires
sensing during execution!
• [Right, if dirt then Suck]
20
(iv)Exploration problem
• Effects of actions are unknown.
• State -the set of possible states may be unknown.
• Accessibility of the world some essential information may be
obtained through sensors only at execution time.
• Consequences of actions may not be known at planning time.
• Goal can’t be completely formulated in advance because states and
consequences may not be known at planning time.
• Discovery from hidden knowledge what states exist.
• Experimentation what are the outcomes of actions.
• Learning remember and evaluate experiments.
21
 Well-Defined Problems Properties:
• Exact formulation of problems and solutions
• Initial state
• current state / set of states, or the state at the beginning of the
problem-solving process must be known to the agent.
• Operator
• description of an action.
• State space
• set of all states reachable from the initial state by a possible
sequence of actions.
• Path in the search space
• sequence of actions between two states.
• Goal test
• determines if the agent has reached a goal state.
• Path cost
• function that assigns a cost to a path usually the sum of the
costs of actions along. 22
 Performance Measuring for problem solving:
•Success
• Has a solution been found?
• completeness: will it find a solution one if one exists?
•quality
• Is it a good solution?
• What are the criteria?
• time efficiency: number of nodes generated
• space efficiency: maximum number of nodes in memory
•optimal solution
• may be difficult to find and not necessary
• does it always find a least-cost solution?
•cost
• sum of
• search cost (time, resources to find a
solution)
• path cost: e.g. ., sum of distances, number of actions executed,
etc.
• c(x,a,y) is the step cost (of taking action a to go from state 23
x to y) assumed c≥ 0.
 Vacuum World State Space Graph
•simplified version: two squares, either dirty or clean, vacuum has
sensors.
•States: integer dirt and robot location (ignore dirt amounts);
location of vacuum, squares dirty or clean
•Operators: move left, move right, suck
•goal test: all squares clean
•path cost:1 unit per action

24
 The 8-puzzle state space graph
•States: locations of tiles[ 8 tiles and one blank space].
•Initial state: any arrangement of the nine tiles.
• actions: move blank left, right, up, down
• goal test: goal state (given)
• path cost: 1 per move

•Distance(number of moves)
to goal:
1. Number of misplaced tiles( 8 in example above ).
2. Sum of Manhattan distance of tile to its goal location(18 in example
above). Manhattan distance between (x1,y1) and (x2,y2) is |x1-
25
x2|+|y1-y2|. This is much better at predicting actual number of
moves.
 Search Tree for the 8 puzzle problem:The (implicit) search tree
•

26
 But this tree is only IMPLICITLY available !!
Example: 8-queens problem

27
Example: 8-queens problem
states : -any arrangement of n<=8 queens
-or arrangements of n<=8 queens in leftmost n
columns, 1 per column, such that no queen
attacks any other.

initial state: no queens on the board

Actions: -add queen to any empty square

-or add queen to leftmost empty square such that it is
not attacked by other queens.

goal test: 8 queens on the board, none attacked.

path cost: 1 per move

28
Example: 8-queens problem:12 Unique Solutions

29
 1. Choice of the Rules
Example: The water jugs problem:

• Given: 2 jugs: 4l 3l

• Problem: fill the 4 l jug with 2 l of water.

 Representation:
 a state:
 [content of large jug, content of small jug]
 initial state:
 [ 0, 0 ]
 goal state:
 [ 2, x ] 30
 Rules for the jugs example(1):
1 (x,y)  (4,y) Fill the 4-gallon jug
if x < 4

2 (x,y)  (x,3) Fill the 3-gallon jug

if y < 3

3 (x,y)  (x – d,y) Pour some water out of the 4-gallon jug

if x > 0

4 (x,y)  (x,y – d) Pour some water out of the 3-gallon jug

if y > 0

5 (x,y)  (0,y) Empty the 4-gallon jug on the ground

if x > 0

6 (x,y)  (x,0) Empty the 3-gallon jug on the ground

if y > 0

7 (x,y)  (4,y – (4 – x))

Pour water from the 3-gallon jug into the 4-gallon
31 if x + y ≥ 4 and y > 0 jug until the 4-gallon jug is full
 Rules for the jugs example (2):
8 (x,y)  (x – (3 – y),3) Pour water from the 4-gallon jug into the 3-gallon
if x + y ≥ 3 and x > 0 jug until the 3-gallon jug is full

9 (x,y)  (x + y, 0)
if x + y ≤ 4 and y > 0 Pour all the water from the 3-gallon jug into the
4-gallon jug

10 (x,y)  (0, x + y)
if x + y ≤ 3 and x > 0 Pour all the water from the 4-gallon jug into the
3-gallon jug

32
 One Solution to the Water Jug Problem
Gallons in the 4- Gallons in the 3- Rule Applied
Gallon Jug Gallon Jug

0 0 2
0 3 9
3 0 2
3 3 7
4 2 5
0 2 9

2 0 Goal
33
 Part of the state space in Graph:

[ 0, 0 ] Fill small

[ 0, 3 ] Empty small
in large
[ 0, 0 ]
[ 3, 0 ]

Fill small
[ 3, 3 ]
[ 0, 3 ]

LOOP ! Fill large

[ 4, 2 ]
from small
[ 0, 0 ] Empty large
[ 0, 2 ]

34

[ 2, 0 ] Empty small in large

 Cannibals and Missionaries problem.
You have 3 cannibals and 3 missionaries, all who have agreed they
want to get to the other side of the river. You don’t want to ever
have more cannibals than missionaries on one side alone or the
cannibals may eat the missionaries. The boat available only holds
two people.

Left Bank Right Bank 35

River
 Cannibals and Missionaries problem.
Assumptions :
1. Number of trips is not restricted
2. Both the missionary and cannibal can row the boat
States: A state consists of an ordered sequence of two numbers
representing the number of missionaries and cannibals
Example : (i,j) = (3,3) three missionaries and three cannibals
Initial state: (i,j) = (3,3) in one side of the river
Successor function: The possible move across the river are:
1. One Missionary and One Cannibal
2. Two Missionaries
3. Two Cannibals
4. One Missionary
5. One Cannibal
•Searching for a state: apply all applicable moves to the current state to
generate a new state, and repeat. 36
 Cannibals and Missionaries problem.
One solution:
Initial State: 3m3cb 0m0c
Send 2c: 3m1c 0m2cb
Return 1c 3m2cb 0m1c
Send 2c 3m0c 0m3cb
Return 1c 3m1cb 0m2c
Send 2m 1m1c 2m2cb
Return 1m1c 2m2cb 1m1c
Send 2m 0m2c 3m1cb
Return 1c 0m3cb 3m0c
Send 2c 0m1c 3m2cb
Return 1c 0m2cb 3m1c 37

Send 2c 0m0c 3m3cb

Note: the space grows exponentially; difficult and almost
impossible to enumerate for large spaces, at Least to find a
goal state (in this case, the goal state is when all 6 people
are on the other side of the river).

38
Assignment One: The Farmer, Wolf, Goat, and Cabbage
Problem[ 20%]
The FWGC problem is stated as follows:
A farmer with his wolf, goat, and cabbage come to the edge of a
river they wish to cross. There is a boat at the river’s edge, but, of
course, only the farmer can row. The boat also can carry only two
things (including the rower) at a time. If the wolf is ever left alone
with the goat, the wolf will eat the goat; similarly, if the goat is left
alone with the cabbage, the goat will eat the cabbage. Devise a
sequence of crossings of the river so that all four characters arrive
safely on the other side of the river.
• { States, Initial state, successor functions, Goal test, path cost}
• Develop rules for the successor function and show the rules
with graph.
• Write a java or C++ program for the rules you have developed.
• Write a test program.
39
 Evaluation of search strategies
 Search algorithms are commonly evaluated according to the
following four criteria:
– Completeness: does it always find a solution if one exists?
– Time complexity: how long does it take as a function of number
of nodes?
– Space complexity: how much memory does it require?
– Optimality: does it guarantee the least-cost solution?
 Time and space complexity are measured in terms of:
– b – max branching factor of the search tree
– d – depth of the least-cost solution
– m – max depth of the search tree (may be infinity) 40
 Uninformed Search Strategies
 Uninformed Search:
– Use only information available in the problem formulation
– Methods that do not use any specific knowledge about the
problem:
• Depth-first
• Breadth-first
• Depth-limited
• Uniform-cost
• Iterative deepening

41
 Depth-first
Image from Russel & Norvig, AIMA, 2003 • Keeps O(bd) nodes in memory.
• Requires a depth limit to avoid infinite
paths
(limit is 3 in the figure).
• Incomplete (is not guaranteed to find a
solution)
• Not optimal
• Linear space complexity (good)
• Exponential time complexity
• Black nodes are removed from memory

b = branching factor, d = depth

Black nodes are removed from memory
 4 4
3 A B C

S 5 5
G
4
D 2 E F 3
4

1. QUEUE <-- path only containing the root;

2. WHILE QUEUE is not empty

AND goal is not reached

DO remove the first path from the QUEUE;

create new paths (to all children);
reject the new paths with loops;
add the new paths to front of QUEUE;

3. IF goal reached
THEN success;
ELSE failure;
43
 Trace of depth-first for running example:
 (S) S removed, (SA,SD) computed and added

 (SA, SD) SA removed, (SAB,SAD,SAS) computed, (SAB,SAD) added

 (SAB,SAD,SD) SAB removed, (SABA,SABC,SABE) computed,

(SABC,SABE) added

 (SABC,SABE,SAD,SD) SABC removed, (SABCB) computed, nothing

added

 (SABE,SAD,SD) SABE removed, (SABEB,SABED,SABEF)

computed, (SABED,SABEF)added

 (SABED,SABEF,SAD,SD) SABED removed,

(SABEDS,[Link]) computed, nothing added

 (SABEF,SAD,SD) SABEF removed, (SABEFE,SABEFG)

computed, (SABEFG) added

 (SABEFG,SAD,SD) goal is reached: reports success

44
 Note: does NOT find the shortest path
A 4 B 4 C
3
S 5 5
G
4 D E F
2 3

3 S 4
4 A 5 5
D 2

4
B D A E
5 2 4 5 4
C 2 E 4 5 E 4 4
B 5 4
B4 F
3
D F B F C E A C G
3 4 3 4
G C G F
3
G
45
 Breadth-first
Image from Russel & Norvig, AIMA, 2003

• Breadth-first finds the solution that is closest (in the graph) to the start node
(always expands the shallowest node).
• Keeps O(bd) nodes in memory  exponential memory requirement!
• Complete (finds a solution if there is one)
• Not necessarily optimal (optimal if cost is the same for each step)
• Exponential space complexity (very bad)
• Exponential time complexity
Nodes marked with open circles = fringe = in the memory

b = branching factor, d = depth

 Breadth-first search:
S

A D  Move downwards,
level by level, until
B D A E goal is reached.

C E E B B F

D F B F C E A C G

G C G F
G

47
 Breadth-first algorithm:
1. QUEUE <-- path only containing the root;

2. WHILE QUEUE is not empty

AND goal is not reached

DO remove the first path from the QUEUE;

create new paths (to all children);
reject the new paths with loops;
add the new paths to back of QUEUE;

3. IF goal reached
THEN success; ONLY
ELSE failure; DIFFERENCE !

48
 Trace of breadth-first for running example:
(S) S removed, (SA,SD) computed and added

 (SA, SD) SA removed, (SAB,SAD,SAS) computed,

(SAB,SAD) added
 (SD,SAB,SAD) SD removed, (SDA,SDE,SDS) computed,
(SDA,SDE) added
 (SAB,SAD,SDA,SDE) SAB removed, (SABA,SABE,SABC)
computed, (SABE,SABC) added
 (SAD,SDA,SDE,SABE,SABC) SAD removed,
(SADS,SADA, SADE) computed, (SADE) added etc, until
QUEUE contains:
 (SABED,SABEF,SADEB,SADEF,SDABC,SDABE,SDEBA,SDEBC,
SDEFG) goal is reached: reports success
49
 Speed (breadth-first)
 If a goal node is found on depth m of the tree, all nodes
up till that depth are created.

m
d
b
G

 Thus: O(bm)
 Note: depth-first would also visit deeper nodes.
50
 Depth-limited search:
1. DEPTH <-- <some natural number>
QUEUE <-- path only containing the root;

2. WHILE QUEUE is not empty

AND goal is not reached

DO remove the first path from the QUEUE;

IF path has length smaller than DEPTH
create new paths (to all children);
reject the new paths with loops;
add the new paths to front of QUEUE;

3. IF goal reached
THEN success;
ELSE failure;

51
 Informed search:
 Informed search: Use heuristics to guide the search
a) Best first:
– Greedy search -- queue first nodes that maximize heuristic
“desirability” based on estimated path cost from current node to
goal;
– A* search – queue first nodes that minimize sum of path cost so
far and estimated path cost to goal.
• An informed search strategy uses problem-specific knowledge beyond
the definition of the problem itself and it can find solutions more
efficiently than an uninformed strategy. The node with the lowest
evaluation is selected for expansion, because the evaluation measures
distance to the goal. 52
 Implementation of Best-first Search using General
Search Algorithm
function BEST-FIRST-SEARCH(problem, EVAL-FN) returns a
solution sequence
inputs: problem, a problem
EVAL-FN, an evaluation function
QUEUEING -FN<- a function that orders nodes by EVAL-FN
return TREE-SEARCH(problem, QUEUEING-FN)
• The key component of these algorithms is a heuristic functions
denoted h(n)
– h(n) = estimated cost of the cheapest path from node n to a goal
node.
– One constraint: if n is a goal node, then h(n) = 0 53
 Implementation of Best-first Search
• The two types of evaluation functions are:
(i) Expand the node closest to the goal state using estimated cost as
the evaluation is called greedy best first search.
(ii) Expand the node on the least cost solution path using estimated
cost and actual cost as the evaluation function is called A*search.
• h(n)= estimated cost of the cheapest path from the state at
node n to a goal state.
• Algorithm :
Function GREEDY-BEST-FIRST SEARCH (problem)
returns a solution or failure
return BEST-FIRST-SEARCH (problem, h)
54
 Romania with step costs in km

374

253

329

comp357, search strategies 55

 Greedy Search
• Estimation function:
h(n) = estimate of cost from n to goal (heuristic).
• For example:
hSLD(n) = straight-line distance from n to Bucharest

• Greedy search expands first the node that appears to be

closest to the goal, according to h(n).

56
 Greedy search, or Heuristic best-first search:

30 • At each step,
S select the node
10
40 with the best (in
20 this case: lowest)
1 heuristic value.
3 • Always expand
35 15 the heuristically
best nodes first.
2 27 18

25 45 The ‘open’
nodes

57
 Greedy search algorithm:
1. QUEUE <-- path only containing the root;

2. WHILE QUEUE is not empty

AND goal is not reached

DO remove the first path from the QUEUE;

create new paths (to all children);
reject the new paths with loops;
add the new paths and sort the entire
QUEUE; (HEURISTIC)

3. IF goal reached
THEN success;
ELSE failure;

58
comp357, search strategies 59
comp357, search strategies 60
comp357, search strategies 61
comp357, search strategies 62
 Properties of Greedy Search
• Complete? No – can get stuck in loops: because it can start down
with an infinite path and never return to try other possibilities.
e.g., X > Y > X > Y > …,Complete in finite space with
repeated-state checking.
• Time? O(b^m) but a good heuristic can give dramatic
improvement.
– Greedy search resembles depth first search, since it follows
one path to the goal state, backtracking occurs when it finds a
dead end.
– The worst case time complexity is equivalent to depth first
search, that is O(bm), where m is the maximum depth of the
search space.

63
 Properties of Greedy Search
• Space? O(b^m) – keeps all nodes in memory
– The greedy search retains all nodes in memory, therefore the
space complexity is also O(bm) The time and space complexity
can be reduced with good heuristic function.

• Optimal? No. It is not optimal, because the next level node for
expansion is selected only depends on the estimated cost and not
the actual cost.

64
Example : Finding the path from one node to another node
• Straight-line distance
to B from A:
A-366
B-0
F-178
P-98
R-193
S-253
T-329
Z-374 65
 Solution to the example given
• Apply the evaluation function h(n) to find a path from A to B

66
 Solution to the example given
• S is selected for next level of expansion, since h(n) is
minimum from S, when comparing to T and Z.

67
 Solution to the example given
• F is selected for next level of expansion, since h(n) is
minimum from F.

• From F, goal state B is reached. Therefore the path from A

to Busing greedy search is A - S - F - B = 450 (i.e) (140 +
99 + 211)

68
A* search( Minimizing the total estimated solution cost)
• Idea: avoid expanding paths that are already expensive
– A* search is both complete and optimal.
• It evaluates nodes by combining g(n), the cost to reach the
node, and h(n.),the cost to get from the node to the goal.
evaluation function: f(n) = g(n) + h(n) with:
g(n) – cost so far to reach n
h(n) – estimated cost to goal from n
f(n) – estimated total cost of path through n to goal
• A* search uses an admissible heuristic, that is,
h(n)  h*(n) where h*(n) is the true cost from n.
For example: hSLD(n) never overestimates actual road 69

distance.
 A* Algorithm

function A* SEARCH(problem) returns a solution

or failure
return BEST-FIRST-SEARCH (problem, g+h)

• Example: Stages in an A* search for Bucharest. Nodes

are labeled with f (n) = g (n) + h(n) [ see next slides]

70
comp357, search strategies 71
comp357, search strategies 72
comp357, search strategies 73
comp357, search strategies 74
comp357, search strategies 75
comp357, search strategies 76
Example : Finding the path from one node to
another node
• Straight-line distance
to B from A:
A-366
B-0
F-178
P-98
R-193
S-253
T-329
Z-374 77
 Solution to the example given
• From the given graph and estimated cost, the goal state is
identified as B from A
• Apply the evaluation function f(n) = g(n) +h(n) to find a path
from A to B

78
 Solution to the example given
• S is selected for next level of expansion, since f(S) is minimum
from S, when comparing to T and Z.

79
 Solution to the example given
• R is selected for next level of expansion, since f(R) is minimum
to A and F.

comp357, search strategies 80

 Solution to the example given

• P is selected for next level of expansion,

since f(P) is minimum.

comp357, search strategies 81

 Conclusion:
• From P, goal state B is reached. Therefore the path from A
to B using A* search is A – S - R - P -B : 418 (ie) {140 +
80 + 97 + 101), that the path cost is less than Greedy search
path cost.

• Time and space complexity: Time complexity depends on

the heuristic function and the admissible heuristic value.
Space complexity remains in the exponential order.

82
 The Behavior of A* search
• Monotonicity (Consistency)
– In search tree any path from the root, the f- cost never
decreases. This condition is true for almost all admissible
heuristics. A heuristic which satisfies this property is
called monotonicity (consistency).
• A heuristic h(n) is consistent if, for every node n and every
successor n' of n generated by any action a, the
estimated cost of reaching the goal from n is no
greater than the step cost of getting to n' plus the
estimated cost of reaching the goal from n’. 83

• { see examples next slides}.

 The Behavior of A* search
• Example for monotonic: Let us consider two nodes n
and n’, where n is the parent of n’.

• g(n) = 3 and h(n) = 4. then f(n) = g(n) + h(n) = 7.

• g(n’) = 5 and h(n’) = 3. then f(n’) = g(n’) + h(n’) = 8
84
 The Behavior of A* search
• Example for Non-monotonic: Let us consider two nodes n
and n’, where n is the parent of n’. For example

• g(n) = 3 and h(n) = 4. then f(n) = g(n) + h(n) = 7.

• g(n’) = 4 and h(n’) = 2. then f(n’) = g(n’) + h(n’) = 6. 85
 The Behavior of A* search
• How to avoid non-monotonic heuristic?
– Non-monotonic heuristic can be avoided using path-max
equation. :f(n') = max (f{n), g(n') + h(n')), ie., max(7,6)=7.
• Optimality
– A* search is complete, optimal, and optimally efficient among
all algorithms
– A* using GRAPH-SEARCH is optimal if h(n) is consistent.
• Completeness
– A* is complete on locally finite graphs (graphs with a finite
branching factor)
– provided there is some constant d such that every operator costs
at least d.
• Drawback :A* usually runs out of space because it keeps all 86

generated nodes in memory