State Space Search

enumeration
graph searh
breadth-first search
depth-first search
topological sort
strongly connected component
Discussion
implicit tree
recursive programing
generate and test
using loop instead of recursion

Finding the solution by searching the state space tree/graph
What is state space representation
For hard problems, the representation is exponential in the size of problem, hence usually the state space tree/graph is implicit.
Representing the solution by
- permutation
- subset
- set partition
State space tree is generated by enumeration.

Enumeration

Example: Representation by subset enumeration of binary string (from Somchaip 2001),
(x1,x2, ... xn) represent a subset, xi = 1 "select", xi = 0 "not-select".

enum( x[1..n], k)
if ( k == n ) then Use( x[1..n] )
else
     x[k+1] = 1
     enum( x [1..n], k+1)
     x[k+1] = 0
     enum( x[1..n], k+1)

Example of state space tree for subset-sum problem.

The solutions are at the leaf nodes. The internal nodes can stored useful information that guide efficient search.
Basic searching techniques for the state space tree/graph are : depth-first, breadth-first, lowest cost. Cost function depends on the problem and it is heuristic. Somchaip (2001) presents basic search for state space tree. Here I will present a more general version for searching graph. (CLR 1990)

Graph search

Breadth-first search

BFS(G,s) // G = <V,E>, s starting point
         // d[.] distance from s
         // p[.] parent
         // Q is a first-in first-out queue
1 for each u in V - {s} do
2     color[u] = WHITE
3     d[u] = INF
4     p[u] = NIL
5 color[s] = GRAY
6 d[s] = 0
7 p[s] = NIL
8 Q = empty
9 while Q is not empty do
10    u = head Q
11    for each v in Adj[u] do
12       if colur[v] = WHITE then
13          color[v] = GRAY
14          d[v] = d[u] + 1
15          p[v] = u
16          enqueue(Q,v)
17     dequeue(Q)
18     color[u] = BLACK

Depth-first search

DFS(G) // G = <V,E>
        // d[.] start time
        // f[.] finish time
        // time is a global variable
1 for each u in V do
2     color[u] = WHITE
3     p[u] = NIL
4 time = 0
5 for each u in V do
6     if colour[u] = WHITE then
7        DFS-VISIT(u)

DFS-VISIT(u)
1 color[u] = GRAY
2 d[u] = time; time = time + 1
3 for each v in Adj[u] do
4     if color[u] = WHITE then
5        p[v] = u
6        DFS-VISIT(v)
7 color[u] = BLACK
8 f[u] = time; time = time + 1

Topological sort

is a linear ordering of vertices in a graph. If (u,v) in E then u comes before v in the ordering. G must be acyclic.

TOPOLOGICAL-SORT(G)
1 call DFS(G)
2 while each vertice is finished insert it in front of a linked list
3 return the linked list

Strongly connected component

is a maximal set U is-subset V such that for each (u,v) in U,
u --> v and v --> u.

SCC(G)
1 call DFS(G)
2 computer G' // G' is G transpose
3 call DFS(G') such that exploring adjacent vertices in decreasing order of f[u]
4 output each tree in the depth-first forest

Discussion

lecture on 26 August 2002

What we try to explore is:
1) state-space representation
2) implicit/explicit tree/graph
3) recursive programming

Solving problems as searching for solutions in state-space. The framework of general seach method is independent to the problem. However, to make searching more efficient, knowledge about the problem can be used to guide the search. This knowledge is usually encoded into the search procedure and is generally known as "heuristics". Artificial intelligence is heavily dominated by this style of problem solving.

Basic assumption about state-space search is
1) the problem is hard, that is, in terms of running time it requires O(k^n) exponential time to solve the problem in the worst case.
2) the state-space tree/graph is exponential in size. It is impossible to explicitly represent it in the memory.
3) we may accept some error in the solution in trade-off with the efficiency of the algorithm (using probabilistic algorithms) or we may accept suboptimal solution (using approximate algorithms).

Implicit representation

As the size of the state-space representation is exponential to the size of the problem, it can not be represented explicitly or it can not be represented entirely in the memory. What that is needed for the search algorithm is the "state" such as, the current node and the procedure to "explode" the current node (to enumerate its children). This required the recursive programming style.

This "implicit" structure represents the current state of the search and the trail of the complete search (from the beginning to the current state) is represented in the trace of control of program execution (recursive calls).

Recursive programming

To understand recursive programming, programming experience is required. You should try to program a number of small problems using recursive style to gain the "insight" of how trace of control work. Here is a simple example:

Given x is a set with tail(x) is the set without the first element. head(x) returns the first element of x. The following program finds the cardinal (size) of the set using recursive programming:

len(x)
if x is empty then return 0
else return 1 + len( tail(x))

Another example, given a is an item, we want to test for its membership with the set x.

member(a, x)
if x is empty then return FALSE
else if a == head(x) then return TRUE
else return member(a, tail(x))

Generate and test

Let us see how the implicit tree and recursive program work together. Here is the program to enumerate all possible arrangement of a binary set. x is a set of {0,1}* stored in an array. (from Somchaip 2002)

1 enum(x[1..n],k)
2 if k == n then USE x
3 else
4     x[k+1] = 1;
5     enum(x[1..n], k+1);
6     x[k+1] = 0;
7     enum(x[1..n], k+1);

The enumeration creates an implicit tree starting from {?,?,?,?) with the call enum(x,0) and generates {1,1,1,1} ... {0,0,0,0} one for each recursive call to enum(). After one tuple is generated (stop at the line 2 k == n), we can use that tuple.

The generated implicit tree represents the solutions at the leaf nodes and the internal nodes represent partial solutions. Heuristic function can be added to decise which solution to explore between line 4--7. An internal node which represents a partial solution is sometime useful to guide which node to explore further.

using loop instead of recursion

Loop can be used instead of recursive call when an auxillary data structure: queue, stack is used. For example a queue of next node to be explored can be used to achieve BFS, a stack of next node to be explored can be used to achieve DFS using loop. As follows:

BFS
while( Q is not empty )
a = dequeue(Q)
USE a
for e = all children of a
enqueue(e,Q)
DFS
while( S is not empty )
a = pop(S)
USE a
for e = all children of a
push(e)

End of lecture last update 28 August 2002