Artificial Intelligence
(5) Strategies for State Space Search
Prof. Moheb Ramzy Girgis
Department of Computer Science
Faculty of Science
Minia University
Data-driven and Goal-driven Search
A state space may be searched in two directions:
from the given data of a problem instance toward a goal, or
from the goal back to the data.
In data-driven search, sometimes called forward chaining:
The problem solver begins with the given facts of the problem
and a set of legal moves or rules for changing state.
Search proceeds by applying rules to facts to produce new
facts, which are in turn used by the rules to generate more
new facts.
This process continues until it generates a path that satisfies
the goal.
In goal driven search, sometimes called backward chaining:
The problem solver takes the goal, and finds the rules or legal
moves that could produce this goal, and determines the
conditions that must be true to use them.
These conditions become the new goals, or subgoals, for the
search.
Search continues, working backward through successive
subgoals until it works back to the facts of the problem.
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
2
Minia University
Data-driven and Goal-driven Search ..
The preferred strategy is determined by careful analysis of
the problem, considering such issues as:
The complexity of the rules.
The branching factor of rule application (on average how
many new states are generated by rule application in
both directions?), i.e. the shape of the state space.
The availability of data.
Ease of determining the potential goals.
In solving a problem using either goal- or data-driven
search, a problem solver must find a path from a start state
to a goal through the state space graph.
The sequence of arcs in this path corresponds to the
ordered steps of the solution.
The problem solver must consider different paths through
the space until it finds a goal.
Backtracking is a technique for systematically trying all
paths through a state space.
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
3
Minia University
The Backtrack Search Algorithm
Backtracking search begins at the start state and pursues
a path until it reaches either a goal or a "dead end".
If it finds a goal, it quits and returns the solution path.
If it reaches a dead end, it "backtracks" to the most
recent node on the path having unexamined children
and continues down one of these branches. 1
A
The algorithm continues until it finds
a goal or exhausts the state space.
2
The following figure shows the B 8 C 10 D
backtrack algorithm applied to 3
E F G
a hypothetical state space. 6
9
The dashed arrows indicate the H 4
I J
5 7
progress of the search up and
down the space. The number beside each node indicates
the order in which it is visited.
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
4
Minia University
The Backtrack Search Algorithm ..
We now define an algorithm that performs a backtrack
using three lists to keep track of nodes in the state space:
SL, for state list, lists the states in the current path being
tried. If a goal is found, SL contains the ordered list of
states on the solution path.
NSL, for new state list, contains nodes whose
descendants have not yet been generated and
searched.
DE, for dead ends, lists states whose descendants have
failed to contain a goal node. If these states are
encountered again, they will be eliminated from
consideration again.
In addition, the algorithm uses the variable CS to hold the
state currently under consideration.
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
5
Minia University
The Backtrack Search Algorithm ..
In defining the backtrack algorithm for the general case (a graph
rather than a tree), it is necessary to detect multiple occurrences of
any state so that it will not be reentered and cause (infinite) loops in
the path.
This is accomplished by testing each newly generated state for
membership in any of these three lists. If a new state belongs to
any of these lists, then it has already been visited and is ignored.
In backtrack, the state currently under consideration, CS, is always
equal to the state most recently added to SL and represents the
"frontier" of the solution path currently being explored.
An ordered set of new states, the children of CS, is generated by
applying inference rules, moves in the game, or other appropriate
problem-solving operators to CS.
The first of these children is made the new current state and added
to SL, and the rest are placed in order on NSL for future
examination, then search continues.
If CS has no children, it is removed from SL (this is where the
algorithm "backtracks") and any remaining children of its
predecessor on SL are examined.
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
6
Minia University
The Backtrack Search Algorithm ..
Function backtrack
begin
SL = [Start]; NSL = [Start]; DE = [ ]; CS = Start; % initialize
while NSL [ ] do
begin
if CS = goal (or meets goal description) then
return SL; % on success, return list on states in path
if CS has no children (excluding nodes already on DE,
SL, and NSL) then
begin % backtrack
while SL is not empty and CS = 1st element of SL do
% This means the state has been visited before.
begin
add CS to DE; % record state as dead end
remove 1st element from SL; % backtrack
remove 1st element from NSL;
CS = 1st element of NSL;
end
add CS to SL;
end
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
7
Minia University
The Backtrack Search Algorithm ..
else % CS has children
begin
generate and place children of CS (except nodes
already on DE, SL, and NSL) on NSL;
CS = 1st element of NSL;
add CS to SL;
end
end;
return FAIL;
end.
As presented here, backtrack implements data-driven search,
taking the root as a start state and evaluating its children to
search for the goal.
The algorithm can be viewed as a goal-driven search by letting
the goal be the root of the graph and evaluating descendants
back in an attempt to find a start state.
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
8
Minia University
The Backtrack Search Algorithm ..
Iteration # CS SL NSL DE
A trace of 0 A [A] [A] []
backtrack on the
graph, shown in 1 B [BA] [BCDA] []
slide 4, where 2 E [EBA] [EFBCDA] []
the desired goal 3 H [HEBA] [HIEFBCDA] []
is G: I [EBA] [IEFBCDA] [H]
Initialize:
4 I [IEBA] [IEFBCDA] [H]
SL = [A];
E [EBA] [EFBCDA] [IH]
NSL = [A];
F [BA] [FBCDA] [EIH]
DE = [ ];
5 F [FBA] [FBCDA] [EIH]
CS = A
6 J [JFBA] [JFBCDA] [EIH]
F [FBA] [FBCDA] [JEIH]
B [BA] [BCDA] [FJEIH]
C [A] [CDA] [BFJEIH]
7
Artificial Intelligence - Prof.C [CA]
Moheb Ramzy Girgis [CDA] [BFJEIH]
Dept. of Computer Science - Faculty of Science
8 Minia University
G [GCA] [GCDA] [BFJEIH]
9 9
The Backtrack Search Algorithm ..
Iteration # CS SL NSL DE
A trace of 0 A [A] [A] []
backtrack on the 1 B [BA] [BCDA] []
graph, shown in 2 E [EBA] [EFBCDA] []
slide 4, where 3 H [HEBA] [HIEFBCDA] []
the desired goal I [EBA] [IEFBCDA] [H]
is G: 4 I [IEBA] [IEFBCDA] [H]
Initialize: E [EBA] [EFBCDA] [IH]
SL = [A]; F [BA] [FBCDA] [EIH]
NSL = [A]; 5 F [FBA] [FBCDA] [EIH]
DE = [ ]; 6 J [JFBA] [JFBCDA] [EIH]
CS = A F [FBA] [FBCDA] [JEIH]
B [BA] [BCDA] [FJEIH]
C [A] [CDA] [BFJEIH]
7 C [CA] [CDA] [BFJEIH]
8 G [GCA] [GCDA] [BFJEIH]
9 G is the Goal, Path = [GCA]
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
Minia University
Depth-First and Breadth-First Search
In addition to specifying a search direction (data-driven or
goal-driven), a search algorithm must determine the order
in which states are examined in the tree or the graph, for
example: depth-first and breadth-first search.
Depth-first search (DFS) goes deeper into the search
space whenever this is possible. Only when no further
descendants of a state can be found are its siblings
considered.
DFS examines the states in the previous graph in the
order: A, B, E, H, I, F, J, C, G, D.
The backtrack algorithm implemented depth-first search.
Breadth-first search (BFS), in contrast, explores the
space in a level-by-level fashion. Only when there are no
more states to be explored at a given level does the
algorithm move on to the next level.
A BFS of the previous graph considers the states in the
order: A, B, C, D, E, F, G, H, I, J.
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
11
Minia University
Depth-First and Breadth-First Search ..
BFS and DFS algorithms use two lists:
open: lists states that have been generated but whose
children have not been examined. The order in which
states are placed in open determines the order of the
search. It is implemented as a queue in BFS and as a
stack in DFS. (open is like NSL in backtrack).
closed: records states that have already been
examined. (closed is the union of the DE and SL lists
of the backtrack algorithm).
The current state is stored in a variable X.
Child states are generated by inference rules, legal
moves of a game, or other state transition operators.
Each iteration produces all children of the state X and
adds them to open.
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
12
Minia University
Breadth-First Search Algorithm
Function BFS
begin
open = [Start]; closed = [ ]; % initialize
while open [ ] do
begin
remove leftmost state from open, and store it in X;
if X is a goal then
return SUCCESS; % goal found
else
begin
generate children of X;
put X on closed;
discard children of X if already on open or closed;
% loop check
put remaining children on right end of open; % queue
end
end
return FAIL
end.
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
13
Minia University
Breadth-First Search Algorithm ..
A trace of BFS on the previous graph, where the desired
goal is G, appears below:
Because BFS Iteration # X open closed
considers every
node at each level 0 - [A] []
of the graph before
going deeper into 1 A [BCD] [A]
the space, all states 2 B [CDEF] [BA]
are first reached
along the shortest 3 C [DEFG] [CBA]
path from the start 4 D [EFG] [DCBA]
State, Breadth-first
search is therefore 5 E [FGHI] [EDCBA]
guaranteed to find 6 F [GHIJ] [FEDCBA]
the shortest path
from the start state 7 G G is the goal
to the goal.
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
14
Minia University
Depth-First Search Algorithm
Function DFS
begin
open = [Start]; closed = [ ]; % initialize
while open [ ] do
begin
remove leftmost state from open, and store it in X;
if X is a goal then
return SUCCESS; % goal found
else
begin
generate children of X;
put X on closed;
discard children of X if already on open or closed;
% loop check
put remaining children on left end of open; % stack
end
end
return FAIL
end.
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
15
Minia University
Depth-First Search Algorithm ..
A trace of DFS on the previous graph, where the desired
goal is G, appears below:
Unlike BFS, a DFS Iteration # X open closed
search is not 0 - [A] []
guaranteed to find 1 A [BCD] [A]
the shortest path to
a state the first time 2 B [EFCD] [BA]
that state is 3 E [HIFCD] [EBA]
encountered. Later 4 H [IFCD] [HEBA]
in the search, a
5 I [FCD] [IHEBA]
different path may
be found to any 6 F [JCD] [FIHEBA]
state. 7 J [CD] [JFIHEBA]
8 C [GD] [CJFIHEBA]
9 G G is the goal
Artificial Intelligence - Prof. Moheb Ramzy Girgis
Dept. of Computer Science - Faculty of Science
16
Minia University
