Each possible solution is called a node. If a node is a solution to the problem, then it is called a goal node.
The search process begins at an initial node (also called the root node). Some nodes can be used to generate further nodes through an operation called expansion. If a node has not yet been expanded, it is called a leaf node.
For our problem, each node is an expression represented in abstract
syntax form, i.e. as a binary tree. A node is expanded by taking
one of its primitive subexpressons, i.e. 1 or n, and
replacing it by all possible subexpressions with a single operator, i.e.
1+1,
1-1, 1*1, 1/1, 1+n, 1-n, etc. We can assume that the initial node
is the expression 1.
search-tree := initial-node
loop
if there
are no leaf nodes then return FAIL
else
choose a leaf node X according to "strategy"
if X is a goal node then return X
else
expand X
add the resulting new leaf node(s) to search-tree
end loop
When a leaf node is expanded, either it has children, in which case
it is no longer a leaf node, or it proves to have no children, in which
case it is a "dead end" that should never be chosen again.
Notice that expanding one node can yield another node that has already
been visited. In general the search algorithm does not "know" this,
where "know" means "has available a directly usable explicit representation."
In some domains it is easy to test whether multiple nodes correspond to the same state in the "real world". In other domains it is impossible.
The general search algorithm explores a search tree, NOT the search space directly.
The depth of a node is the number of nodes on the path from the root to this node. (Note that the depth of the root is 0 by this defn.)
The fringe of the tree is the set of leaf nodes of the tree. A leaf node is a node that is NOT the parent of any other node.
The search algorithm needs an efficient representation of the fringe.
We shall use a queue, i.e. a special list where you can remove elements
from the front and you can insert new elements into the middle.
fringe := make-queue(initial-node)
loop
if empty?(fringe)
then return FAIL
else
X := remove-front(fringe)
if isa-goal?(state(X)) then return X
else
fringe := insert(fringe,expand(X))
end loop
The well-formulated search problem includes the following functions:
- initial-node is a node
representing the initial state
- isa-goal? tests whether
a state is a goal state
- expand applies all the
operators of the problem to a node
and returns
all the successors of this node
The function "insert" includes a set of nodes in the queue in a specific
way. Different algorithms use different "insert" functions.
DFS goes down a path until it reaches a node that has no children.
Then DFS "backtracks" and expands a sibling of the node that had
no children. If this node has no siblings, then DFS looks for
a sibling of the grandparent, and so on.
The major weakness of DFS is that it will fail to terminate if there is an infinite path "to the left of" the path to the first solution.
In other words, for many problems DFS is not complete: a solution exists but DFS cannot find it.
The major advantage of DFS is that it only uses O(bm) space if the branching
factor is b and the maximum depth is m. (Explanation: there are m
nodes on the longest path, and for each of these b-1 siblings must be stored.)
If a solution exists at depth M or less, then M-limited DFS will find it and is very space-efficient: it uses only O(b*M) space.
If a solution exists but only at depth greater than M, then depth-limited
DFS is not complete.
The idea is to depth-limited DFS repeatedly, with an increasing depth limit, until a solution is found.
Intuitively, this is a dubious idea because each repetition of depth-limited DFS will repeat uselessly all the work done by previous repetitions.
But, this useless repetition is not significant because a branching factor b > 1 implies that
# nodes at depth k >> # nodes at depth k-1 or less
Iterative deepening simulates BFS with linear space complexity.
For a problem with branching factor b where the first solution is at
depth k, the time complexity of iterative deepening is O(b^k), and its
space complexity is O(b*k).