this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2004, 2016
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#ifndef GECODE_SEARCH_SEQ_LDS_HH
35#define GECODE_SEARCH_SEQ_LDS_HH
36
37#include <gecode/search.hh>
38#include <gecode/search/support.hh>
39#include <gecode/search/worker.hh>
40
41namespace Gecode { namespace Search { namespace Seq {
42
43 /// %Probe engine for %LDS
44 template<class Tracer>
45 class Probe : public Worker {
46 protected:
47 /// Node identity type
48 typedef typename Tracer::ID ID;
49 /// %Node in the search tree for %LDS
50 class Node {
51 private:
52 /// %Space of current node
53 Space* _space;
54 /// Choice
55 const Choice* _choice;
56 /// Next alternative to try
57 unsigned int _alt;
58 /// Node identifier
59 ID _nid;
60 public:
61 /// Default constructor
62 Node(void);
63 /// Initialize with node \a s, choice \a c, and alternative \a a
64 Node(Space* s, const Choice* c, unsigned int a, unsigned int nid);
65 /// Return space
66 Space* space(void) const;
67 /// Return choice
68 const Choice* choice(void) const;
69 /// Return next alternative
70 unsigned int alt(void) const;
71 /// Return node identifier
72 unsigned int nid(void) const;
73 /// %Set next alternative
74 void next(void);
75 };
76 /// Search tracer
77 Tracer tracer;
78 /// %Stack storing current path in search tree
79 Support::DynamicStack<Node,Heap> ds;
80 /// Current space
81 Space* cur;
82 /// Current discrepancy
83 unsigned int d;
84 /// Whether entire search space has been exhausted
85 bool exhausted;
86 public:
87 /// Initialize
88 Probe(const Options& opt);
89 /// Initialize with space \a s
90 void init(Space* s);
91 /// Reset with space \a s and discrepancy \a d
92 void reset(Space* s, unsigned int d);
93 /// Return statistics
94 Statistics statistics(void) const;
95 /// Destructor
96 ~Probe(void);
97 /// %Search for next solution
98 Space* next(const Options& o);
99 /// Test whether probing is done
100 bool done(void) const;
101 };
102
103 /// Limited discrepancy search engine implementation
104 template<class Tracer>
105 class LDS : public Engine {
106 protected:
107 /// Search options
108 Options opt;
109 /// The probe engine
110 Probe<Tracer> e;
111 /// Root node for problem
112 Space* root;
113 /// Current discrepancy
114 unsigned int d;
115 /// Solution found for current discrepancy
116 bool no_solution;
117 public:
118 /// Initialize for space \a s with options \a o
119 LDS(Space* s, const Options& o);
120 /// Return next solution (nullptr, if none exists or search has been stopped)
121 virtual Space* next(void);
122 /// Return statistics
123 virtual Statistics statistics(void) const;
124 /// Constrain future solutions to be better than \a b (should never be called)
125 void constrain(const Space& b);
126 /// Reset engine to restart at space \a s
127 void reset(Space* s);
128 /// Check whether engine has been stopped
129 virtual bool stopped(void) const;
130 /// Destructor
131 virtual ~LDS(void);
132 };
133
134}}}
135
136#include <gecode/search/seq/lds.hpp>
137
138#endif
139
140// STATISTICS: search-seq