Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.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.org>
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.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
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 == NULL) || (s->status(*this) == SS_FAILED)) {
45 fail++;
46 cur = NULL;
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 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
62 delete s;
63 cur = NULL;
64 } else {
65 cur = s;
66 }
68 }
69
70 template<class Tracer>
73 return path;
74 }
75
76 template<class Tracer>
79 /*
80 * The engine maintains the following invariant:
81 * - If the current space (cur) is not NULL, the path always points
82 * to exactly that space.
83 * - If the current space (cur) is NULL, the path always points
84 * to the next space (if there is any).
85 *
86 * This invariant is needed so that no-goods can be extracted properly
87 * when the engine is stopped or has found a solution.
88 *
89 */
90 start();
91 while (true) {
92 if (stop(opt))
93 return NULL;
94 while (cur == NULL) {
95 if (path.empty())
96 return NULL;
97 cur = path.recompute(d,opt.a_d,*this,tracer);
98 if (cur != NULL)
99 break;
100 path.next();
101 }
102 node++;
104 if (tracer && (path.entries() > 0)) {
105 typename Path<Tracer>::Edge& top = path.top();
106 ei.init(tracer.wid(), top.nid(), top.truealt(), *cur, *top.choice());
107 }
108 unsigned int nid = tracer.nid();
109 switch (cur->status(*this)) {
110 case SS_FAILED:
111 if (tracer) {
113 tracer.wid(), nid, *cur);
114 tracer.node(ei,ni);
115 }
116 fail++;
117 delete cur;
118 cur = NULL;
119 path.next();
120 break;
121 case SS_SOLVED:
122 {
123 if (tracer) {
125 tracer.wid(), nid, *cur);
126 tracer.node(ei,ni);
127 }
128 // Deletes all pending branchers
129 (void) cur->choice();
130 Space* s = cur;
131 cur = NULL;
132 path.next();
133 return s;
134 }
135 case SS_BRANCH:
136 {
137 Space* c;
138 if ((d == 0) || (d >= opt.c_d)) {
139 c = cur->clone();
140 d = 1;
141 } else {
142 c = NULL;
143 d++;
144 }
145 const Choice* ch = path.push(*this,cur,c,nid);
146 if (tracer) {
148 tracer.wid(), nid, *cur, ch);
149 tracer.node(ei,ni);
150 }
151 cur->commit(*ch,0);
152 break;
153 }
154 default:
156 }
157 }
159 return NULL;
160 }
161
162 template<class Tracer>
165 return *this;
166 }
167
168 template<class Tracer>
169 forceinline void
171 (void) b;
172 assert(false);
173 }
174
175 template<class Tracer>
178 delete cur;
179 tracer.done();
180 path.reset();
181 }
182
183}}}
184
185// STATISTICS: search-seq
Choice for performing commit
Definition core.hpp:1414
No-goods recorded from restarts.
Definition core.hpp:1590
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:278
@ BRANCH
A failed node.
Definition search.hh:279
@ DFS
Engine is a DFS engine.
Definition search.hh:194
Search engine options
Definition search.hh:746
Space * next(void)
Search for next solution
Definition dfs.hpp:78
Statistics statistics(void) const
Return statistics.
Definition dfs.hpp:164
~DFS(void)
Destructor.
Definition dfs.hpp:177
NoGoods & nogoods(void)
Return no-goods.
Definition dfs.hpp:72
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
Definition dfs.hpp:170
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:66
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition path.hpp:67
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:99
const Choice * choice(void) const
Return choice.
Definition path.hpp:93
Search engine statistics
Definition search.hh:147
unsigned long int fail
Number of failed nodes in search tree.
Definition search.hh:150
unsigned long int node
Number of nodes expanded.
Definition search.hh:152
void start(void)
Reset stop information.
Definition worker.hh:74
bool stop(const Options &o)
Check whether engine must be stopped.
Definition worker.hh:79
Computation spaces.
Definition core.hpp:1744
void reset(void)
Reset information.
Definition core.hpp:4697
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1686
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1685
@ SS_FAILED
Space is failed
Definition core.hpp:1684
Search engines
Gecode toplevel namespace
#define forceinline
Definition config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56