Generated on for Gecode by doxygen 1.17.0
dfs.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 *
6 * Copyright:
7 * Christian Schulte, 2009
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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
34namespace Gecode { namespace Search { namespace Seq {
35
36 template<class Tracer>
39 : tracer(o.tracer), opt(o), path(opt.nogoods_limit), d(0) {
40 if (tracer) {
41 tracer.engine(SearchTracer::EngineType::DFS, 1U);
42 tracer.worker();
43 }
44 if ((s == nullptr) || (s->status(*this) == SS_FAILED)) {
45 fail++;
46 cur = nullptr;
47 if (!opt.clone)
48 delete s;
49 } else {
50 cur = snapshot(s,opt);
51 }
52 }
53
54 template<class Tracer>
55 forceinline void
57 tracer.round();
58 delete cur;
59 path.reset();
60 d = 0;
61 // Reset the statistics first, so that a failed root is counted
63 if (s == nullptr) {
64 cur = nullptr;
65 } else if (s->status(*this) == SS_FAILED) {
66 fail++;
67 delete s;
68 cur = nullptr;
69 } else {
70 cur = s;
71 }
72 }
73
74 template<class Tracer>
77 return path;
78 }
79
80 template<class Tracer>
83 /*
84 * The engine maintains the following invariant:
85 * - If the current space (cur) is not nullptr, the path always points
86 * to exactly that space.
87 * - If the current space (cur) is nullptr, the path always points
88 * to the next space (if there is any).
89 *
90 * This invariant is needed so that no-goods can be extracted properly
91 * when the engine is stopped or has found a solution.
92 *
93 */
94 start();
95 while (true) {
96 // An exhausted search is complete, even when a limit has been reached
97 if ((cur == nullptr) && path.empty())
98 return nullptr;
99 if (stop_seq(opt))
100 return nullptr;
101 while (cur == nullptr) {
102 if (path.empty())
103 return nullptr;
104 cur = path.recompute(d,opt.a_d,*this,tracer);
105 if (cur != nullptr)
106 break;
107 path.next();
108 }
109 node++;
111 if (tracer && (path.entries() > 0)) {
112 typename Path<Tracer>::Edge& top = path.top();
113 ei.init(tracer.wid(), top.nid(), top.truealt(), *cur, *top.choice());
114 }
115 unsigned int nid = tracer.nid();
116 switch (cur->status(*this)) {
117 case SS_FAILED:
118 if (tracer) {
120 tracer.wid(), nid, *cur);
121 tracer.node(ei,ni);
122 }
123 fail++;
124 delete cur;
125 cur = nullptr;
126 path.next();
127 break;
128 case SS_SOLVED:
129 {
130 if (tracer) {
132 tracer.wid(), nid, *cur);
133 tracer.node(ei,ni);
134 }
135 // Deletes all pending branchers
136 (void) cur->choice();
137 Space* s = cur;
138 cur = nullptr;
139 path.next();
140 return s;
141 }
142 case SS_BRANCH:
143 {
144 Space* c;
145 if ((d == 0) || (d >= opt.c_d)) {
146 c = cur->clone();
147 d = 1;
148 } else {
149 c = nullptr;
150 d++;
151 }
152 const Choice* ch = path.push(*this,cur,c,nid);
153 if (tracer) {
155 tracer.wid(), nid, *cur, ch);
156 tracer.node(ei,ni);
157 }
158 cur->commit(*ch,0);
159 break;
160 }
161 default:
163 }
164 }
166 return nullptr;
167 }
168
169 template<class Tracer>
172 return *this;
173 }
174
175 template<class Tracer>
176 forceinline void
178 (void) b;
179 assert(false);
180 }
181
182 template<class Tracer>
185 delete cur;
186 tracer.done();
187 path.reset();
188 }
189
190}}}
191
192// STATISTICS: search-seq
Choice for performing commit
Definition core.hpp:1430
No-goods recorded from restarts.
Definition core.hpp:1606
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition tracer.hpp:107
unsigned int nid(void) const
Return parent node id.
Definition tracer.hpp:142
@ FAILED
A solution node.
Definition search.hh:286
@ BRANCH
A failed node.
Definition search.hh:287
@ DFS
Engine is a DFS engine.
Definition search.hh:202
Search engine options
Definition search.hh:848
Space * next(void)
Search for next solution
Definition dfs.hpp:82
Statistics statistics(void) const
Return statistics.
Definition dfs.hpp:171
~DFS(void)
Destructor.
Definition dfs.hpp:184
NoGoods & nogoods(void)
Return no-goods.
Definition dfs.hpp:76
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called).
Definition dfs.hpp:177
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition dfs.hpp:38
Search tree edge for recomputation
Definition path.hh:70
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization).
Definition path.hpp:71
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:103
const Choice * choice(void) const
Return choice.
Definition path.hpp:97
Search engine statistics
Definition search.hh:155
unsigned long long int fail
Number of failed nodes in search tree.
Definition search.hh:158
unsigned long long int node
Number of nodes expanded.
Definition search.hh:160
void start(void)
Reset stop information.
Definition worker.hh:76
bool stop_seq(Options &o)
Check stop and wait for admission of a sequential worker.
Definition worker.hh:89
Computation spaces.
Definition core.hpp:1787
void reset(void)
Reset information.
Definition core.hpp:4974
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1729
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1728
@ SS_FAILED
Space is failed
Definition core.hpp:1727
Search engines
Gecode toplevel namespace
#define forceinline
Definition config.hpp:144
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56