Branch data Line data Source code
1 : : #include <mutable/IR/HeuristicSearchPlanEnumerator.hpp>
2 : :
3 : : #include <cstring>
4 : : #include <execution>
5 : : #include <functional>
6 : : #include <memory>
7 : : #include <mutable/catalog/Catalog.hpp>
8 : : #include <mutable/Options.hpp>
9 : : #include <mutable/util/fn.hpp>
10 : :
11 : :
12 : : using namespace m;
13 : : using namespace m::pe;
14 : : using namespace m::pe::hs;
15 : :
16 : :
17 : : /*======================================================================================================================
18 : : * Options
19 : : *====================================================================================================================*/
20 : :
21 : : namespace {
22 : :
23 : : ///> command-line options for the HeuristicSearchPlanEnumerator
24 : : namespace options {
25 : :
26 : : /** The heuristic search vertex to use. */
27 : : const char *vertex = "SubproblemsArray";
28 : : /** The vertex expansion to use. */
29 : : const char *expand = "BottomUpComplete";
30 : : /** The heuristic function to use. */
31 : : const char *heuristic = "zero";
32 : : /** The search method to use. */
33 : : const char *search = "AStar";
34 : : /** The weighting factor to use. */
35 : : float weighting_factor = 1.f;
36 : : /** Whether to compute an initial upper bound for cost-based pruning. */
37 : : bool initialize_upper_bound = false;
38 : : /** The expansion budget for Anytime A*. */
39 : : uint64_t expansion_budget = std::numeric_limits<uint64_t>::max();
40 : :
41 : : }
42 : :
43 : : }
44 : :
45 : :
46 : : /*======================================================================================================================
47 : : * Helper functions
48 : : *====================================================================================================================*/
49 : :
50 : : namespace {
51 : :
52 : : template<typename State>
53 : 108 : std::array<Subproblem, 2> delta(const State &before_join, const State &after_join)
54 : : {
55 : 108 : std::array<Subproblem, 2> delta;
56 : 108 : M_insist(before_join.size() == after_join.size() + 1);
57 : 108 : auto after_it = after_join.cbegin();
58 : 108 : auto before_it = before_join.cbegin();
59 : 108 : auto out_it = delta.begin();
60 : :
61 [ + + ]: 398 : while (out_it != delta.end()) {
62 : 290 : M_insist(before_it != before_join.cend());
63 [ + - ]: 290 : if (after_it == after_join.cend()) {
64 : 0 : *out_it++ = *before_it++;
65 [ + + ]: 290 : } else if (*before_it == *after_it) {
66 : 74 : ++before_it;
67 : 74 : ++after_it;
68 : 74 : } else {
69 : 216 : *out_it++ = *before_it++;
70 : : }
71 : : }
72 : 108 : return delta;
73 : : }
74 : 1 :
75 : : template<typename PlanTable, typename State>
76 : 164 : void reconstruct_plan_bottom_up(const State &state, PlanTable &PT, const QueryGraph &G,const CardinalityEstimator &CE,
77 : : const CostFunction &CF)
78 : : {
79 [ + + + - : 164 : static cnf::CNF condition; // TODO: use join condition
# # # # ]
80 : :
81 : 164 : const State *parent = state.parent();
82 [ + + # # ]: 164 : if (not parent) return;
83 : 58 : reconstruct_plan_bottom_up(*parent, PT, G, CE, CF); // solve recursively
84 : 58 : const auto D = delta(*parent, state); // find joined subproblems
85 : 58 : M_insist(not PT.has_plan(D[0] | D[1]), "PlanTable must not contain plans for intermediate results");
86 : 58 : PT.update(G, CE, CF, D[0], D[1], condition); // update plan table
87 : 164 : }
88 : :
89 : : template<typename PlanTable, typename State>
90 : 20 : void reconstruct_plan_top_down(const State &goal, PlanTable &PT, const QueryGraph &G, const CardinalityEstimator &CE,
91 : : const CostFunction &CF)
92 : : {
93 : 20 : const State *current = &goal;
94 [ + + + - : 20 : static cnf::CNF condition; // TODO: use join condition
# # # # ]
95 : :
96 [ + + # # ]: 70 : while (current->parent()) {
97 : 50 : const State *parent = current->parent();
98 : 50 : const auto D = delta(*current, *parent); // find joined subproblems
99 : 50 : M_insist(not PT.has_plan(D[0] | D[1]), "PlanTable must not contain plans for intermediate results");
100 : 50 : PT.update(G, CE, CF, D[0], D[1], condition); // update plan table
101 : 50 : current = parent; // advance
102 : : }
103 : 20 : }
104 : :
105 : : /* Reconstruct a saved (partial) plan. */
106 : : template<typename PlanTable>
107 : 0 : void reconstruct_saved_plan(const std::vector<std::pair<Subproblem, Subproblem>> &saved_plan, PlanTable &PT,
108 : : const QueryGraph &G, const CardinalityEstimator &CE, const CostFunction &CF)
109 : : {
110 [ # # # # : 0 : static cnf::CNF condition; // TODO: use join condition
# # # # ]
111 [ # # # # ]: 0 : for (auto [left, right]: saved_plan) {
112 : 0 : M_insist(not PT.has_plan(left | right), "PlanTable must not contain plans for intermediate results");
113 : 3 : PT.update(G, CE, CF, left, right, condition);
114 : : }
115 : 0 : };
116 : : }
117 : :
118 : : namespace m::pe::hs {
119 : :
120 : : /* Run GOO from the starting state 'state' until all relations of the query graph are joined. Return the cost of the
121 : : * resulting (partial) plan. We save the found (partial) plan in the provided `plan`. */
122 : : template<typename PlanTable, typename State>
123 : 4 : double goo_path_completion(const State &state, PlanTable &PT, const QueryGraph &G, const AdjacencyMatrix &M,
124 : : const CardinalityEstimator &CE, const CostFunction &CF, binary_plan_type &plan)
125 : : {
126 : : /*----- Initialize nodes. -----*/
127 [ - + # # ]: 4 : m::pe::GOO::node nodes[G.num_sources()];
128 : 4 : std::size_t num_nodes = 0;
129 : 24 : state.for_each_subproblem([&](Subproblem S) {
130 : 16 : new (&nodes[num_nodes++]) m::pe::GOO::node(S, M.neighbors(S));
131 : 20 : }, G);
132 : :
133 : : /*----- Greedily enumerate all joins. -----*/
134 : 4 : const Subproblem All = Subproblem::All(G.num_sources());
135 : 4 : double cost = 0;
136 [ + - + - : 20 : m::pe::GOO{}.for_each_join([&](Subproblem left, Subproblem right) {
# # # # ]
137 [ + + + - : 12 : static cnf::CNF condition; // TODO: use join condition
# # # # ]
138 : 12 : plan.emplace_back(std::pair(left, right));
139 [ + + # # ]: 12 : if (All != (left|right)) {
140 : : /* We only consider the cost of the current join and discard the accumulated costs of the inputs. */
141 : 8 : const double old_cost_left = std::exchange(PT[left].cost, 0);
142 : 8 : const double old_cost_right = std::exchange(PT[right].cost, 0);
143 : 8 : cost += CF.calculate_join_cost(G, PT, CE, left, right, condition);
144 : 8 : PT[left].cost = old_cost_left;
145 : 8 : PT[right].cost = old_cost_right;
146 : 8 : }
147 : 16 : }, PT, G, M, CF, CE, nodes, nodes + num_nodes);
148 : :
149 : 4 : return cost;
150 : 4 : }
151 : : }
152 : :
153 : :
154 : : /*======================================================================================================================
155 : : * Heuristic Search States: class/static fields
156 : : *====================================================================================================================*/
157 : :
158 : : namespace m::pe::hs {
159 : : namespace search_states {
160 : :
161 : 1 : SubproblemsArray::allocator_type SubproblemsArray::allocator_;
162 : 1 : SubproblemTableBottomUp::allocator_type SubproblemTableBottomUp::allocator_;
163 : 1 : EdgesBottomUp::allocator_type EdgesBottomUp::allocator_;
164 : : EdgePtrBottomUp::Scratchpad EdgePtrBottomUp::scratchpad_;
165 : :
166 : : }
167 : : }
168 : :
169 : : namespace m::pe::hs {
170 : :
171 : : template<
172 : : typename PlanTable,
173 : : typename State,
174 : : typename Expand,
175 : : typename SearchAlgorithm,
176 : : template<typename, typename, typename> typename Heuristic,
177 : : ai::SearchConfigConcept StaticConfig
178 : : >
179 : 146 : bool heuristic_search(PlanTable &PT, const QueryGraph &G, const AdjacencyMatrix &M, const CostFunction &CF,
180 : : const CardinalityEstimator &CE, SearchAlgorithm &S,
181 : : const ai::SearchConfiguration<StaticConfig> &config)
182 : : {
183 : 146 : State::RESET_STATE_COUNTERS();
184 : :
185 : : if constexpr (StaticConfig::PerformCostBasedPruning) {
186 [ # # # # : 10 : if (Options::Get().statistics)
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # +
- + - # #
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
187 : 0 : std::cout << "initial upper bound is " << config.upper_bound << std::endl;
188 : : }
189 : :
190 : : try {
191 [ + - # # : 146 : State initial_state = Expand::template Start<State>(PT, G, M, CF, CE);
# # # # #
# + - # #
+ - # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
# # # # #
# + - # #
# # # # #
# + - # #
# # # # +
- # # # #
# # + - #
# # # # #
# # + - #
# # # # #
# # + - #
# + - + -
# # # # #
# # # # #
+ - + - +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
192 : : using H = Heuristic<PlanTable, State, Expand>;
193 [ + - # # : 150 : H h(PT, G, M, CF, CE);
# # # # #
# + + # #
+ + # # #
# # # # #
# # # # #
# + + + +
# # # # #
# # # # #
# # # # #
# + - # #
# # # # #
# + - # #
# # # # +
- # # # #
# # + - #
# # # # #
# # + - #
# # # # #
# # + - #
# + - + -
# # # # #
# # # # #
+ - + - +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
194 : :
195 : : /*----- Run the search algorithm. -----*/
196 [ + - # # : 126 : const State &goal = S.search(
# # # # #
# + + # #
+ + # # #
# # # # #
# # # # #
# + + + +
# # # # #
# # # # #
# # # # #
# + - # #
# # # # #
# + - # #
# # # # +
- # # # #
# # + - #
# # # # #
# # + - #
# # # # #
# # + - #
# - + - +
# # # # #
# # # # #
+ + + - +
+ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
197 [ + - # # : 126 : /* initial_state= */ std::move(initial_state),
# # # # #
# + - # #
+ - # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
# # # # #
# + - # #
# # # # #
# + - # #
# # # # +
- # # # #
# # + - #
# # # # #
# # + - #
# # # # #
# # + - #
# + - + -
# # # # #
# # # # #
+ - + - +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
198 : : /* expand= */ Expand{},
199 : : /* heuristic= */ h,
200 : 126 : /* config= */ config,
201 : : /*----- Context -----*/
202 : 126 : PT, G, M, CF, CE
203 : : );
204 [ + - - + : 104 : if (Options::Get().statistics)
# # # # #
# # # # #
# # # # #
# + - - +
# # # # +
- - + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - - +
+ - - + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - - +
# # # # #
# # # # #
# # # # #
# + - - +
# # # # #
# # # # #
# # + - -
+ # # # #
# # # # #
# # # + -
- + # # #
# # # # #
# # # # #
# # # + -
- + # # #
# # # # #
# # # # #
# # # + -
- + # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # +
- - + + -
- + + - -
+ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # +
- - + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
205 [ # # # # : 0 : S.dump(std::cout);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
206 : :
207 : : /*----- Reconstruct the plan from the found path to goal. -----*/
208 : : if constexpr (std::is_base_of_v<expansions::TopDown, Expand>) {
209 [ + - # # : 9 : reconstruct_plan_top_down(goal, PT, G, CE, CF);
# # # # +
- # # # #
# # # # +
- # # # #
# # # # +
- # # # #
# # # # #
# # # # #
# # + - +
- + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
210 : : } else {
211 : : static_assert(std::is_base_of_v<expansions::BottomUp, Expand>, "unexpected expansion");
212 [ + - # # : 95 : reconstruct_plan_bottom_up(goal, PT, G, CE, CF);
# # # # #
# + - # #
+ - # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
# # # # #
# + - # #
# # # # #
# + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
213 : : }
214 [ # # # # : 146 : } catch (std::logic_error) {
# # # # #
# # # # #
# # # # #
# - + - +
# # # # -
+ - + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# - + - +
- + - + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# - + - +
- + - + #
# # # # #
# # # # #
# # # # #
# # # # -
+ - + # #
# # - + -
+ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
215 : : /*----- Handle incomplete search not finding a plan. -----*/
216 : : /* Any incplete search may *not* find a plan and hence throw a `std::logic_error`. In this case, we can attempt
217 : : * to use a plan we found during initialization of the search. If we do no have such a plan, we resort to a
218 : : * complete search, e.g. `DPccp`. */
219 : : if constexpr (StaticConfig::PerformCostBasedPruning) {
220 [ # # # # : 0 : if (options::initialize_upper_bound) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
221 : : /* Fall back to initial plan from upper bound initialization. */
222 [ # # # # : 0 : if (not Options::Get().quiet)
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
223 [ # # # # : 0 : std::cout << "search did not reach a goal state, fall back to plan found during initialization"
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
224 [ # # # # : 0 : << std::endl;
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
225 [ # # # # : 0 : reconstruct_saved_plan(config.initial_plan, PT, G, CE, CF);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
226 : 0 : }
227 : : }
228 [ # # # # : 0 : if (not options::initialize_upper_bound) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
229 : : /* No plan available from upper bound initialization. Fall back to DPccp. */
230 [ # # # # : 0 : if (not Options::Get().quiet)
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
231 [ # # # # : 0 : std::cout << "search did not reach a goal state, fall back to DPccp" << std::endl;
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
232 [ # # # # : 0 : DPccp{}(G, CF, PT);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
233 : 0 : }
234 [ # # # # : 42 : } catch (ai::budget_exhausted_exception) {
# # # # #
# # # # #
# # # # #
# + - # #
# # # # +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - # #
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - # #
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # +
- # # # #
# # + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
235 : : /*--- No plan was found within the given budget for A* ⇒ use GOO to complete the *nearest* partial solution --*/
236 : : /* Find the set of states that is closest to the goal state, concerning path length. Among these states chose
237 : : * the state X with the lowest f-value (f(X)=g(X)+h(X)). In the case that this state is a goal state, the found
238 : : * path to this state is returned. Otherwise, use GOO from this state to find a plan. */
239 : :
240 [ # # # # : 42 : M_insist(SearchAlgorithm::use_anytime_search, "exception can only be thrown during anytime search");
# # # # #
# + + # #
+ + # # #
# # # # #
# # # # #
# + + + +
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
+ - # # +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
241 [ # # # # : 22 : if (Options::Get().statistics)
# # # # #
# # # # #
# # # # #
# + - - +
# # # # +
- - + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - - +
+ - - + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - - +
+ - - + #
# # # # #
# # # # #
# # # # #
# # # # +
- - + # #
# # + - -
+ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
242 [ # # # # : 0 : S.dump(std::cout);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
243 : :
244 : : using partition_type = typename SearchAlgorithm::state_manager_type::map_type; ///< map from State to StateInfo
245 [ # # # # : 22 : const auto &SM = S.state_manager();
# # # # #
# + - # #
+ - # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
+ - # # +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
246 [ # # # # : 22 : const auto &partitions = SM.partitions();
# # # # #
# + - # #
+ - # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
+ - # # +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
247 : :
248 : : /*----- Find the `last_state_found' as the starting state for path completion -----*/
249 : : /* Find the partition closest to the goal, i.e. the partition that minimizes the difference between the number
250 : : * of subproblems included in the states of the partition and the number of subproblems of the goal. Thus, the
251 : : * direction of traversal to finding this partition depends on the chosen search direction. For bottom-up
252 : : * search, traverse the partitions starting at the partition with each state only consisting of one subproblem,
253 : : * i.e. the goal of bottom-up Search. For top-down search, traverse the partitions in the reverse direction,
254 : : * starting at the partition with each state only consisting of base relations, i.e. the goal of top-down
255 : : * search. In the partition closest to the goal, choose the state X with ths smallest unweighted f(X). */
256 : 44 : auto find_partition_closest_to_goal = [](auto partitions) -> const partition_type & {
257 : 22 : auto it = std::find_if_not(
258 : 22 : partitions.begin(),
259 : 22 : partitions.end(),
260 : 49 : [](const partition_type &partition) -> bool { return partition.empty(); }
261 : : );
262 : 22 : M_insist(it != partitions.end(), "all partitions empty");
263 : 22 : return *it;
264 : : };
265 : :
266 [ # # # # : 66 : auto &last_partition = [&find_partition_closest_to_goal](auto partitions) -> const partition_type & {
# # # # #
# # # # #
# # # # #
# + - + -
# # # # +
- + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - + -
+ - + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - + -
+ - + - #
# # # # #
# # # # #
# # # # #
# # # # +
- + - # #
# # + - +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
267 : : if constexpr (std::is_base_of_v<expansions::TopDown, Expand>)
268 : 11 : return find_partition_closest_to_goal(partitions.reverse());
269 : : else
270 : 11 : return find_partition_closest_to_goal(partitions);
271 : 22 : }(partitions);
272 : :
273 : : using entry_type = SearchAlgorithm::state_manager_type::map_type::value_type;
274 : 82 : auto min_state = [&config](const entry_type *best, const entry_type &next) -> const entry_type* {
275 : : /** Compute the *f*-value of an entry in the state manager. */
276 : 180 : auto f = [&config](const entry_type &e) {
277 : : if constexpr (SearchAlgorithm::use_weighted_search)
278 : 18 : return e.first.g() + e.second.h / config.weighting_factor;
279 : : else
280 : 102 : return e.first.g() + e.second.h;
281 : : };
282 : 60 : const double f_best = f(*best);
283 : 60 : const double f_next = f(next);
284 [ # # # # : 60 : return f_best <= f_next ? best : &next;
# # # # #
# + + # #
+ + # # #
# # # # #
# # # # #
# + + + +
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + + + +
# # # # #
# # # # #
+ + # # +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
285 : : };
286 : :
287 [ # # # # : 22 : auto &last_state_found = std::accumulate(
# # # # #
# + - # #
+ - # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
+ - # # +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
288 : 22 : /* first= */ last_partition.begin(),
289 : 22 : /* last= */ last_partition.end(),
290 : 22 : /* init= */ &*last_partition.begin(),
291 : 22 : /* op= */ min_state
292 : 22 : )->first;
293 : :
294 : : /*----- Check whether the 'last_state_found' is a goal state already -----*/
295 : : /* This may happen when a goal state is added to the state manager during vertex expansion but it is never
296 : : * popped from the queue and expanded itself. If the `last_state_found` is a goal state, we can directly
297 : : * reconstruct the path. */
298 [ # # # # : 22 : if (Expand::is_goal(last_state_found, PT, G, M, CF, CE)) {
# # # # #
# # # # #
# # # # #
# + - + +
# # # # +
- - + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - - +
+ - - + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - - +
+ - - + #
# # # # #
# # # # #
# # # # #
# # # # +
- + + # #
# # + - +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
299 : : if (std::is_base_of_v<expansions::BottomUp, Expand>)
300 [ # # # # : 1 : reconstruct_plan_bottom_up(last_state_found, PT, G, CE, CF);
# # # # #
# + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
301 : : else
302 [ # # # # : 6 : reconstruct_plan_top_down(last_state_found, PT, G, CE, CF);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # + - #
# + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
303 : 7 : } else if constexpr (std::is_base_of_v<expansions::BottomUp, Expand>) {
304 : : /*----- BottomUp -----*/
305 : : /* The `last_state_found` is *not* a goal state. We need to *finish* the partial solution using a greedy
306 : : * approach. */
307 : :
308 : : /* Reconstruct partial plan found so far. */
309 [ # # # # : 10 : reconstruct_plan_bottom_up(last_state_found, PT, G, CE, CF);
# # # # #
# + - # #
+ - # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
310 : :
311 : : /* Initialize nodes with the subproblems of the starting state */
312 [ # # # # : 50 : pe::GOO::node nodes[G.num_sources()];
# # # # #
# # # # #
# # # # #
# - + + +
# # # # -
+ + + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# - + + +
- + + + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
313 : 0 : std::size_t num_nodes = 0;
314 [ # # # # : 27 : last_state_found.for_each_subproblem([&](Subproblem S) {
# # # # #
# # # # #
# # # # #
# + + + +
# # # # +
+ + + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + + + +
+ + + + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
315 : 27 : nodes[num_nodes++] = pe::GOO::node(S, M.neighbors(S));
316 : 27 : }, G);
317 : :
318 : : /* Run GOO from the starting state and update the PlanTable accordingly */
319 [ # # # # : 10 : pe::GOO{}.compute_plan(PT, G, M, CF, CE, nodes, nodes + num_nodes);
# # # # #
# + - # #
+ - # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
320 : :
321 [ # # # # : 10 : M_insist(PT.has_plan(Subproblem::All(G.num_sources())), "No full plan found");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - + -
+ - # # #
# # # + -
+ - + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - + -
+ - + - +
- + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
322 : :
323 : :
324 : 10 : } else {
325 : : /*----- TopDown -----*/
326 : : static_assert(std::is_base_of_v<expansions::TopDown, Expand>);
327 [ # # # # : 5 : static cnf::CNF condition;
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
+ - + - +
- + - # #
# # # # #
# # # # #
# # # # #
# # # + +
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
328 : :
329 : : /* Initialize worklist with the subproblems of the starting state. */
330 : 5 : std::vector<Subproblem> worklist;
331 [ # # # # : 5 : worklist.reserve(G.num_sources());
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # + -
+ - # # #
# # # # #
# # + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
332 [ # # # # : 5 : worklist.insert(worklist.end(), last_state_found.cbegin(), last_state_found.cend());
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # + - +
- + - + -
+ - + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # +
- + - + -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
333 : :
334 : : /* Compute the remaining plan with TDGOO. */
335 : 15 : auto update_PT = [&](Subproblem left, Subproblem right) {
336 : 10 : PT.update(G, CE, CF, left, right, condition); // TODO: use actual condition
337 : 10 : };
338 [ # # # # : 5 : pe::TDGOO{}.for_each_join(update_PT, PT, G, M, CF, CE, std::move(worklist));
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # + -
+ - # # #
# # # # #
# # + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
339 : :
340 : : /* To complete the plan found by TDGOO, fill the PlanTable with the joins initially found by the search */
341 [ # # # # : 5 : reconstruct_plan_top_down(last_state_found, PT, G, CE, CF);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # + -
+ - # # #
# # # # #
# # + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
342 : :
343 [ # # # # : 5 : M_insist(PT.has_plan(Subproblem::All(G.num_sources())), "No full plan found");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # + - +
- + - + -
+ - + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # +
- + - + -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
344 : 5 : }
345 [ # # # # : 22 : }
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
346 : : #ifdef COUNTERS
347 [ + - # # : 126 : if (Options::Get().statistics) {
# # # # #
# + - # #
+ - # # #
# # # # #
# # # # #
# + - + -
# # # # #
# # # # #
# # # # #
# + - # #
# # # # #
# + - # #
# # # # +
- # # # #
# # + - #
# # # # #
# # + - #
# # # # #
# # + - #
# + - + -
# # # # #
# # # # #
+ - + - +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
348 : 0 : std::cout << "Vertices generated: " << State::NUM_STATES_GENERATED()
349 : 0 : << "\nVertices expanded: " << State::NUM_STATES_EXPANDED()
350 : 0 : << "\nVertices constructed: " << State::NUM_STATES_CONSTRUCTED()
351 : 0 : << "\nVertices disposed: " << State::NUM_STATES_DISPOSED()
352 : 0 : << std::endl;
353 : 0 : }
354 : : #endif
355 : 126 : return true;
356 : 82 : }
357 : :
358 : : }
359 : :
360 : : namespace {
361 : :
362 : : template<
363 : : typename PlanTable,
364 : : typename State,
365 : : typename Expand,
366 : : template<typename, typename, typename> typename Heuristic,
367 : : template<typename, typename, typename, typename, typename...> typename Search,
368 : : ai::SearchConfigConcept StaticConfig
369 : : >
370 : 81 : bool heuristic_search_helper(const char *vertex_str, const char *expand_str, const char *heuristic_str,
371 : : const char *search_str, PlanTable &PT, const QueryGraph &G, const AdjacencyMatrix &M,
372 : : const CostFunction &CF, const CardinalityEstimator &CE)
373 : : {
374 [ # # # # : 162 : if (streq(options::vertex, vertex_str ) and
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # +
- - + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
375 [ # # # # : 81 : streq(options::expand, expand_str ) and
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
376 [ # # # # : 81 : streq(options::heuristic, heuristic_str) and
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
377 : 81 : streq(options::search, search_str ))
378 : : {
379 : 81 : ai::SearchConfiguration<StaticConfig> config;
380 : :
381 : : if constexpr (StaticConfig::PerformCostBasedPruning) {
382 [ # # # # : 0 : if (options::initialize_upper_bound) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
383 : : /*----- Run GOO to compute upper bound of plan cost. -----*/
384 : : /* Obtain the sum of the costs of the left and the right subplan of the resulting initial plan. The
385 : : * costs considered for the search do not include the cardinality of the result set. Save the initial
386 : : * plan. */
387 [ # # # # : 0 : config.upper_bound = [&]() {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
388 : 0 : config.initial_plan->reserve(G.num_sources()-1);
389 : 0 : double cost_initial_plan = 0;
390 : 0 : State initial_state = expansions::BottomUpComplete::template Start<State>(PT, G, M, CF, CE);
391 [ # # # # : 0 : cost_initial_plan = goo_path_completion(initial_state, PT, G, M, CE, CF, config.initial_plan);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
392 : 0 : return cost_initial_plan;
393 : 0 : }();
394 : 0 : }
395 [ # # # # : 81 : } else if (options::initialize_upper_bound) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
396 : 0 : std::cerr << "WARNING: option --hs-init-upper-bound has no effect for the chosen search configuration"
397 : 0 : << std::endl;
398 : 0 : }
399 : :
400 : : if constexpr (StaticConfig::PerformWeightedSearch) {
401 : 0 : config.weighting_factor = options::weighting_factor;
402 [ # # # # : 81 : } else if (options::weighting_factor != 1.f) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
403 [ # # # # : 0 : std::cerr << "WARNING: option --hs-wf has no effect for the chosen search configuration"
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
404 [ # # # # : 0 : << std::endl;
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
405 : 0 : }
406 : :
407 : : if constexpr (StaticConfig::PerformAnytimeSearch) {
408 : 0 : config.expansion_budget = options::expansion_budget;
409 [ # # # # : 81 : } else if (options::expansion_budget != std::numeric_limits<uint64_t>::max()) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
410 [ # # # # : 0 : std::cerr << "WARNING: option --hs-budget has no effect for the chosen search configuration"
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
411 [ # # # # : 0 : << std::endl;
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
412 : 0 : }
413 : :
414 : : using H = Heuristic<PlanTable, State, Expand>;
415 : :
416 : : using SearchAlgorithm = Search<
417 : : State, Expand, H, StaticConfig,
418 : : /*----- context -----*/
419 : : PlanTable&,
420 : : const QueryGraph&,
421 : : const AdjacencyMatrix&,
422 : : const CostFunction&,
423 : : const CardinalityEstimator&
424 : : >;
425 : :
426 [ # # # # : 81 : SearchAlgorithm S(PT, G, M, CF, CE);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
427 : :
428 [ # # # # : 81 : return m::pe::hs::heuristic_search<
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
- + # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
429 : : PlanTable,
430 : : State,
431 : : Expand,
432 : : SearchAlgorithm,
433 : : Heuristic,
434 : : StaticConfig
435 : 81 : >(PT, G, M, CF, CE, S, config);
436 : 81 : }
437 : 0 : return false;
438 : :
439 : 81 : }
440 : :
441 : : }
442 : :
443 : : namespace m::pe::hs {
444 : :
445 : : template<typename PlanTable>
446 : 0 : void HeuristicSearch::operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const
447 : : {
448 : 0 : Catalog &C = Catalog::Get();
449 : 0 : auto &CE = C.get_database_in_use().cardinality_estimator();
450 : 0 : const AdjacencyMatrix &M = G.adjacency_matrix();
451 : :
452 : :
453 : : #define HEURISTIC_SEARCH(STATE, EXPAND, HEURISTIC, STATIC_CONFIG) \
454 : : if (heuristic_search_helper<PlanTable, \
455 : : search_states::STATE, \
456 : : expansions::EXPAND, \
457 : : heuristics::HEURISTIC, \
458 : : ai::genericAStar, \
459 : : config::STATIC_CONFIG \
460 : : >(#STATE, #EXPAND, #HEURISTIC, #STATIC_CONFIG, PT, G, M, CF, CE)) \
461 : : { \
462 : : goto matched_heuristic_search; \
463 : : }
464 : :
465 : : // bottom-up
466 : : // zero
467 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, zero, AStar )
# # # # ]
468 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, zero, AStar_with_cbp )
# # # # ]
469 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, zero, beam_search )
# # # # ]
470 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, zero, beam_search_with_cbp )
# # # # ]
471 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, zero, dynamic_beam_search )
# # # # ]
472 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, zero, anytimeAStar )
# # # # ]
473 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, zero, weighted_anytimeAStar )
# # # # ]
474 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, zero, anytimeAStar_with_cbp )
# # # # ]
475 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, zero, weighted_anytimeAStar_with_cbp )
# # # # ]
476 : :
477 : :
478 : : // sum
479 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, sum, AStar )
# # # # ]
480 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, sum, AStar_with_cbp )
# # # # ]
481 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, sum, weighted_AStar )
# # # # ]
482 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, sum, lazyAStar )
# # # # ]
483 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, sum, beam_search )
# # # # ]
484 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, sum, dynamic_beam_search )
# # # # ]
485 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, sum, anytimeAStar )
# # # # ]
486 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, sum, weighted_anytimeAStar )
# # # # ]
487 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, sum, anytimeAStar_with_cbp )
# # # # ]
488 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, sum, weighted_anytimeAStar_with_cbp )
# # # # ]
489 : :
490 : :
491 : : // scaled_sum
492 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, scaled_sum, AStar )
# # # # ]
493 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, scaled_sum, beam_search )
# # # # ]
494 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, scaled_sum, dynamic_beam_search )
# # # # ]
495 : :
496 : : // avg_sel
497 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, avg_sel, AStar )
# # # # ]
498 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, avg_sel, beam_search )
# # # # ]
499 : :
500 : : // product
501 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, product, AStar )
# # # # ]
502 : :
503 : : // GOO
504 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, GOO, AStar )
# # # # ]
505 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, GOO, AStar_with_cbp )
# # # # ]
506 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, GOO, weighted_AStar )
# # # # ]
507 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, GOO, beam_search )
# # # # ]
508 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, GOO, dynamic_beam_search )
# # # # ]
509 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, GOO, anytimeAStar )
# # # # ]
510 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, GOO, weighted_anytimeAStar )
# # # # ]
511 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, GOO, anytimeAStar_with_cbp )
# # # # ]
512 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, GOO, weighted_anytimeAStar_with_cbp )
# # # # ]
513 : :
514 : :
515 : : // HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, bottomup_lookahead_cheapest, AStar )
516 : : // HEURISTIC_SEARCH( SubproblemsArray, BottomUpComplete, perfect_oracle, AStar )
517 : :
518 : : // top-down
519 : : // zero
520 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, zero, AStar )
# # # # ]
521 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, zero, AStar_with_cbp )
# # # # ]
522 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, zero, beam_search )
# # # # ]
523 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, zero, dynamic_beam_search )
# # # # ]
524 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, zero, anytimeAStar )
# # # # ]
525 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, zero, weighted_anytimeAStar )
# # # # ]
526 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, zero, anytimeAStar_with_cbp )
# # # # ]
527 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, zero, weighted_anytimeAStar_with_cbp)
# # # # ]
528 : :
529 : : // sqrt_sum
530 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, sqrt_sum, AStar )
# # # # ]
531 : :
532 : : // sum
533 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, sum, AStar )
# # # # ]
534 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, sum, AStar_with_cbp )
# # # # ]
535 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, sum, weighted_AStar )
# # # # ]
536 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, sum, beam_search )
# # # # ]
537 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, sum, dynamic_beam_search )
# # # # ]
538 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, sum, anytimeAStar )
# # # # ]
539 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, sum, weighted_anytimeAStar )
# # # # ]
540 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, sum, anytimeAStar_with_cbp )
# # # # ]
541 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, sum, weighted_anytimeAStar_with_cbp)
# # # # ]
542 : :
543 : : // GOO
544 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, GOO, AStar )
# # # # ]
545 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, GOO, AStar_with_cbp )
# # # # ]
546 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, GOO, weighted_AStar )
# # # # ]
547 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, GOO, beam_search )
# # # # ]
548 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, GOO, dynamic_beam_search )
# # # # ]
549 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, GOO, anytimeAStar )
# # # # ]
550 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, GOO, weighted_anytimeAStar )
# # # # ]
551 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, GOO, anytimeAStar_with_cbp )
# # # # ]
552 [ # # # # : 0 : HEURISTIC_SEARCH( SubproblemsArray, TopDownComplete, GOO, weighted_anytimeAStar_with_cbp)
# # # # ]
553 : :
554 : :
555 [ # # # # : 0 : throw std::invalid_argument("illegal search configuration");
# # # # ]
556 : : #undef HEURISTIC_SEARCH
557 : :
558 : : matched_heuristic_search:;
559 : : #ifndef NDEBUG
560 : 0 : if (Options::Get().statistics) {
561 : 0 : auto plan_cost = [&PT]() -> double {
562 : 0 : const Subproblem left = PT.get_final().left;
563 : 0 : const Subproblem right = PT.get_final().right;
564 : 0 : return PT[left].cost + PT[right].cost;
565 : : };
566 : :
567 : 0 : const double hs_cost = plan_cost();
568 : 0 : DPccp dpccp;
569 [ # # # # : 0 : dpccp(G, CF, PT);
# # # # ]
570 [ # # # # : 0 : const double dp_cost = plan_cost();
# # # # ]
571 : :
572 [ # # # # : 0 : std::cout << "AI: " << hs_cost << ", DP: " << dp_cost << ", Δ " << hs_cost / dp_cost << 'x' << std::endl;
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
573 [ # # # # : 0 : if (hs_cost > dp_cost)
# # # # ]
574 [ # # # # : 0 : std::cout << "WARNING: Suboptimal solution!" << std::endl;
# # # # #
# # # # #
# # ]
575 : 0 : }
576 : : #endif
577 : 0 : }
578 : :
579 : : // explicit template instantiation
580 : : template void HeuristicSearch::operator()(enumerate_tag, PlanTableSmallOrDense &PT, const QueryGraph &G, const CostFunction &CF) const;
581 : : template void HeuristicSearch::operator()(enumerate_tag, PlanTableLargeAndSparse &PT, const QueryGraph &G, const CostFunction &CF) const;
582 : :
583 : : }
584 : :
585 : :
586 : : namespace {
587 : :
588 : : __attribute__((constructor(202)))
589 : 1 : void register_heuristic_search_plan_enumerator()
590 : : {
591 : 1 : Catalog &C = Catalog::Get();
592 [ - + ]: 1 : C.register_plan_enumerator(
593 : 1 : C.pool("HeuristicSearch"),
594 [ + - ]: 1 : std::make_unique<HeuristicSearch>(),
595 : : "uses heuristic search to find a plan; "
596 : : "found plans are optimal when the search method is optimal and the heuristic is admissible"
597 : : );
598 : :
599 : : /*----- Command-line arguments -----------------------------------------------------------------------------------*/
600 : 1 : C.arg_parser().add<const char*>(
601 : : /* group= */ "HeuristicSearch",
602 : : /* short= */ nullptr,
603 : : /* long= */ "--hs-vertex",
604 : : /* description= */ "the heuristic search vertex to use",
605 : 0 : [] (const char *str) { options::vertex = str; }
606 : : );
607 : 1 : C.arg_parser().add<const char*>(
608 : : /* group= */ "HeuristicSearch",
609 : : /* short= */ nullptr,
610 : : /* long= */ "--hs-expand",
611 : : /* description= */ "the vertex expansion to use",
612 : 0 : [] (const char *str) { options::expand = str; }
613 : : );
614 : 1 : C.arg_parser().add<const char*>(
615 : : /* group= */ "HeuristicSearch",
616 : : /* short= */ nullptr,
617 : : /* long= */ "--hs-heuristic",
618 : : /* description= */ "the heuristic function to use",
619 : 0 : [] (const char *str) { options::heuristic = str; }
620 : : );
621 : 1 : C.arg_parser().add<const char*>(
622 : : /* group= */ "HeuristicSearch",
623 : : /* short= */ nullptr,
624 : : /* long= */ "--hs-search",
625 : : /* description= */ "the search method to use",
626 : 0 : [] (const char *str) { options::search = str; }
627 : : );
628 : 1 : C.arg_parser().add<float>(
629 : : /* group= */ "HeuristicSearch",
630 : : /* short= */ nullptr,
631 : : /* long= */ "--hs-wf",
632 : : /* description= */ "the weighting factor for the heuristic value (defaults to 1)",
633 : 0 : [] (float wf) { options::weighting_factor = wf; }
634 : : );
635 : 1 : C.arg_parser().add<bool>(
636 : : /* group= */ "HeuristicSearch",
637 : : /* short= */ nullptr,
638 : : /* long= */ "--hs-init-upper-bound",
639 : : /* description= */ "greedily compute an initial upper bound for cost-based pruning",
640 : 0 : [] (bool) { options::initialize_upper_bound = true; }
641 : : );
642 : 1 : C.arg_parser().add<uint64_t>(
643 : : /* group= */ "HeuristicSearch",
644 : : /* short= */ nullptr,
645 : : /* long= */ "--hs-budget",
646 : : /* description= */ "the expansion budget to use for Anytime A*",
647 : 0 : [] (uint64_t n) { options::expansion_budget = n; }
648 : : );
649 : 1 : }
650 : :
651 : : }
|
