- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/Bcps-0.91.0/Alps/src/AlpsSearchStrategy.h

Go to the documentation of this file.

    00001 /*===========================================================================*
    00002  * This file is part of the Abstract Library for Parallel Search (ALPS).     *
    00003  *                                                                           *
    00004  * ALPS is distributed under the Common Public License as part of the        *
    00005  * COIN-OR repository (http://www.coin-or.org).                              *
    00006  *                                                                           *
    00007  * Authors:                                                                  *
    00008  *                                                                           *
    00009  *          Yan Xu, Lehigh University                                        *
    00010  *          Ted Ralphs, Lehigh University                                    *
    00011  *                                                                           *
    00012  * Conceptual Design:                                                        *
    00013  *                                                                           *
    00014  *          Yan Xu, Lehigh University                                        *
    00015  *          Ted Ralphs, Lehigh University                                    *
    00016  *          Laszlo Ladanyi, IBM T.J. Watson Research Center                  *
    00017  *          Matthew Saltzman, Clemson University                             *
    00018  *                                                                           *
    00019  *                                                                           *
    00020  * Copyright (C) 2001-2009, Lehigh University, Yan Xu, and Ted Ralphs.       *
    00021  *===========================================================================*/
    00022
    00023 #ifndef AlpsSearchStrategy_h_
    00024 #define AlpsSearchStrategy_h_
    00025
    00026 #include "AlpsSearchStrategyBase.h"
    00027 #include "AlpsSubTree.h"
    00028 #include "AlpsTreeNode.h"
    00029
    00030 //#############################################################################
    00031 //#############################################################################
    00032
    00033 class AlpsTreeSelection : public AlpsSearchStrategy<AlpsSubTree*>
    00034 {
    00035 public:
    00037     AlpsTreeSelection() {}
    00038
    00040     virtual ~AlpsTreeSelection() {}
    00041
    00044     virtual bool compare(AlpsSubTree * x, AlpsSubTree * y) = 0;
    00045 };
    00046
    00047 //#############################################################################
    00048
    00049 class AlpsNodeSelection : public AlpsSearchStrategy<AlpsTreeNode*>
    00050 {
    00051 public:
    00053     AlpsNodeSelection() {}
    00054
    00056     virtual ~AlpsNodeSelection() {}
    00057
    00060     virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) = 0;
    00061
    00062     /* Select the next node to be processed. */
    00063     virtual AlpsTreeNode* selectNextNode(AlpsSubTree *subTree);
    00064
    00065     /* Create new nodes from pregnant node and store them in node pool. */
    00066     virtual void createNewNodes(AlpsSubTree *subTree, AlpsTreeNode *node);
    00067 };
    00068
    00069 //#############################################################################
    00070 // SUBTREE SELECTION RULES
    00071 //#############################################################################
    00072
    00073 class AlpsTreeSelectionBest : public AlpsTreeSelection
    00074 {
    00075 public:
    00077     AlpsTreeSelectionBest() { type_ = AlpsSearchTypeBestFirst; }
    00078
    00080     virtual ~AlpsTreeSelectionBest() {}
    00081
    00084     virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
    00085 };
    00086
    00087 //#############################################################################
    00088
    00089 class AlpsTreeSelectionBreadth : public AlpsTreeSelection
    00090 {
    00091 public:
    00093     AlpsTreeSelectionBreadth() { type_ = AlpsSearchTypeBreadthFirst; }
    00094
    00096     virtual ~AlpsTreeSelectionBreadth() {}
    00097
    00100     virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
    00101 };
    00102
    00103 //#############################################################################
    00104
    00105 class AlpsTreeSelectionDepth : public AlpsTreeSelection
    00106 {
    00107 public:
    00109     AlpsTreeSelectionDepth() { type_ = AlpsSearchTypeDepthFirst; }
    00110
    00112     virtual ~AlpsTreeSelectionDepth() {}
    00113
    00116     virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
    00117 };
    00118
    00119 //#############################################################################
    00120
    00121 class AlpsTreeSelectionEstimate : public AlpsTreeSelection
    00122 {
    00123 public:
    00125     AlpsTreeSelectionEstimate() { type_ = AlpsSearchTypeBestEstimate; }
    00126
    00128     virtual ~AlpsTreeSelectionEstimate() {}
    00129
    00132     virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
    00133 };
    00134
    00135 //#############################################################################
    00136 // NODE SELECTION RULES
    00137 //#############################################################################
    00138
    00139 class AlpsNodeSelectionBest : public AlpsNodeSelection
    00140 {
    00141 public:
    00143     AlpsNodeSelectionBest() { type_ = AlpsSearchTypeBestFirst; }
    00144
    00146     virtual ~AlpsNodeSelectionBest() {}
    00147
    00150     virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
    00151         return (x->getQuality() > y->getQuality());
    00152     }
    00153 };
    00154
    00155 //#############################################################################
    00156
    00157 class AlpsNodeSelectionBreadth : public AlpsNodeSelection
    00158 {
    00159 public:
    00161     AlpsNodeSelectionBreadth() { type_ = AlpsSearchTypeBreadthFirst; }
    00162
    00164     virtual ~AlpsNodeSelectionBreadth() {}
    00165
    00168     virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
    00169         return x->getDepth() > y->getDepth();
    00170     }
    00171 };
    00172
    00173 //#############################################################################
    00174
    00175 class AlpsNodeSelectionDepth : public AlpsNodeSelection
    00176 {
    00177  public:
    00179     AlpsNodeSelectionDepth() { type_ = AlpsSearchTypeDepthFirst; }
    00180
    00182     virtual ~AlpsNodeSelectionDepth() {}
    00183
    00186     virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
    00187         return (x->getDepth() < y->getDepth());
    00188     }
    00189 };
    00190
    00191 //#############################################################################
    00192
    00193 class AlpsNodeSelectionEstimate : public AlpsNodeSelection
    00194 {
    00195  public:
    00197     AlpsNodeSelectionEstimate() { type_ = AlpsSearchTypeBestEstimate; }
    00198
    00200     virtual ~AlpsNodeSelectionEstimate() {}
    00201
    00204     virtual bool compare (AlpsTreeNode * x, AlpsTreeNode * y) {
    00205         return (x->getSolEstimate() > y->getSolEstimate());
    00206     }
    00207 };
    00208
    00209 //#############################################################################
    00210
    00211 class AlpsNodeSelectionHybrid : public AlpsNodeSelection
    00212 {
    00213 public:
    00215     AlpsNodeSelectionHybrid() { type_ = AlpsSearchTypeHybrid; }
    00216
    00218     virtual ~AlpsNodeSelectionHybrid() {}
    00219
    00222     virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
    00223         // best first
    00224         return (x->getQuality() > y->getQuality());
    00225     }
    00226
    00227     /* Select the next node to be processed. */
    00228     virtual AlpsTreeNode* selectNextNode(AlpsSubTree *subTree);
    00229
    00230     /* Create new nodes from pregnant node and store them in node pool. */
    00231     virtual void createNewNodes(AlpsSubTree *subTree, AlpsTreeNode *node);
    00232 };
    00233
    00234 //#############################################################################
    00235 #endif