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 * Contributing authors:
7 * Guido Tack <tack@gecode.org>
8 *
9 * Copyright:
10 * Christian Schulte, 2004
11 * Guido Tack, 2004
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#ifndef GECODE_SEARCH_SEQ_BAB_HH
39#define GECODE_SEARCH_SEQ_BAB_HH
40
41#include <gecode/search.hh>
42#include <gecode/search/support.hh>
43#include <gecode/search/worker.hh>
44#include <gecode/search/seq/path.hh>
45
46namespace Gecode { namespace Search { namespace Seq {
47
48 /// Implementation of depth-first branch-and-bound search engine
49 template<class Tracer>
50 class BAB : public Worker {
51 private:
52 /// Search tracer
53 Tracer tracer;
54 /// Search options
55 Options opt;
56 /// Current path in search tree
57 Path<Tracer> path;
58 /// Current space being explored
59 Space* cur;
60 /// Distance until next clone
61 unsigned int d;
62 /// Number of entries not yet constrained to be better
63 int mark;
64 /// Best solution found so far
65 Space* best;
66 public:
67 /// Initialize with space \a s and search options \a o
68 BAB(Space* s, const Options& o);
69 /// %Search for next better solution
70 Space* next(void);
71 /// Return statistics
72 Statistics statistics(void) const;
73 /// Constrain future solutions to be better than \a b
74 void constrain(const Space& b);
75 /// Reset engine to restart at space \a s
76 void reset(Space* s);
77 /// Return no-goods
78 NoGoods& nogoods(void);
79 /// Destructor
80 ~BAB(void);
81 };
82
83}}}
84
85#include <gecode/search/seq/bab.hpp>
86
87#endif
88
89// STATISTICS: search-seq