Alps 1.5.7
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-2019, Lehigh University, Yan Xu, and Ted Ralphs. *
21 *===========================================================================*/
22
23#ifndef AlpsSearchStrategy_h_
24#define AlpsSearchStrategy_h_
25
27#include "AlpsSubTree.h"
28#include "AlpsTreeNode.h"
29
30//#############################################################################
31//#############################################################################
32
33class AlpsTreeSelection : public AlpsSearchStrategy<AlpsSubTree*>
34{
35public:
38
40 virtual ~AlpsTreeSelection() {}
41
44 virtual bool compare(AlpsSubTree * x, AlpsSubTree * y) = 0;
45};
46
47//#############################################################################
48
49class AlpsNodeSelection : public AlpsSearchStrategy<AlpsTreeNode*>
50{
51public:
54
56 virtual ~AlpsNodeSelection() {}
57
60 virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) = 0;
61
62 /* Select the next node to be processed. */
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
74{
75public:
78
81
84 virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
85};
86
87//#############################################################################
88
90{
91public:
94
97
100 virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
101};
102
103//#############################################################################
104
106{
107public:
110
113
116 virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
117};
118
119//#############################################################################
120
122{
123public:
126
129
132 virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
133};
134
135//#############################################################################
136// NODE SELECTION RULES
137//#############################################################################
138
140{
141public:
144
147
150 virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
151 return (x->getQuality() > y->getQuality());
152 }
153};
154
155//#############################################################################
156
158{
159public:
162
165
168 virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
169 return x->getDepth() > y->getDepth();
170 }
171};
172
173//#############################################################################
174
176{
177 public:
180
183
186 virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
187 return (x->getDepth() < y->getDepth());
188 }
189};
190
191//#############################################################################
192
194{
195 public:
198
201
204 virtual bool compare (AlpsTreeNode * x, AlpsTreeNode * y) {
205 return (x->getSolEstimate() > y->getSolEstimate());
206 }
207};
208
209//#############################################################################
210
212{
213public:
216
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. */
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
@ AlpsSearchTypeDepthFirst
Definition: Alps.h:77
@ AlpsSearchTypeHybrid
Definition: Alps.h:79
@ AlpsSearchTypeBestEstimate
Definition: Alps.h:78
@ AlpsSearchTypeBestFirst
Definition: Alps.h:75
@ AlpsSearchTypeBreadthFirst
Definition: Alps.h:76
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.
virtual ~AlpsNodeSelectionBest()
Default Destructor.
AlpsNodeSelectionBest()
Default Constructor.
AlpsNodeSelectionBreadth()
Default Constructor.
virtual ~AlpsNodeSelectionBreadth()
Default Destructor.
virtual bool compare(AlpsTreeNode *x, AlpsTreeNode *y)
This returns true if the depth of node y is lesser than that of node x.
virtual bool compare(AlpsTreeNode *x, AlpsTreeNode *y)
This returns true if the depth of node y is greater than that of node x.
virtual ~AlpsNodeSelectionDepth()
Default Destructor.
AlpsNodeSelectionDepth()
Default Constructor.
AlpsNodeSelectionEstimate()
Default Constructor.
virtual ~AlpsNodeSelectionEstimate()
Default Destructor.
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...
AlpsNodeSelectionHybrid()
Default Constructor.
virtual void createNewNodes(AlpsSubTree *subTree, AlpsTreeNode *node)
virtual AlpsTreeNode * selectNextNode(AlpsSubTree *subTree)
virtual ~AlpsNodeSelectionHybrid()
Default Destructor.
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.
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()
Default Constructor.
virtual AlpsTreeNode * selectNextNode(AlpsSubTree *subTree)
virtual void createNewNodes(AlpsSubTree *subTree, AlpsTreeNode *node)
virtual ~AlpsNodeSelection()
Default Destructor.
This class contains the data pertaining to a particular subtree in the search tree.
Definition: AlpsSubTree.h:47
This class holds one node of the search tree.
Definition: AlpsTreeNode.h:50
double getQuality() const
Query/set the quality of the node.
Definition: AlpsTreeNode.h:218
int getDepth() const
Query/set what depth the search tree node is at.
Definition: AlpsTreeNode.h:206
double getSolEstimate() const
Query/set the solution estimate of the node.
Definition: AlpsTreeNode.h:212
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...
virtual ~AlpsTreeSelectionBest()
Default Destructor.
AlpsTreeSelectionBest()
Default Constructor.
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...
AlpsTreeSelectionBreadth()
Default Constructor.
virtual ~AlpsTreeSelectionBreadth()
Default Destructor.
AlpsTreeSelectionDepth()
Default Constructor.
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...
virtual ~AlpsTreeSelectionDepth()
Default Destructor.
virtual ~AlpsTreeSelectionEstimate()
Default Destructor.
AlpsTreeSelectionEstimate()
Default Constructor.
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...
AlpsTreeSelection()
Default Constructor.
virtual ~AlpsTreeSelection()
Default Destructor.
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...