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

- File List
- File Members

AlpsSearchStrategy.h
Go to the documentation of this file.
1 /*===========================================================================*
2 * This file is part of the Abstract Library for Parallel Search (ALPS). *
3 * *
4 * ALPS is distributed under the Eclipse Public License as part of the *
5 * COIN-OR repository (http://www.coin-or.org). *
6 * *
7 * Authors: *
8 * *
9 * Yan Xu, Lehigh University *
10 * Ted Ralphs, Lehigh University *
11 * *
12 * Conceptual Design: *
13 * *
14 * Yan Xu, Lehigh University *
15 * Ted Ralphs, Lehigh University *
16 * Laszlo Ladanyi, IBM T.J. Watson Research Center *
17 * Matthew Saltzman, Clemson University *
18 * *
19 * *
20 * Copyright (C) 2001-2013, Lehigh University, Yan Xu, and Ted Ralphs. *
21 *===========================================================================*/
22
23 #ifndef AlpsSearchStrategy_h_
24 #define AlpsSearchStrategy_h_
25
26 #include "AlpsSearchStrategyBase.h"
27 #include "AlpsSubTree.h"
28 #include "AlpsTreeNode.h"
29
30 //#############################################################################
31 //#############################################################################
32
33 class AlpsTreeSelection : public AlpsSearchStrategy<AlpsSubTree*>
34 {
35 public:
37 AlpsTreeSelection() {}
38
40 virtual ~AlpsTreeSelection() {}
41
44 virtual bool compare(AlpsSubTree * x, AlpsSubTree * y) = 0;
45 };
46
47 //#############################################################################
48
49 class AlpsNodeSelection : public AlpsSearchStrategy<AlpsTreeNode*>
50 {
51 public:
53 AlpsNodeSelection() {}
54
56 virtual ~AlpsNodeSelection() {}
57
60 virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) = 0;
61
62 /* Select the next node to be processed. */
63 virtual AlpsTreeNode* selectNextNode(AlpsSubTree *subTree);
64
65 /* Create new nodes from pregnant node and store them in node pool. */
66 virtual void createNewNodes(AlpsSubTree *subTree, AlpsTreeNode *node);
67 };
68
69 //#############################################################################
70 // SUBTREE SELECTION RULES
71 //#############################################################################
72
73 class AlpsTreeSelectionBest : public AlpsTreeSelection
74 {
75 public:
77 AlpsTreeSelectionBest() { type_ = AlpsSearchTypeBestFirst; }
78
80 virtual ~AlpsTreeSelectionBest() {}
81
84 virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
85 };
86
87 //#############################################################################
88
89 class AlpsTreeSelectionBreadth : public AlpsTreeSelection
90 {
91 public:
93 AlpsTreeSelectionBreadth() { type_ = AlpsSearchTypeBreadthFirst; }
94
96 virtual ~AlpsTreeSelectionBreadth() {}
97
100 virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
101 };
102
103 //#############################################################################
104
105 class AlpsTreeSelectionDepth : public AlpsTreeSelection
106 {
107 public:
109 AlpsTreeSelectionDepth() { type_ = AlpsSearchTypeDepthFirst; }
110
112 virtual ~AlpsTreeSelectionDepth() {}
113
116 virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
117 };
118
119 //#############################################################################
120
121 class AlpsTreeSelectionEstimate : public AlpsTreeSelection
122 {
123 public:
125 AlpsTreeSelectionEstimate() { type_ = AlpsSearchTypeBestEstimate; }
126
128 virtual ~AlpsTreeSelectionEstimate() {}
129
132 virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
133 };
134
135 //#############################################################################
136 // NODE SELECTION RULES
137 //#############################################################################
138
139 class AlpsNodeSelectionBest : public AlpsNodeSelection
140 {
141 public:
143 AlpsNodeSelectionBest() { type_ = AlpsSearchTypeBestFirst; }
144
146 virtual ~AlpsNodeSelectionBest() {}
147
150 virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
151 return (x->getQuality() > y->getQuality());
152 }
153 };
154
155 //#############################################################################
156
157 class AlpsNodeSelectionBreadth : public AlpsNodeSelection
158 {
159 public:
161 AlpsNodeSelectionBreadth() { type_ = AlpsSearchTypeBreadthFirst; }
162
164 virtual ~AlpsNodeSelectionBreadth() {}
165
168 virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
169 return x->getDepth() > y->getDepth();
170 }
171 };
172
173 //#############################################################################
174
175 class AlpsNodeSelectionDepth : public AlpsNodeSelection
176 {
177 public:
179 AlpsNodeSelectionDepth() { type_ = AlpsSearchTypeDepthFirst; }
180
182 virtual ~AlpsNodeSelectionDepth() {}
183
186 virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
187 return (x->getDepth() < y->getDepth());
188 }
189 };
190
191 //#############################################################################
192
193 class AlpsNodeSelectionEstimate : public AlpsNodeSelection
194 {
195 public:
197 AlpsNodeSelectionEstimate() { type_ = AlpsSearchTypeBestEstimate; }
198
200 virtual ~AlpsNodeSelectionEstimate() {}
201
204 virtual bool compare (AlpsTreeNode * x, AlpsTreeNode * y) {
205 return (x->getSolEstimate() > y->getSolEstimate());
206 }
207 };
208
209 //#############################################################################
210
211 class AlpsNodeSelectionHybrid : public AlpsNodeSelection
212 {
213 public:
215 AlpsNodeSelectionHybrid() { type_ = AlpsSearchTypeHybrid; }
216
218 virtual ~AlpsNodeSelectionHybrid() {}
219
222 virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
223 // best first
224 return (x->getQuality() > y->getQuality());
225 }
226
227 /* Select the next node to be processed. */
228 virtual AlpsTreeNode* selectNextNode(AlpsSubTree *subTree);
229
230 /* Create new nodes from pregnant node and store them in node pool. */
231 virtual void createNewNodes(AlpsSubTree *subTree, AlpsTreeNode *node);
232 };
233
234 //#############################################################################
235 #endif
AlpsSearchTypeBreadthFirst
Definition: Alps.h:76
AlpsSearchTypeBestFirst
Definition: Alps.h:75
AlpsTreeSelection::AlpsTreeSelection
AlpsTreeSelection()
Default Constructor.
Definition: AlpsSearchStrategy.h:37
AlpsNodeSelectionBreadth::compare
virtual bool compare(AlpsTreeNode *x, AlpsTreeNode *y)
This returns true if the depth of node y is lesser than that of node x.
Definition: AlpsSearchStrategy.h:168
AlpsNodeSelectionBreadth
Definition: AlpsSearchStrategy.h:157
AlpsNodeSelection::AlpsNodeSelection
AlpsNodeSelection()
Default Constructor.
Definition: AlpsSearchStrategy.h:53
AlpsTreeSelectionDepth::~AlpsTreeSelectionDepth
virtual ~AlpsTreeSelectionDepth()
Default Destructor.
Definition: AlpsSearchStrategy.h:112
AlpsTreeNode::getSolEstimate
double getSolEstimate() const
Query/set the solution estimate of the node.
Definition: AlpsTreeNode.h:216
AlpsTreeSelectionDepth::compare
virtual bool compare(AlpsSubTree *x, AlpsSubTree *y)
This returns true if the depth of the root node in subtree y is greater than that of the root node in...
AlpsNodeSelectionDepth::~AlpsNodeSelectionDepth
virtual ~AlpsNodeSelectionDepth()
Default Destructor.
Definition: AlpsSearchStrategy.h:182
AlpsNodeSelectionEstimate
Definition: AlpsSearchStrategy.h:193
AlpsNodeSelectionBest::~AlpsNodeSelectionBest
virtual ~AlpsNodeSelectionBest()
Default Destructor.
Definition: AlpsSearchStrategy.h:146
AlpsTreeSelectionDepth::AlpsTreeSelectionDepth
AlpsTreeSelectionDepth()
Default Constructor.
Definition: AlpsSearchStrategy.h:109
AlpsNodeSelectionHybrid
Definition: AlpsSearchStrategy.h:211
AlpsNodeSelectionHybrid::compare
virtual bool compare(AlpsTreeNode *x, AlpsTreeNode *y)
This returns true if the quality of node y is better (the lesser the better) than that of node x...
Definition: AlpsSearchStrategy.h:222
AlpsTreeSelectionEstimate
Definition: AlpsSearchStrategy.h:121
AlpsTreeSelectionBreadth::compare
virtual bool compare(AlpsSubTree *x, AlpsSubTree *y)
This returns true if the depth of the root node in subtree y is smaller than that of the root node in...
AlpsSubTree
This class contains the data pertaining to a particular subtree in the search tree.
Definition: AlpsSubTree.h:47
AlpsSearchTypeBestEstimate
Definition: Alps.h:78
AlpsTreeSelectionBest::compare
virtual bool compare(AlpsSubTree *x, AlpsSubTree *y)
This returns true if the quality of the subtree y is better (the less the better) than that the subtr...
AlpsNodeSelectionHybrid::AlpsNodeSelectionHybrid
AlpsNodeSelectionHybrid()
Default Constructor.
Definition: AlpsSearchStrategy.h:215
AlpsNodeSelectionHybrid::selectNextNode
virtual AlpsTreeNode * selectNextNode(AlpsSubTree *subTree)
AlpsTreeSelectionEstimate::compare
virtual bool compare(AlpsSubTree *x, AlpsSubTree *y)
This returns true if the estimated quality of the subtree y is better (the less the better) than that...
AlpsNodeSelectionHybrid::~AlpsNodeSelectionHybrid
virtual ~AlpsNodeSelectionHybrid()
Default Destructor.
Definition: AlpsSearchStrategy.h:218
AlpsTreeSelectionBest
Definition: AlpsSearchStrategy.h:73
AlpsTreeNode
This class holds one node of the search tree.
Definition: AlpsTreeNode.h:50
AlpsNodeSelectionBest::compare
virtual bool compare(AlpsTreeNode *x, AlpsTreeNode *y)
This returns true if quality of node y is better (the less the better) than that of node x...
Definition: AlpsSearchStrategy.h:150
AlpsNodeSelection::compare
virtual bool compare(AlpsTreeNode *x, AlpsTreeNode *y)=0
This returns true if the depth of node y is lesser than that of node x.
AlpsNodeSelection::selectNextNode
virtual AlpsTreeNode * selectNextNode(AlpsSubTree *subTree)
AlpsNodeSelectionBest::AlpsNodeSelectionBest
AlpsNodeSelectionBest()
Default Constructor.
Definition: AlpsSearchStrategy.h:143
AlpsNodeSelectionBreadth::~AlpsNodeSelectionBreadth
virtual ~AlpsNodeSelectionBreadth()
Default Destructor.
Definition: AlpsSearchStrategy.h:164
AlpsSearchStrategyBase.h
AlpsNodeSelectionHybrid::createNewNodes
virtual void createNewNodes(AlpsSubTree *subTree, AlpsTreeNode *node)
AlpsTreeSelectionEstimate::~AlpsTreeSelectionEstimate
virtual ~AlpsTreeSelectionEstimate()
Default Destructor.
Definition: AlpsSearchStrategy.h:128
AlpsTreeSelectionBreadth::AlpsTreeSelectionBreadth
AlpsTreeSelectionBreadth()
Default Constructor.
Definition: AlpsSearchStrategy.h:93
AlpsNodeSelectionDepth::compare
virtual bool compare(AlpsTreeNode *x, AlpsTreeNode *y)
This returns true if the depth of node y is greater than that of node x.
Definition: AlpsSearchStrategy.h:186
AlpsNodeSelection::~AlpsNodeSelection
virtual ~AlpsNodeSelection()
Default Destructor.
Definition: AlpsSearchStrategy.h:56
AlpsTreeSelectionBreadth::~AlpsTreeSelectionBreadth
virtual ~AlpsTreeSelectionBreadth()
Default Destructor.
Definition: AlpsSearchStrategy.h:96
AlpsTreeSelection::~AlpsTreeSelection
virtual ~AlpsTreeSelection()
Default Destructor.
Definition: AlpsSearchStrategy.h:40
AlpsTreeSelectionDepth
Definition: AlpsSearchStrategy.h:105
AlpsTreeSelectionEstimate::AlpsTreeSelectionEstimate
AlpsTreeSelectionEstimate()
Default Constructor.
Definition: AlpsSearchStrategy.h:125
AlpsNodeSelectionEstimate::compare
virtual bool compare(AlpsTreeNode *x, AlpsTreeNode *y)
This returns true if the estimate quality of node y is better (the lesser the better) than that of no...
Definition: AlpsSearchStrategy.h:204
AlpsNodeSelectionEstimate::~AlpsNodeSelectionEstimate
virtual ~AlpsNodeSelectionEstimate()
Default Destructor.
Definition: AlpsSearchStrategy.h:200
AlpsSubTree.h
AlpsTreeNode.h
AlpsNodeSelection::createNewNodes
virtual void createNewNodes(AlpsSubTree *subTree, AlpsTreeNode *node)
AlpsNodeSelectionEstimate::AlpsNodeSelectionEstimate
AlpsNodeSelectionEstimate()
Default Constructor.
Definition: AlpsSearchStrategy.h:197
AlpsTreeNode::getDepth
int getDepth() const
Query/set what depth the search tree node is at.
Definition: AlpsTreeNode.h:210
AlpsNodeSelectionDepth::AlpsNodeSelectionDepth
AlpsNodeSelectionDepth()
Default Constructor.
Definition: AlpsSearchStrategy.h:179
AlpsNodeSelectionDepth
Definition: AlpsSearchStrategy.h:175
AlpsNodeSelectionBest
Definition: AlpsSearchStrategy.h:139
AlpsNodeSelection
Definition: AlpsSearchStrategy.h:49
AlpsSearchTypeDepthFirst
Definition: Alps.h:77
AlpsTreeSelectionBest::~AlpsTreeSelectionBest
virtual ~AlpsTreeSelectionBest()
Default Destructor.
Definition: AlpsSearchStrategy.h:80
AlpsNodeSelectionBreadth::AlpsNodeSelectionBreadth
AlpsNodeSelectionBreadth()
Default Constructor.
Definition: AlpsSearchStrategy.h:161
AlpsSearchTypeHybrid
Definition: Alps.h:79
AlpsTreeSelectionBest::AlpsTreeSelectionBest
AlpsTreeSelectionBest()
Default Constructor.
Definition: AlpsSearchStrategy.h:77
AlpsTreeSelection
Definition: AlpsSearchStrategy.h:33
AlpsTreeSelectionBreadth
Definition: AlpsSearchStrategy.h:89
AlpsTreeSelection::compare
virtual bool compare(AlpsSubTree *x, AlpsSubTree *y)=0
This returns true if the quality of the subtree y is better (the less the better) than that the subtr...
AlpsTreeNode::getQuality
double getQuality() const
Query/set the quality of the node.
Definition: AlpsTreeNode.h:222