dfs-reco.cc
Go to the documentation of this file.00001 /* 00002 * Main authors: 00003 * Christian Schulte <schulte@gecode.org> 00004 * 00005 * Copyright: 00006 * Christian Schulte, 2004 00007 * 00008 * Last modified: 00009 * $Date: 2005-08-09 21:44:53 +0200 (Tue, 09 Aug 2005) $ by $Author: schulte $ 00010 * $Revision: 2192 $ 00011 * 00012 * This file is part of Gecode, the generic constraint 00013 * development environment: 00014 * http://www.gecode.org 00015 * 00016 * See the file "LICENSE" for information on usage and 00017 * redistribution of this file, and for a 00018 * DISCLAIMER OF ALL WARRANTIES. 00019 * 00020 */ 00021 00022 #include "search/dfs-reco.hh" 00023 00024 namespace Gecode { namespace Search { 00025 00026 DfsReCoEngine::~DfsReCoEngine(void) { 00027 delete cur; 00028 ds.reset(); 00029 } 00030 00031 void 00032 DfsReCoEngine::reset(Space* s) { 00033 delete cur; 00034 ds.reset(); 00035 cur = s; 00036 d = 0; 00037 FullStatistics::reset(s); 00038 } 00039 00040 size_t 00041 DfsReCoEngine::stacksize(void) const { 00042 return ds.size(); 00043 } 00044 00045 Space* 00046 DfsReCoEngine::explore(void) { 00047 while (true) { 00048 while (cur) { 00049 unsigned int alt; 00050 switch (cur->status(alt,propagate)) { 00051 case SS_FAILED: 00052 fail++; 00053 delete cur; 00054 cur = NULL; 00055 FullStatistics::current(NULL); 00056 break; 00057 case SS_SOLVED: 00058 { 00059 Space* s = cur; 00060 cur = NULL; 00061 FullStatistics::current(NULL); 00062 return s; 00063 } 00064 case SS_BRANCH: 00065 { 00066 Space* c; 00067 if ((d == 0) || (d >= c_d)) { 00068 clone++; 00069 c = cur->clone(); 00070 d = 1; 00071 } else { 00072 c = NULL; 00073 if (alt > 1) 00074 d++; 00075 } 00076 BranchingDesc* desc = ds.push(cur,c,alt); 00077 FullStatistics::push(c,desc); 00078 commit++; 00079 cur->commit(0, desc); 00080 break; 00081 } 00082 } 00083 } 00084 if (!ds.next(*this)) 00085 return NULL; 00086 cur = ds.recompute(d,*this); 00087 FullStatistics::current(cur); 00088 } 00089 return NULL; 00090 } 00091 00092 }} 00093 00094 // STATISTICS: search-any