Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef AlpsSubTree_h_
00024 #define AlpsSubTree_h_
00025
00026 #include <cassert>
00027 #include <list>
00028
00029 #include "CoinError.hpp"
00030 #include "CoinSort.hpp"
00031
00032 #include "AlpsSearchStrategy.h"
00033 #include "AlpsKnowledge.h"
00034 #include "AlpsNodePool.h"
00035 #include "AlpsPriorityQueue.h"
00036 #include "AlpsTreeNode.h"
00037
00038 class AlpsKnowledgeBroker;
00039
00040
00041
00047 class AlpsSubTree : public AlpsKnowledge {
00048
00049 protected:
00050
00052 AlpsTreeNode* root_;
00053
00055 AlpsNodePool* nodePool_;
00056
00058 AlpsNodePool* diveNodePool_;
00059
00061 AlpsSearchStrategy<AlpsTreeNode*> * diveNodeRule_;
00062
00064 int diveDepth_;
00065
00066
00067
00068
00071 AlpsTreeNode* activeNode_;
00072
00074 double quality_;
00075
00078
00079 AlpsKnowledgeBroker* broker_;
00080
00081 protected:
00082
00089 void removeDeadNodes(AlpsTreeNode*& node);
00090
00092 void replaceNode(AlpsTreeNode* oldNode, AlpsTreeNode* newNode);
00093
00097 void fathomAllNodes();
00098
00099 public:
00100
00102 AlpsSubTree();
00103
00105 AlpsSubTree(AlpsKnowledgeBroker* kb);
00106
00108 virtual ~AlpsSubTree();
00109
00110 public:
00111
00113 inline AlpsTreeNode* activeNode() { return activeNode_; }
00114
00116 inline void setActiveNode(AlpsTreeNode *activeNode)
00117 { activeNode_ = activeNode; }
00118
00120 void createChildren(AlpsTreeNode* parent,
00121 std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus,
00122 double> >& children,
00123 AlpsNodePool *kidNodePool = NULL);
00124
00129 inline AlpsTreeNode* getRoot() const { return root_; }
00130
00132 inline void setRoot(AlpsTreeNode* r) { root_ = r; }
00133
00135 inline AlpsNodePool* nodePool() { return nodePool_; }
00136
00138 inline AlpsNodePool* diveNodePool() { return diveNodePool_; }
00139
00141 inline void setNodePool(AlpsNodePool* np) {
00142 if (nodePool_ != NULL) {
00143 delete nodePool_;
00144 nodePool_ = NULL;
00145 }
00146 nodePool_ = np;
00147 }
00148
00150 inline void changeNodePool(AlpsNodePool* np) {
00151 if (nodePool_ != NULL) {
00152
00153 nodePool_->clear();
00154
00155 assert(nodePool_->hasKnowledge() == false);
00156 delete nodePool_;
00157 nodePool_ = NULL;
00158 }
00159 nodePool_ = np;
00160 }
00161
00163 double getBestKnowledgeValue() const;
00164
00166 AlpsTreeNode *getBestNode() const;
00167
00169 inline AlpsKnowledgeBroker* getKnowledgeBroker() const { return broker_; }
00170
00172 inline void setKnowledgeBroker(AlpsKnowledgeBroker* kb) {
00173 assert(kb);
00174 broker_ = kb;
00175 }
00176
00178 inline double getQuality() const { return quality_; }
00179
00181 inline double getSolEstimate() const {
00182 if (root_) {
00183 return root_->getSolEstimate();
00184 }
00185 else {
00186 return ALPS_OBJ_MAX;
00187 };
00188 }
00189
00191 void incDiveDepth(int num=1) { diveDepth_ += num; }
00192
00194 int getDiveDepth() { return diveDepth_; }
00195
00197 void setDiveDepth(int num) { diveDepth_ = num; }
00198
00201 double calculateQuality();
00202
00203
00204
00205 int nextIndex();
00206
00208 int getNextIndex() const;
00209
00211 void setNextIndex(int next);
00212
00214 int getNumNodes() const {
00215 assert(nodePool_ && diveNodePool_);
00216 int nn = 0;
00217 if (activeNode_) {
00218 if ( (activeNode_->getStatus() != AlpsNodeStatusFathomed) &&
00219 (activeNode_->getStatus() != AlpsNodeStatusBranched) ) {
00220 ++nn;
00221 }
00222 }
00223 return (nn + nodePool_->getNumKnowledges() +
00224 diveNodePool_->getNumKnowledges());
00225 }
00226
00228 void setNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) {
00229 nodePool_->setNodeSelection(*nc);
00230 }
00232
00235 AlpsSubTree* splitSubTree(int& returnSize, int size = 10);
00236
00240 virtual AlpsReturnStatus exploreSubTree(AlpsTreeNode* root,
00241 int nodeLimit,
00242 double timeLimit,
00243 int & numNodesProcessed,
00244 int & numNodesBranched,
00245 int & numNodesDiscarded,
00246 int & numNodesPartial,
00247 int & depth);
00248
00254 AlpsReturnStatus exploreUnitWork(bool leaveAsIt,
00255 int unitWork,
00256 double unitTime,
00257 AlpsExitStatus & solStatus,
00258 int & numNodesProcessed,
00259 int & numNodesBranched,
00260 int & numNodesDiscarded,
00261 int & numNodesPartial,
00262 int & depth,
00263 bool & betterSolution);
00264
00267 virtual int rampUp(int minNumNodes,
00268 int requiredNumNodes,
00269 int& depth,
00270 AlpsTreeNode* root = NULL);
00271
00272 using AlpsKnowledge::encode ;
00275 virtual AlpsEncoded* encode() const;
00276
00281 virtual AlpsKnowledge* decode(AlpsEncoded& encoded) const;
00282
00285 virtual AlpsSubTree* newSubTree() const {
00286 return new AlpsSubTree;
00287 }
00288
00290 void clearNodePools() {
00291 if (nodePool_) {
00292 nodePool_->clear();
00293 }
00294 if (diveNodePool_) {
00295 diveNodePool_->clear();
00296 }
00297 }
00298
00300 void nullRootActiveNode() {
00301 root_ = NULL;
00302 activeNode_ = NULL;
00303 }
00304
00306 void reset() {
00307
00308 AlpsTreeNode *tempNode = NULL;
00309 while (diveNodePool_->getNumKnowledges() > 0) {
00310 tempNode = dynamic_cast<AlpsTreeNode *>
00311 (diveNodePool_->getKnowledge().first);
00312 diveNodePool_->popKnowledge();
00313 nodePool_->addKnowledge(tempNode, tempNode->getQuality());
00314 }
00315 if (activeNode_) {
00316 nodePool_->addKnowledge(activeNode_, activeNode_->getQuality());
00317 activeNode_ = NULL;
00318 }
00319
00320 diveDepth_ = 0;
00321 }
00322
00323 };
00324 #endif
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350