1 #ifndef _SEARCH_HPP_CAW
2 #define _SEARCH_HPP_CAW
3
4
5 #include "search/search_common.hpp"
6
7 class EndOfSearch : public std::exception
8 { };
9
10 template<bool firstbranch>
doSearchBranch(const SearchOptions & so,Problem * p,SolutionStore * ss,RBase * rbase,TraceFollowingQueue * tfq,int depth)11 bool doSearchBranch(const SearchOptions& so, Problem* p, SolutionStore* ss,
12 RBase* rbase, TraceFollowingQueue* tfq, int depth)
13 {
14 info_out(1, "search depth: " << depth);
15 info_out(2, "Current partition: " << p->p_stack.dumpCurrentPartition());
16 if(depth > rbase->depth())
17 {
18 info_out(1, "Reached bottom of search");
19 return handlePossibleSolution(p,ss,rbase);
20 }
21 else
22 {
23 int branchcell = rbase->branchcell[depth];
24 int cell_start = p->p_stack.cellStartPos(branchcell);
25
26 if(firstbranch)
27 {
28 int first_val = rbase->branchvalue[depth];
29 int first_val_pos = p->p_stack.invval(first_val);
30 p->p_stack.swapPositions(first_val_pos, cell_start);
31 }
32
33 // We need to really make a copy of this, else we have problems
34 // with iterating through the cell in a sensible method.
35 vec1<int> cell = p->p_stack.cellAsVec(branchcell);
36
37 info_out(1, "branching on cell: " << cell);
38 // if we are on the first branch, doing a group search, the first value we branch on must be the rbase
39 // value, so we don't pass it to the sorter
40
41 orderCell(firstbranch ? cell.begin() + 1 : cell.begin(),
42 cell.end(),
43 firstbranch ? so.heuristic.search_first_branch_value : so.heuristic.search_value,
44 rbase);
45
46 for(int i : range1(cell.size()))
47 {
48 D_ASSERT(!(firstbranch && i == 1 && !ss->isMinimum(cell[i])));
49 D_ASSERT(!(firstbranch && i == 1 && cell[i] != rbase->branchvalue[depth]));
50 info_out(1, "consider branching on: " << cell[i]);
51 if(!firstbranch || !so.only_find_generators || ss->isMinimum(cell[i]))
52 {
53 // Find value we are branching on
54 int i_pos = p->p_stack.invval(cell[i]);
55
56 // Put it at the start of the partition
57 p->p_stack.swapPositions(cell_start, i_pos);
58
59 // Push state of the world
60 p->full_search_memory_backtracker.pushWorld();
61 info_out(1, "branch on: " << cell[i]);
62 Stats::container().node_count++;
63 if(so.node_limit >= 0 && Stats::container().node_count >= so.node_limit)
64 { throw EndOfSearch(); }
65 tfq->beginBranch();
66 SplitState branch_split = p->p_stack.split(branchcell, cell_start + 1);
67 (void)branch_split;
68 D_ASSERT(!branch_split.hasFailed());
69 tfq->endBranch();
70 debug_out(3, "search", "Perm State " << p->p_stack.printCurrentPartition());
71
72
73 SplitState split = tfq->execute_trace();
74 if(!split.hasFailed())
75 {
76 Stats::container().bad_leaves++;
77 bool ret;
78 if(firstbranch && i == 1)
79 ret = doSearchBranch<true>(so, p, ss, rbase, tfq, depth + 1);
80 else
81 ret = doSearchBranch<false>(so, p, ss, rbase, tfq, depth + 1);
82 if(so.only_find_generators && ret)
83 {
84 if(!firstbranch)
85 {
86 p->full_search_memory_backtracker.popWorld();
87 return true;
88 }
89 else
90 {
91 ss->markLastSolutionFrom(cell[1], cell[i]);
92 }
93 }
94 }
95 p->full_search_memory_backtracker.popWorld();
96 }
97 else
98 { debug_out(1, "search", "skipping " << i); }
99 }
100 info_out(1, "backtracking");
101 if(!firstbranch)
102 Stats::container().bad_internal_nodes++;
103 return false;
104 }
105
106 }
107
doSearch(Problem * p,const std::vector<AbstractConstraint * > & cons,const SearchOptions & so)108 SolutionStore doSearch(Problem* p, const std::vector<AbstractConstraint*>& cons, const SearchOptions& so)
109 {
110 Stats::reset();
111 timing_reset();
112 for(auto con : cons) p->addConstraint(con);
113 p->con_store.initConstraints(true);
114 p->tracer_generator.clearTrace();
115 RBase* rb = buildRBase(p, so.heuristic.rbase_cell, so.heuristic.rbase_value);
116 Stats::container().rBase_value_ordering = rb->value_ordering;
117 timing_event("Finish RBase");
118 SolutionStore solutions(rb);
119 if(!so.just_rbase)
120 {
121
122 TraceFollowingQueue tfq(rb->trace, &p->full_search_memory_backtracker);
123
124 p->p_stack.setAbstractQueue(&tfq);
125
126 Stats::container().node_count = 0;
127 try {
128 doSearchBranch<true>(so, p, &solutions, rb, &tfq, 1);
129 }
130 catch(const EndOfSearch&) {
131 debug_out(1, "search", "Node limit reached!");
132 }
133 }
134 debug_out(1, "search", "Node count:" << Stats::container().node_count);
135 delete rb;
136
137 RECORD_STATS(dumpStats());
138
139 return solutions;
140 }
141
doCosetSearch(Problem * p,const std::vector<AbstractConstraint * > & consCommon,const std::vector<AbstractConstraint * > & consL,const std::vector<AbstractConstraint * > & consR,const SearchOptions & so)142 SolutionStore doCosetSearch(Problem* p, const std::vector<AbstractConstraint*>& consCommon,
143 const std::vector<AbstractConstraint*>& consL,
144 const std::vector<AbstractConstraint*>& consR,
145 const SearchOptions& so)
146 {
147 Stats::reset();
148 (void)consL;
149 (void)consR;
150 for(auto i : consCommon)
151 {
152 p->addConstraint(i);
153 }
154 p->con_store.initConstraints(true);
155 p->tracer_generator.clearTrace();
156 RBase* rb = buildRBase(p, so.heuristic.rbase_cell, so.heuristic.rbase_value);
157 Stats::container().rBase_value_ordering = rb->value_ordering;
158 timing_event("Finish RBase");
159 SolutionStore solutions(rb);
160 if(!so.just_rbase)
161 {
162
163 TraceFollowingQueue tfq(rb->trace, &p->full_search_memory_backtracker);
164
165 p->p_stack.setAbstractQueue(&tfq);
166
167 Stats::container().node_count = 0;
168 doSearchBranch<true>(so, p, &solutions, rb, &tfq, 1);
169 }
170 debug_out(1, "search", "Node count:" << Stats::container().node_count);
171 delete rb;
172
173 RECORD_STATS(dumpStats());
174
175 return solutions;
176 }
177
178 #endif
179