enumerationFinding the solution by searching the state space tree/graph
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
enum( x[1..n], k)Example of state space tree for subset-sum problem.
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)
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)
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(G)
1 call DFS(G)
2 while each vertice is finished insert it in front of a
linked list
3 return the linked list
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
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).
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).
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)Another example, given a is an item, we want to test for its membership with the set x.
if x is empty then return 0
else return 1 + len( tail(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))
1 enum(x[1..n],k)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.
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 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.
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)