00001 /* 00002 * Parallel state space search library 00003 * 00004 * Jonathan A. Booth 00005 * Sun Mar 2 22:39:32 CST 2003 00006 */ 00007 00008 #include "cklibs/serialtree.h" 00009 00010 00011 00012 SerialTree::SerialTree(problem *start, int height) 00013 : Expanded(0), SolutionHeight(0), Solution(NULL) { 00014 // If this is a solution, then note that and you can cease 00015 if ( start->solution() ) { 00016 Solution = start; 00017 SolutionHeight = height; 00018 return; 00019 } 00020 00021 // Otherwise we need to search the children of this problem. 00022 ChildSearch(start, height); 00023 } 00024 00025 SerialTree::~SerialTree() { 00026 // Free any memory that is mine 00027 problem *tmp; 00028 while ( (tmp = Children.deq()) != NULL ) { 00029 delete tmp; 00030 } 00031 if ( Solution ) { 00032 delete Solution; 00033 Solution = NULL; 00034 } 00035 } 00036 00037 00038 00039 void SerialTree::ChildSearch(problem *current, int heightLeft) { 00040 // Expand this node 00041 CkQ<problem *> kids; 00042 current->children(&kids); 00043 Expanded++; 00044 00045 // For each of those children, search it 00046 problem *tmp; 00047 while ( (tmp = kids.deq()) != NULL ) { 00048 Search(tmp, heightLeft - 1); 00049 } 00050 } 00051 00052 void SerialTree::Search(problem *current, int heightLeft) { 00053 // If I'm a solution, chuck myself in the solution queue and quit searching. 00054 if ( current->solution() ) { 00055 Solution = current; 00056 SolutionHeight = heightLeft; 00057 return; 00058 } 00059 00060 // If I've found a solution and it's better than I could be, abort 00061 if ( heightLeft < SolutionHeight ) { 00062 delete current; 00063 return; 00064 } 00065 00066 // Else if I'm out of height left to search, stick myself in the 00067 // children needing to be respawned queue 00068 if ( heightLeft <= 0 ) { 00069 Children.enq(current); 00070 return; 00071 } 00072 00073 // Otherwise I'm an intermediate node in the search area. I'm not needed 00074 // after my children have been searched, so fire off a search on them 00075 // and then delete me. 00076 ChildSearch(current, heightLeft); 00077 delete current; 00078 }
1.5.5