Generated on for Gecode by doxygen 1.17.0
rbs.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.dev>
5 * Guido Tack <tack@gecode.dev>
6 *
7 * Copyright:
8 * Christian Schulte, 2014
9 * Guido Tack, 2012
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.dev
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
38#include <memory>
39
40namespace Gecode { namespace Search { namespace Seq {
41
44 rbsstop(Stop* so);
45
48 rbsengine(Space* master, Stop* stop, Engine* slave,
49 const Search::Statistics& stat, const Options& opt,
50 bool best);
51
60 rbsengine(Space* master, Stop* stop, Engine* slave,
61 const Search::Statistics& stat, const Options& opt,
62 bool best, bool complete);
63
64}}}
65
66namespace Gecode { namespace Search {
67
69 template<class T, template<class> class E>
70 class RbsBuilder : public Builder {
71 using Builder::opt;
72 public:
74 RbsBuilder(const Options& opt);
76 virtual Engine* operator() (Space* s) const;
77 };
78
79 template<class T, template<class> class E>
80 inline
82 : Builder(opt,E<T>::best) {}
83
84 template<class T, template<class> class E>
85 Engine*
87 return build<T,RBS<T,E> >(s,opt);
88 }
89
90}}
91
92namespace Gecode {
93
94 template<class T, template<class> class E>
95 inline
96 RBS<T,E>::RBS(T* s, const Search::Options& m_opt) {
97 if (m_opt.cutoff == nullptr)
98 throw Search::UninitializedCutoff("RBS::RBS");
99 Search::Options e_opt(m_opt.expand());
101 std::unique_ptr<Search::Stop> stop(Search::Seq::rbsstop(m_opt.stop));
102 e_opt.stop = stop.get();
103 // Retain the seed while a potentially nested builder owns its clone.
104 e_opt.clone = true;
107 if (s->status(stat) == SS_FAILED) {
108 stat.fail++;
109 if (!m_opt.clone)
110 delete s;
111 e = Search::Seq::dead(e_opt, stat);
112 // The engine owns the cutoff, but a dead engine does not take it
113 delete m_opt.cutoff;
114 } else {
115 std::unique_ptr<Space> master(m_opt.clone ? s->clone() : s);
116 std::unique_ptr<Space> slave(master->clone());
117 MetaInfo mi(0,MetaInfo::RR_INIT,0,0,nullptr,NoGoods::eng);
118 bool complete = slave->slave(mi);
119 std::unique_ptr<Search::Engine> leaf(
120 Search::build<T,E>(slave.get(),e_opt));
121 e = Search::Seq::rbsengine(master.get(),stop.get(),leaf.get(),
122 stat,m_opt,E<T>::best,complete);
123 master.release();
124 stop.release();
125 leaf.release();
126 }
127 }
128
129
130 template<class T, template<class> class E>
131 inline T*
132 rbs(T* s, const Search::Options& o) {
133 RBS<T,E> r(s,o);
134 return r.next();
135 }
136
137 template<class T, template<class> class E>
138 SEB
140 if (o.cutoff == nullptr)
141 throw Search::UninitializedCutoff("rbs");
142 return new Search::RbsBuilder<T,E>(o);
143 }
144
145
146}
147
148// STATISTICS: search-seq
Information passed by meta search engines.
Definition core.hpp:1635
@ RR_INIT
Restarting after initialisation.
Definition core.hpp:1649
static NoGoods eng
Empty no-goods.
Definition core.hpp:1628
Meta-engine performing restart-based search.
Definition search.hh:1471
RBS(T *s, const Search::Options &o)
Initialize engine for space s and options o.
Definition rbs.hpp:96
@ RBS
Engine is a RBS engine.
Definition search.hh:205
Engine * e
The actual search engine.
Definition search.hh:1107
Options opt
Stored and already expanded options.
Definition search.hh:1143
Builder(const Options &opt, bool best)
Initialize with options opt and best solution search support.
Definition build.hpp:37
bool best(void) const
Whether engine is a best solution search engine.
Definition build.hpp:48
Search engine implementation interface
Definition search.hh:1063
Search engine options
Definition search.hh:848
bool clone
Whether engines create a clone when being initialized.
Definition search.hh:851
Cutoff * cutoff
Cutoff for restart-based search.
Definition search.hh:877
Options expand(void) const
Expand with real number of threads.
Definition options.cpp:43
Stop * stop
Stop object for stopping search.
Definition search.hh:875
SearchTracer * tracer
Tracer object for tracing search.
Definition search.hh:879
A RBS engine builder.
Definition rbs.hpp:70
virtual Engine * operator()(Space *s) const
The actual build function.
Definition rbs.hpp:86
RbsBuilder(const Options &opt)
The constructor.
Definition rbs.hpp:81
Search engine statistics
Definition search.hh:155
unsigned long long int fail
Number of failed nodes in search tree.
Definition search.hh:158
Exception: Uninitialized cutoff for restart-based search
Definition exception.hpp:42
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
Computation spaces.
Definition core.hpp:1787
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition rbs.hpp:132
@ SS_FAILED
Space is failed
Definition core.hpp:1727
Engine * dead(const Options &o, const Statistics &stat)
Definition dead.cpp:90
Stop * rbsstop(Stop *stop)
Create stop object.
Definition rbs.cpp:39
Engine * rbsengine(Space *master, Stop *stop, Engine *slave, const Search::Statistics &stat, const Options &opt, bool best)
Create restart engine whose first slave search yields valid no-goods.
Definition rbs.cpp:44
Search engines
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Definition build.hpp:55
Gecode toplevel namespace
Search::Builder * SEB
Type for a search engine builder.
Definition search.hh:1168
#define GECODE_SEARCH_EXPORT
Definition search.hh:75