summaryrefslogtreecommitdiff
path: root/casa/search
diff options
context:
space:
mode:
Diffstat (limited to 'casa/search')
-rw-r--r--casa/search/Filter.H60
-rw-r--r--casa/search/Goal.H32
-rw-r--r--casa/search/GreedyFilter.H64
-rw-r--r--casa/search/Guide.H34
-rw-r--r--casa/search/Heuristic.H32
-rw-r--r--casa/search/Node.H137
-rw-r--r--casa/search/Search.H460
-rw-r--r--casa/search/SearchConfiguration.H99
-rw-r--r--casa/search/SearchFinish.H55
-rw-r--r--casa/search/SearchIteration.H28
-rw-r--r--casa/search/StateGuide.H34
-rw-r--r--casa/search/StateSpace.H50
12 files changed, 1085 insertions, 0 deletions
diff --git a/casa/search/Filter.H b/casa/search/Filter.H
new file mode 100644
index 0000000..071eb71
--- /dev/null
+++ b/casa/search/Filter.H
@@ -0,0 +1,60 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef FILTER_H
+#define FILTER_H
+
+#include <set>
+
+#include "search/Heuristic.H"
+#include "search/Goal.H"
+
+// Controls which children (immediately reachable neighbors) are explored by a
+// search. The filtering happens after children are enumerated; limitations that
+// apply to the enumeration process itself (such as only computing a fixed
+// number of random children) are better managed by the parameters in a
+// SearchConfiguration, which are passed to the getChildren() method of the
+// StateSpace.
+
+template<class STATE, class COST>class Filter {
+public:
+ typedef Heuristic<STATE,COST> HeuristicT;
+ typedef Goal<STATE> GoalT;
+
+ virtual ~Filter() {}
+
+ // Mutates the children set; the heuristic and goal may guide the mutation.
+ virtual void operator()
+ (std::set<STATE>&children, const HeuristicT&heuristic, const GoalT&goal)
+ const {}
+
+ // Just as the other operator(), but, at the filter's option, the parent may
+ // be considered to be its own child. This is useful, for example, when the
+ // SearchConfiguration is sampling a random subset of the children and the
+ // filter would prefer a different pool to choose from.
+ virtual void operator()
+ (std::set<STATE>&children,
+ const STATE&parent,
+ const HeuristicT&heuristic,
+ const GoalT&goal) const {
+ children.insert(parent);
+ operator()(children, heuristic, goal);
+ }
+};
+
+#endif
diff --git a/casa/search/Goal.H b/casa/search/Goal.H
new file mode 100644
index 0000000..d7209c8
--- /dev/null
+++ b/casa/search/Goal.H
@@ -0,0 +1,32 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef GOAL_H
+#define GOAL_H
+
+// Decides when a search should terminate because it has found a solution. In
+// some applications the goal's RTTI is also used to inform other search objects
+// (such as the heuristic).
+
+template<class STATE>class Goal {
+public:
+ virtual ~Goal() {}
+ virtual bool isGoal(const STATE&state) = 0;
+};
+
+#endif
diff --git a/casa/search/GreedyFilter.H b/casa/search/GreedyFilter.H
new file mode 100644
index 0000000..47ddef4
--- /dev/null
+++ b/casa/search/GreedyFilter.H
@@ -0,0 +1,64 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef GREEDYFILTER_H
+#define GREEDYFILTER_H
+
+#include "search/Filter.H"
+
+// A specialization of Filter where only the heuristically best child is
+// explored. Furthermore, if given the option to treat the parent as a child,
+// the filter will only have the search explore children if at least one of them
+// is heuristically better than the parent.
+
+template<class STATE, class COST>class GreedyFilter :
+ public Filter<STATE, COST> {
+ typedef Heuristic<STATE, COST> HeuristicT;
+ typedef Goal<STATE> GoalT;
+
+public:
+ void operator()
+ (std::set<STATE>&children, const HeuristicT&heuristic, const GoalT&goal)
+ const {
+ typename std::set<STATE>::iterator best = children.end();
+ COST score = 0;
+ for(typename std::set<STATE>::iterator
+ iterator = children.begin(),
+ end = children.end();
+ iterator != end;
+ ++iterator) {
+ COST estimate = heuristic.estimate(*iterator, goal);
+ if (best == children.end() || estimate < score) {
+ best = iterator;
+ score = estimate;
+ }
+ }
+ for(typename std::set<STATE>::iterator
+ iterator = children.begin(),
+ end = children.end();
+ iterator != end;){
+ if (iterator == best) {
+ ++iterator;
+ } else {
+ children.erase(iterator++);
+ }
+ }
+ }
+};
+
+#endif
diff --git a/casa/search/Guide.H b/casa/search/Guide.H
new file mode 100644
index 0000000..797d39f
--- /dev/null
+++ b/casa/search/Guide.H
@@ -0,0 +1,34 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef GUIDE_H
+#define GUIDE_H
+
+// Decides the order in which states are explored. Usual policies include
+// visiting the heuristically best states first, visiting states whose distance
+// from the start state added to the heuristic is minimal, visiting states
+// randomly, etc. There is provision to treat start states specially.
+
+template<class STATE, class COST>class Guide {
+public:
+ virtual ~Guide() {}
+ virtual COST rankStart(const Node<STATE, COST>&start) const = 0;
+ virtual COST rank(const Node<STATE, COST>&node) const = 0;
+};
+
+#endif
diff --git a/casa/search/Heuristic.H b/casa/search/Heuristic.H
new file mode 100644
index 0000000..40affe5
--- /dev/null
+++ b/casa/search/Heuristic.H
@@ -0,0 +1,32 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef HEURISTIC_H
+#define HEURISTIC_H
+
+#include "search/Goal.H"
+
+// Rates the quality of a state (never a path).
+
+template<class STATE, class COST>class Heuristic {
+public:
+ virtual ~Heuristic() {}
+ virtual COST estimate(const STATE&state, const Goal<STATE>&goal) const = 0;
+};
+
+#endif
diff --git a/casa/search/Node.H b/casa/search/Node.H
new file mode 100644
index 0000000..5e5b478
--- /dev/null
+++ b/casa/search/Node.H
@@ -0,0 +1,137 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef NODE_H
+#define NODE_H
+
+#include <cassert>
+#include <iostream>
+#include <set>
+
+// Represents an explored state, its heuristic estimate, the best known path
+// leading to that state, and other nodes whose best paths this state is on.
+
+template<class STATE, class COST>class Node {
+protected:
+ typedef Node<STATE,COST>* Edge;
+
+ // The node immediately preceding this one on a best path.
+ Edge parent;
+ // The state.
+ const STATE state;
+ // The distance from the start state along the best path.
+ COST traveled;
+ // The heuristic estimate of the distance to a goal state.
+ COST estimate;
+ // The set of nodes who have this one as their parent.
+ std::set<Edge> children;
+
+public:
+ Node(Edge parent, const STATE&state, COST traveled, COST estimate) :
+ parent(parent),
+ state(state),
+ traveled(traveled),
+ estimate(estimate) {
+ if (parent) {
+ parent->children.insert(this);
+ }
+ }
+
+ virtual ~Node() {
+ if (parent) {
+ parent->removeChild(this);
+ }
+ for (typename std::set<Edge>::iterator
+ iterator = children.begin(),
+ end = children.end();
+ iterator != end;) {
+ Edge child = *iterator;
+ ++iterator;
+ removeChild(child);
+ }
+ }
+
+ const STATE&getState() const {
+ return state;
+ }
+
+ COST getTraveled() const {
+ return traveled;
+ }
+ void setTraveled(COST traveled) {
+ this->traveled = traveled;
+ }
+
+ COST getEstimate() const {
+ return estimate;
+ }
+ void setEstimate(COST estimate) {
+ this->estimate = estimate;
+ }
+
+ Edge getParent() const {
+ return parent;
+ }
+
+ const std::set<Edge>&getChildren() const {
+ return children;
+ }
+
+ void addChild(Edge child) {
+ assert(child);
+ if (child->parent) {
+ if (child->parent == this) {
+ return;
+ }
+ child->parent->removeChild(child);
+ }
+ child->parent = this;
+ children.insert(child);
+ }
+
+ void removeChild(Edge child) {
+ assert(child);
+ if (child->parent != this) {
+ return;
+ }
+ child->parent = NULL;
+ children.erase(child);
+ }
+
+ // Comparisons are made solely by state.
+#define COMP(op) bool operator op(const Node&other) const { \
+ return state op other.state; \
+ }
+ COMP(<);
+ COMP(>);
+ COMP(==);
+ COMP(!=);
+#undef COMP
+};
+
+template<class STATE, class COST>std::ostream&operator <<
+ (std::ostream&out, const Node<STATE, COST>node) {
+ out << node.getState() << '(' << node.getTraveled() << '+' <<
+ node.getEstimate() << "*)";
+ if (node.getParent()) {
+ return out << "<-" << *node.getParent();
+ }
+ return out;
+}
+
+#endif
diff --git a/casa/search/Search.H b/casa/search/Search.H
new file mode 100644
index 0000000..0524ea5
--- /dev/null
+++ b/casa/search/Search.H
@@ -0,0 +1,460 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef SEARCH_H
+#define SEARCH_H
+
+#include <cassert>
+#include <vector>
+#include <set>
+
+#include "utility/pless.H"
+#include "utility/relation.H"
+
+#include "events/EventSource.H"
+
+#include "search/SearchConfiguration.H"
+#include "search/Node.H"
+#include "search/StateSpace.H"
+#include "search/Heuristic.H"
+#include "search/Guide.H"
+#include "search/Goal.H"
+#include "search/Filter.H"
+#include "search/SearchIteration.H"
+#include "search/SearchFinish.H"
+
+// A highly parameterized searching object.
+
+// Clients of this code mostly need to understand the objects passed at
+// construction time and, if pathfinding, fulfill the assumption that shortening
+// a path prefix will shorten an entire path. The complexity here is merely for
+// careful bookkeeping and memory management.
+
+// The general calling pattern is:
+// <constructor>
+// foreach search {
+// addStartState(...);
+// // Possibly more calls to addStartState(...)
+// search(...);
+// ... = getBest() // If we care about the best results
+// // Possibly more calls to search(...) if the search is restartable
+// clear();
+// }
+// <destructor>
+
+template<class STATE, class COST>class Search :
+ public EventSource<SearchIteration>,
+ public EventSource<SearchFinish<STATE, COST> > {
+public:
+ typedef Node<STATE, COST> NodeT;
+
+protected:
+ typedef relation<NodeT*, COST, true, false, pless<NodeT> >
+ VisitSetT;
+ typedef StateSpace<STATE, COST>
+ StateSpaceT;
+ typedef Heuristic<STATE, COST>
+ HeuristicT;
+ typedef Guide<STATE, COST>
+ GuideT;
+ typedef Goal<STATE> GoalT;
+ typedef Filter<STATE,COST> FilterT;
+ typedef SearchFinish<STATE, COST>
+ SearchFinishT;
+
+ SearchConfiguration configuration;
+ StateSpaceT* space;
+ HeuristicT* heuristic;
+ GuideT* guide;
+ GoalT* goal;
+ FilterT* filter;
+ bool oneBest;
+ VisitSetT open;
+ VisitSetT closed;
+ std::set<const NodeT*> best;
+ COST bestRank;
+
+public:
+ // See the classes SearchConfiguration, StateSpace, Heuristic, Guide, Goal,
+ // and Filter for documentation on their role in search. The parameter
+ // oneBest does not affect the method of search, but merely how many solutions
+ // are remembered in the case of a tie in the guide's ranking.
+ Search
+ (SearchConfiguration configuration,
+ StateSpaceT*space,
+ HeuristicT*heuristic,
+ GuideT*guide,
+ GoalT*goal,
+ FilterT*filter,
+ bool oneBest) :
+ configuration(configuration),
+ space(space),
+ heuristic(heuristic),
+ guide(guide),
+ goal(goal),
+ filter(filter),
+ oneBest(oneBest) {
+ assert(space);
+ assert(heuristic);
+ assert(guide);
+ assert(goal);
+ assert(filter);
+ }
+
+ virtual ~Search() {
+ clear();
+ }
+
+protected:
+ // A leak-free way to clear the set of best nodes.
+ void clearBest() {
+ if (!configuration.useClosed) {
+ for (typename std::set<const NodeT*>::const_iterator
+ iterator = best.begin(),
+ end = best.end();
+ iterator != end;
+ ++iterator) {
+ NodeT*node = const_cast<NodeT*>(*iterator);
+ if (open.key_find(node) == open.key_end()) {
+ delete node;
+ }
+ }
+ }
+ best.clear();
+ }
+
+ // See if the given node with the given guide ranking should be entered into
+ // the set of best nodes.
+ void updateBest(const NodeT&node, COST rank) {
+ if (rank < bestRank) {
+ clearBest();
+ }
+ if (best.empty()) {
+ best.insert(&node);
+ bestRank = rank;
+ } else if (rank == bestRank) {
+ if (oneBest) clearBest();
+ best.insert(&node);
+ }
+ }
+
+ // Pop the best ranked node from the set of nodes that have been seen but not
+ // explored.
+ NodeT&popBestOpen() {
+ assert(!open.empty());
+ typename VisitSetT::data_iterator pop = open.data_begin();
+ assert(pop->second);
+ if (configuration.useClosed) {
+ closed.key_insert(pop->second, pop->first);
+ }
+ NodeT&result = *(pop->second);
+ open.data_erase(pop);
+ return result;
+ }
+
+ // Get the children (immediately reachable neighbors) according to the
+ // SearchConfiguration.
+ std::set<STATE>getChildren(const NodeT&parent) {
+ if (configuration.proportionChildren) {
+ return space->getChildren
+ (parent.getState(), configuration.childrenAsk.proportion);
+ }
+ return space->getChildren
+ (parent.getState(), configuration.childrenAsk.count);
+ }
+
+ // Return true if a node should be discarded because we have seen a better one
+ // representing the same state, but not explored it yet. Also, forget about
+ // any nodes that we have seen but not explored if they represent the same
+ // state but are worse.
+ bool replaceInOpen(NodeT&parent, NodeT&node, COST traveled) {
+ typename VisitSetT::key_iterator similar = open.key_find(&node);
+ if (similar == open.key_end()) {
+ // The node does not have an already seen state.
+ return false;
+ }
+ NodeT*visited = similar->first;
+ assert(visited);
+ if (visited->getTraveled() <= traveled) {
+ // The node has an already seen state and cannot improve a path; discard
+ // it.
+ return true;
+ }
+ // The node has an already seen state, but may improve some paths; use it
+ // instead.
+ if (configuration.useClosed) {
+ parent.addChild(visited);
+ }
+ visited->setTraveled(traveled);
+ open.key_erase(similar);
+ COST rank = guide->rank(*visited);
+ open.key_insert(visited, rank);
+ updateBest(*visited, rank);
+ return true;
+ }
+
+ // Correct any out-of-date distance calculations when we change a path prefix.
+ // The arguments are the newly connected parent and child nodes.
+ void updateTraveled(NodeT&parent, NodeT&visited) {
+ // Setup to DFS from the visited node.
+ std::set<NodeT*>parentSet;
+ std::set<NodeT*>visitedSet;
+ parentSet.insert(&parent);
+ visitedSet.insert(&visited);
+ std::vector<const std::set<NodeT*>*>extrusion;
+ std::vector<typename std::set<NodeT*>::const_iterator>path;
+ extrusion.push_back(&parentSet);
+ path.push_back(extrusion.back()->begin());
+ extrusion.push_back(&visitedSet);
+ path.push_back(extrusion.back()->begin());
+ // Run the DFS, updating traveled distances and resorting.
+ for (;;) {
+ if (path.back() == extrusion.back()->end()) {
+ path.pop_back();
+ extrusion.pop_back();
+ if (path.empty()) {
+ break;
+ }
+ ++path.back();
+ } else {
+ typename
+ std::vector<typename std::set<NodeT*>::const_iterator>::
+ const_reverse_iterator back = path.rbegin();
+ NodeT&update = ***back;
+ assert(&update);
+ ++back;
+ NodeT&source = ***back;
+ assert(&source);
+ update.setTraveled(space->getTraveled(source, update.getState()));
+ COST rank = guide->rank(update);
+ typename VisitSetT::key_iterator moribund = open.key_find(&update);
+ if (moribund != open.key_end()) {
+ open.key_erase(moribund);
+ open.key_insert(&update, rank);
+ updateBest(update, rank);
+ ++path.back();
+ } else {
+ moribund = closed.key_find(&update);
+ assert(moribund != closed.key_end());
+ closed.key_erase(moribund);
+ closed.key_insert(&update, rank);
+ updateBest(update, rank);
+ // Push children.
+ extrusion.push_back(&update.getChildren());
+ path.push_back(extrusion.back()->begin());
+ }
+ }
+ }
+ }
+
+ // Return true if a node should be discarded because we have explored a better
+ // node representing the same state. Also, forget about any nodes that we
+ // have explored if they represent the same state but are worse.
+ bool replaceInClosed(NodeT&parent, NodeT&node, COST traveled) {
+ typename VisitSetT::key_iterator similar = closed.key_find(&node);
+ if (similar == closed.key_end()) {
+ // The node does not have an already explored state.
+ return false;
+ }
+ NodeT*visited = similar->first;
+ assert(visited);
+ if (visited->getTraveled() <= traveled) {
+ // The node has an already explored state and cannot improve a path;
+ // discard it.
+ return true;
+ }
+ // The node has an already explored state, but will improve some paths; use
+ // it instead.
+ parent.addChild(visited);
+ updateTraveled(parent, *visited);
+ return true;
+ }
+
+ //Add a newly seen node to the set of seen but not yet explored nodes.
+ void addNew(NodeT*node) {
+ COST rank = guide->rank(*node);
+ open.key_insert(node,rank);
+ updateBest(*node,rank);
+ }
+
+public:
+ // Add a start state before searching.
+ void addStartState(const STATE&start) {
+ NodeT*node =
+ new NodeT
+ (NULL,
+ start,
+ space->getTraveled(start),
+ heuristic->estimate(start, *goal));
+ addNew(node);
+ }
+
+ // Try to find a goal in the given budget. If restartable is true the search
+ // can be resumed by a later call to this method.
+ std::set<NodeT*>search(unsigned iterations, bool restartable) {
+ std::set<NodeT*>result;
+ if (open.empty()) {
+ return result;
+ }
+ for (unsigned i = iterations, j = configuration.prunePeriod;
+ i-- && result.empty();) {
+#ifdef SEARCH_PROGRESS
+ if (!(i & 0x3FF)) {
+ std::cout << i << " iterations left after this one" << std::endl;
+ }
+#endif
+ NodeT&parent = popBestOpen();
+ // If it is time to prune exploration to the most promising frontier:
+ if (!--j) {
+ j = configuration.prunePeriod;
+ std::set<const NodeT*>lineage;
+ typename std::set<const NodeT*>::const_iterator
+ lineageEnd = lineage.end();
+ for (const NodeT*k = &parent; k; k = k->getParent()) {
+ lineage.insert(k);
+ }
+ for (typename VisitSetT::key_iterator
+ k = closed.key_begin(),
+ kend = closed.key_end();
+ k != kend;) {
+ if (lineage.find(k->first) == lineageEnd) {
+ delete k->first;
+ closed.key_erase(k++);
+ } else {
+ ++k;
+ }
+ }
+ for (typename VisitSetT::key_iterator
+ k = open.key_begin(),
+ kend = open.key_end();
+ k != kend;++k) {
+ delete k->first;
+ }
+ open.clear();
+ }
+ // Explore.
+ std::set<STATE>children = getChildren(parent);
+ if (configuration.retryChildren) {
+ (*filter)(children, parent.getState(), *heuristic, *goal);
+ } else {
+ (*filter)(children, *heuristic, *goal);
+ }
+ // The flag to decide if the parent information can be deleted. It is
+ // true when we aren't looking for paths and the parent isn't part of the
+ // best set.
+ bool parentMoribund = false;
+ if (!configuration.useClosed) {
+ typename std::set<const NodeT*>::const_iterator
+ asBest = best.find(&parent),
+ bestEnd = best.end();
+ if (asBest == bestEnd) {
+ parentMoribund = true;
+ }
+ }
+ // See children.
+ for (typename std::set<STATE>::const_iterator
+ iterator = children.begin(),
+ end = children.end();
+ iterator != end;
+ ++iterator) {
+ COST traveled = space->getTraveled(parent, *iterator);
+ NodeT*node =
+ new NodeT
+ (configuration.useClosed ? &parent : NULL,
+ *iterator,
+ traveled,
+ heuristic->estimate(*iterator, *goal));
+ if (replaceInOpen(parent, *node, traveled)) {
+ // The new node was beaten by something in the open set.
+ delete node;
+ } else if (configuration.useClosed &&
+ replaceInClosed(parent, *node, traveled)) {
+ // The new node was beaten by something in the closed set.
+ delete node;
+ } else {
+ // The new node is worth exploring.
+ addNew(node);
+ // Track goals.
+ if (goal->isGoal(*iterator)) {
+ result.insert(node);
+ // If we are just interested in finding a goal, we can return now.
+ if (!restartable) {
+ if (parentMoribund) {
+ delete &parent;
+ }
+ // Complete the search.
+ SearchFinishT finish(*this, result, iterations - i, iterations);
+ EventSource<SearchFinishT>::dispatch(finish);
+ return result;
+ }
+ }
+ }
+ }
+ if (parentMoribund) {
+ delete &parent;
+ }
+ // Complete the iteration.
+ SearchIteration iteration;
+ EventSource<SearchIteration>::dispatch(iteration);
+ }
+ // Complete the search.
+ SearchFinishT finish(*this, result, iterations, iterations);
+ EventSource<SearchFinishT>::dispatch(finish);
+ return result;
+ }
+
+#define GET_SET(type, member, capMember) \
+ const type get ## capMember() const { \
+ return member; \
+ } \
+ void set ## capMember(const type&member) { \
+ this->member = member; \
+ }
+ GET_SET(SearchConfiguration, configuration, SearchConfiguration);
+ GET_SET(StateSpaceT*, space, Space);
+ GET_SET(HeuristicT*, heuristic, Heuristic);
+ GET_SET(GuideT*, guide, Guide);
+ GET_SET(GoalT*, goal, Goal);
+#undef GET_SET
+
+ const std::set<const NodeT*>getBest() const {
+ return best;
+ }
+
+ void clear() {
+ clearBest();
+ for (typename VisitSetT::key_iterator
+ k = open.key_begin(),
+ kend = open.key_end();
+ k != kend;
+ ++k) {
+ delete k->first;
+ }
+ open.clear();
+ for (typename VisitSetT::key_iterator
+ k = closed.key_begin(),
+ kend = closed.key_end();
+ k != kend;
+ ++k) {
+ delete k->first;
+ }
+ closed.clear();
+ }
+};
+
+#endif
diff --git a/casa/search/SearchConfiguration.H b/casa/search/SearchConfiguration.H
new file mode 100644
index 0000000..469a6ae
--- /dev/null
+++ b/casa/search/SearchConfiguration.H
@@ -0,0 +1,99 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef SEARCH_CONFIGURATION_H
+#define SEARCH_CONFIGURATION_H
+
+// Controls behaviors of the search that are parameterized by value, not code.
+
+struct SearchConfiguration {
+ // Should we keep a history of where we've been?
+ // Defaults to true.
+ // If false:
+ // Nodes are always without parent, so the search cannot find paths.
+ // States that have been visited and expanded may be visited and expanded
+ // again.
+ bool useClosed;
+
+ // Should we allow a parent to consider itself its own child?
+ // Defaults to false.
+ // If true:
+ // Node's states are forcibly added to their own sets of children.
+ // Filters can therefore choose the trivial (no-move) transition, like in
+ // hill-climbing.
+ // The search may spin at local maxima.
+ bool retryChildren;
+
+ // Should we limit the number of children by a proportion rather than a count?
+ // Defaults to true.
+ // If true:
+ // The state space is asked to enumerate a fixed proportion of children.
+ // States with more children will have longer enumerations.
+ // If false:
+ // The state space is asked to enumerate a fixed number of children.
+ // States with too few children will have all of them listed.
+ // States with too many children will not.
+ bool proportionChildren;
+
+ // How many children should we ask for?
+ // (See the documentation of proportionChildren above.)
+ union {
+ float proportion;
+ unsigned count;
+ } childrenAsk;
+
+ // How many iterations before each pruning of the space?
+ // Defaults to zero, which is treated as infinity.
+ // If nonzero:
+ // After the given number of iterations, the search will forget all visits
+ // except for the best nodes in the closed and open sets.
+ // This is sometimes an appropriate way to trade performance for memory.
+ unsigned prunePeriod;
+
+ SearchConfiguration() :
+ useClosed(true),
+ retryChildren(false),
+ proportionChildren(true),
+ prunePeriod(0) {
+ childrenAsk.proportion = 1;
+ }
+ SearchConfiguration
+ (bool useClosed,
+ bool retryChildren,
+ float proportion,
+ unsigned prunePeriod) :
+ useClosed(useClosed),
+ retryChildren(retryChildren),
+ proportionChildren(true),
+ prunePeriod(prunePeriod) {
+ childrenAsk.proportion = proportion;
+ }
+ SearchConfiguration
+ (bool useClosed,
+ bool retryChildren,
+ unsigned count,
+ unsigned prunePeriod) :
+ useClosed(useClosed),
+ retryChildren(retryChildren),
+ proportionChildren(false),
+ prunePeriod(prunePeriod) {
+ childrenAsk.count = count;
+ }
+};
+
+#endif
diff --git a/casa/search/SearchFinish.H b/casa/search/SearchFinish.H
new file mode 100644
index 0000000..67d4835
--- /dev/null
+++ b/casa/search/SearchFinish.H
@@ -0,0 +1,55 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef SEARCH_FINISH_H
+#define SEARCH_FINISH_H
+
+#include <set>
+
+#include "search/Node.H"
+
+// A forward declaration for when this header is included by Search.H:
+template<class, class>class Search;
+
+// A message broadcast when a search finishes (even if it was unsuccessful).
+
+template<class STATE, class COST>class SearchFinish {
+public:
+ typedef Search<STATE, COST> SearchT;
+ typedef Node<STATE, COST> NodeT;
+
+ const SearchT& source;
+ std::set<NodeT*> results;
+ unsigned iterations;
+ unsigned maxIterations;
+
+ SearchFinish
+ (const SearchT&source,
+ const std::set<NodeT*>&results,
+ unsigned iterations,
+ unsigned maxIterations) :
+ source(source),
+ results(results),
+ iterations(iterations),
+ maxIterations(maxIterations) {}
+};
+
+// For inclusion from anywhere but Search.H:
+#include "search/Search.H"
+
+#endif
diff --git a/casa/search/SearchIteration.H b/casa/search/SearchIteration.H
new file mode 100644
index 0000000..41a267a
--- /dev/null
+++ b/casa/search/SearchIteration.H
@@ -0,0 +1,28 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef SEARCH_ITERATION_H
+#define SEARCH_ITERATION_H
+
+// A message broadcast when a search completes an iteration but does not finish.
+
+class SearchIteration {
+ // Information about the progress of search could go here.
+};
+
+#endif
diff --git a/casa/search/StateGuide.H b/casa/search/StateGuide.H
new file mode 100644
index 0000000..0551904
--- /dev/null
+++ b/casa/search/StateGuide.H
@@ -0,0 +1,34 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef STATE_GUIDE_H
+#define STATE_GUIDE_H
+
+// A specialized guide that ranks strictly by the states' heuristic estimates.
+
+template<class STATE, class COST>class StateGuide : public Guide<STATE, COST> {
+public:
+ COST rankStart(const Node<STATE, COST>&start) const {
+ return start.getEstimate();
+ }
+ COST rank(const Node<STATE, COST>&node) const {
+ return node.getEstimate();
+ }
+};
+
+#endif
diff --git a/casa/search/StateSpace.H b/casa/search/StateSpace.H
new file mode 100644
index 0000000..5003f9b
--- /dev/null
+++ b/casa/search/StateSpace.H
@@ -0,0 +1,50 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef STATE_SPACE_H
+#define STATE_SPACE_H
+
+#include <set>
+
+#include "search/Node.H"
+
+// A description of a state space, namely the state interconnections and
+// distances (for pathfinding rather than statefinding).
+
+template<class STATE, class COST>class StateSpace {
+public:
+ virtual ~StateSpace() {}
+
+ // Determine the distance incurred by starting at the given state.
+ virtual COST getTraveled(const STATE&start) const = 0;
+
+ // Determine the total distance traveled to reach state after taking the best
+ // known path reaching parent.
+ virtual COST getTraveled(const Node<STATE, COST>&parent, const STATE&state)
+ const = 0;
+
+ // Enumerate a fixed fraction of the children of state, rounding up.
+ virtual std::set<STATE>getChildren(const STATE&state, float proportion)
+ const = 0;
+
+ // Enumerate the children of state up to some limit.
+ virtual std::set<STATE>getChildren(const STATE&state, unsigned count)
+ const = 0;
+};
+
+#endif
generated by cgit v1.2.1 (git 2.18.0) at 2024-05-02 05:44:12 +0000