lemon-1.3: comparison lemon/insertion

equal deleted inserted replaced

-:53efd5c9a659
+:672d580c328f
 /// \ingroup tsp
 /// \file
 /// \brief Insertion algorithm for symmetric TSP
 #include <vector>
+#include <functional>
 #include <lemon/full_graph.h>
 #include <lemon/maps.h>
 #include <lemon/random.h>
 namespace lemon {
 /// \brief Insertion algorithm for symmetric TSP.
 ///
 /// InsertionTsp implements the insertion heuristic for solving
 /// symmetric \ref tsp "TSP".
 ///
-/// This is a basic TSP heuristic that has many variants.
+/// This is a fast and effective tour construction method that has
+/// many variants.
 /// It starts with a subtour containing a few nodes of the graph and it
 /// iteratively inserts the other nodes into this subtour according to a
 /// certain node selection rule.
 ///
-/// This implementation provides four different node selection rules,
+/// This method is among the fastest TSP algorithms, and it typically
-/// from which the most powerful one is used by default.
+/// provides quite good solutions (usually much better than
+/// \ref NearestNeighborTsp and \ref GreedyTsp).
+///
+/// InsertionTsp implements four different node selection rules,
+/// from which the most effective one (\e farthest \e node \e selection)
+/// is used by default.
+/// With this choice, the algorithm runs in O(n<sup>2</sup>) time.
 /// For more information, see \ref SelectionRule.
 ///
 /// \tparam CM Type of the cost map.
 template <typename CM>
 class InsertionTsp
 GRAPH_TYPEDEFS(FullGraph);
 const FullGraph &_gr;
 const CostMap &_cost;
 std::vector<Node> _notused;
-std::vector<Node> _path;
+std::vector<Node> _tour;
 Cost _sum;
 public:
 /// \brief Constants for specifying the node selection rule.
 /// Enum type containing constants for specifying the node selection
 /// rule for the \ref run() function.
 ///
 /// During the algorithm, nodes are selected for addition to the current
 /// subtour according to the applied rule.
-/// In general, the FARTHEST method yields the best tours, thus it is the
+/// The FARTHEST method is one of the fastest selection rules, and
-/// default option. The RANDOM rule usually gives somewhat worse results,
+/// it is typically the most effective, thus it is the default
-/// but it is much faster than the others and it is the most robust.
+/// option. The RANDOM rule usually gives slightly worse results,
+/// but it is more robust.
 ///
 /// The desired selection rule can be specified as a parameter of the
 /// \ref run() function.
 enum SelectionRule {
 /// An unvisited node having minimum distance from the current
 /// subtour is selected at each step.
-/// The algorithm runs in O(n<sup>3</sup>) time using this
+/// The algorithm runs in O(n<sup>2</sup>) time using this
 /// selection rule.
 NEAREST,
 /// An unvisited node having maximum distance from the current
 /// subtour is selected at each step.
-/// The algorithm runs in O(n<sup>3</sup>) time using this
+/// The algorithm runs in O(n<sup>2</sup>) time using this
 /// selection rule.
 FARTHEST,
 /// An unvisited node whose insertion results in the least
 /// increase of the subtour's total cost is selected at each step.
 /// The algorithm runs in O(n<sup>3</sup>) time using this
-/// selection rule.
+/// selection rule, but in most cases, it is almost as fast as
+/// with other rules.
 CHEAPEST,
 /// An unvisited node is selected randomly without any evaluation
 /// at each step.
 /// The global \ref rnd "random number generator instance" is used.
 /// \param rule The node selection rule. For more information, see
 /// \ref SelectionRule.
 ///
 /// \return The total cost of the found tour.
 Cost run(SelectionRule rule = FARTHEST) {
-_path.clear();
+_tour.clear();
 if (_gr.nodeNum() == 0) return _sum = 0;
 else if (_gr.nodeNum() == 1) {
-_path.push_back(_gr(0));
+_tour.push_back(_gr(0));
 return _sum = 0;
 }
 switch (rule) {
 case NEAREST:
 init(true);
-start<NearestSelection, DefaultInsertion>();
+start<ComparingSelection<std::less<Cost> >,
+DefaultInsertion>();
 break;
 case FARTHEST:
 init(false);
-start<FarthestSelection, DefaultInsertion>();
+start<ComparingSelection<std::greater<Cost> >,
+DefaultInsertion>();
 break;
 case CHEAPEST:
 init(true);
 start<CheapestSelection, CheapestInsertion>();
 break;
 /// This function returns a const reference to a vector
 /// that stores the node sequence of the found tour.
 ///
 /// \pre run() must be called before using this function.
 const std::vector<Node>& tourNodes() const {
-return _path;
+return _tour;
 }
 /// \brief Gives back the node sequence of the found tour.
 ///
 /// This function copies the node sequence of the found tour into
 /// the given standard container.
 ///
 /// \pre run() must be called before using this function.
 template <typename Container>
 void tourNodes(Container &container) const {
-container.assign(_path.begin(), _path.end());
+container.assign(_tour.begin(), _tour.end());
 }
 /// \brief Gives back the found tour as a path.
 ///
 /// This function copies the found tour as a list of arcs/edges into
 ///
 /// \pre run() must be called before using this function.
 template <typename Path>
 void tour(Path &path) const {
 path.clear();
-for (int i = 0; i < int(_path.size()) - 1; ++i) {
+for (int i = 0; i < int(_tour.size()) - 1; ++i) {
-path.addBack(_gr.arc(_path[i], _path[i+1]));
+path.addBack(_gr.arc(_tour[i], _tour[i+1]));
 }
-if (int(_path.size()) >= 2) {
+if (int(_tour.size()) >= 2) {
-path.addBack(_gr.arc(_path.back(), _path.front()));
+path.addBack(_gr.arc(_tour.back(), _tour.front()));
 }
 }
 /// @}
 // Initializes the algorithm
 void init(bool min) {
 Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
-_path.clear();
+_tour.clear();
-_path.push_back(_gr.u(min_edge));
+_tour.push_back(_gr.u(min_edge));
-_path.push_back(_gr.v(min_edge));
+_tour.push_back(_gr.v(min_edge));
 _notused.clear();
 for (NodeIt n(_gr); n!=INVALID; ++n) {
 if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
 _notused.push_back(n);
 }
 // Executes the algorithm
 template <class SelectionFunctor, class InsertionFunctor>
 void start() {
-SelectionFunctor selectNode(_gr, _cost, _path, _notused);
+SelectionFunctor selectNode(_gr, _cost, _tour, _notused);
-InsertionFunctor insertNode(_gr, _cost, _path, _sum);
+InsertionFunctor insertNode(_gr, _cost, _tour, _sum);
 for (int i=0; i<_gr.nodeNum()-2; ++i) {
 insertNode.insert(selectNode.select());
 }
-_sum = _cost[_gr.edge(_path.back(), _path.front())];
+_sum = _cost[_gr.edge(_tour.back(), _tour.front())];
-for (int i = 0; i < int(_path.size())-1; ++i) {
+for (int i = 0; i < int(_tour.size())-1; ++i) {
-_sum += _cost[_gr.edge(_path[i], _path[i+1])];
+_sum += _cost[_gr.edge(_tour[i], _tour[i+1])];
 }
 }
-// Implementation of the nearest selection rule
+// Implementation of the nearest and farthest selection rule
-class NearestSelection {
+template <typename Comparator>
+class ComparingSelection {
 public:
-NearestSelection(const FullGraph &gr, const CostMap &cost,
+ComparingSelection(const FullGraph &gr, const CostMap &cost,
-std::vector<Node> &path, std::vector<Node> &notused)
+std::vector<Node> &tour, std::vector<Node> &notused)
-: _gr(gr), _cost(cost), _path(path), _notused(notused) {}
+: _gr(gr), _cost(cost), _tour(tour), _notused(notused),
+_dist(gr, 0), _compare()
-Node select() const {
+{
-Cost insert_val = 0;
+// Compute initial distances for the unused nodes
-int insert_node = -1;
 for (unsigned int i=0; i<_notused.size(); ++i) {
-Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
+Node u = _notused[i];
-int min_node = 0;
+Cost min_dist = _cost[_gr.edge(u, _tour[0])];
+for (unsigned int j=1; j<_tour.size(); ++j) {
-for (unsigned int j=1; j<_path.size(); ++j) {
+Cost curr = _cost[_gr.edge(u, _tour[j])];
-Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
+if (curr < min_dist) {
-if (min_val > curr) {
+min_dist = curr;
-min_val = curr;
-min_node = j;
 }
 }
+_dist[u] = min_dist;
-if (insert_val > min_val || insert_node == -1) {
+}
-insert_val = min_val;
+}
-insert_node = i;
-}
+Node select() {
-}
+// Select an used node with minimum distance
-Node n = _notused[insert_node];
+Cost ins_dist = 0;
-_notused.erase(_notused.begin()+insert_node);
+int ins_node = -1;
+for (unsigned int i=0; i<_notused.size(); ++i) {
-return n;
+Cost curr = _dist[_notused[i]];
+if (_compare(curr, ins_dist) || ins_node == -1) {
+ins_dist = curr;
+ins_node = i;
+}
+}
+// Remove the selected node from the unused vector
+Node sn = _notused[ins_node];
+_notused[ins_node] = _notused.back();
+_notused.pop_back();
+// Update the distances of the remaining nodes
+for (unsigned int i=0; i<_notused.size(); ++i) {
+Node u = _notused[i];
+Cost nc = _cost[_gr.edge(sn, u)];
+if (nc < _dist[u]) {
+_dist[u] = nc;
+}
+}
+return sn;
 }
 private:
 const FullGraph &_gr;
 const CostMap &_cost;
-std::vector<Node> &_path;
+std::vector<Node> &_tour;
 std::vector<Node> &_notused;
+FullGraph::NodeMap<Cost> _dist;
+Comparator _compare;
 };
-// Implementation of the farthest selection rule
-class FarthestSelection {
-public:
-FarthestSelection(const FullGraph &gr, const CostMap &cost,
-std::vector<Node> &path, std::vector<Node> &notused)
-: _gr(gr), _cost(cost), _path(path), _notused(notused) {}
-Node select() const {
-Cost insert_val = 0;
-int insert_node = -1;
-for (unsigned int i=0; i<_notused.size(); ++i) {
-Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
-int min_node = 0;
-for (unsigned int j=1; j<_path.size(); ++j) {
-Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
-if (min_val > curr) {
-min_val = curr;
-min_node = j;
-}
-}
-if (insert_val < min_val || insert_node == -1) {
-insert_val = min_val;
-insert_node = i;
-}
-}
-Node n = _notused[insert_node];
-_notused.erase(_notused.begin()+insert_node);
-return n;
-}
-private:
-const FullGraph &_gr;
-const CostMap &_cost;
-std::vector<Node> &_path;
-std::vector<Node> &_notused;
-};
 // Implementation of the cheapest selection rule
 class CheapestSelection {
 private:
 Cost costDiff(Node u, Node v, Node w) const {
 _cost[_gr.edge(u, v)];
 }
 public:
 CheapestSelection(const FullGraph &gr, const CostMap &cost,
-std::vector<Node> &path, std::vector<Node> &notused)
+std::vector<Node> &tour, std::vector<Node> &notused)
-: _gr(gr), _cost(cost), _path(path), _notused(notused) {}
+: _gr(gr), _cost(cost), _tour(tour), _notused(notused),
+_ins_cost(gr, 0), _ins_pos(gr, -1)
-Cost select() const {
+{
-int insert_notused = -1;
+// Compute insertion cost and position for the unused nodes
-int best_insert_index = -1;
-Cost insert_val = 0;
 for (unsigned int i=0; i<_notused.size(); ++i) {
-int min = i;
+Node u = _notused[i];
-int best_insert_tmp = 0;
+Cost min_cost = costDiff(_tour.back(), _tour.front(), u);
-Cost min_val =
+int min_pos = 0;
-costDiff(_path.front(), _path.back(), _notused[i]);
+for (unsigned int j=1; j<_tour.size(); ++j) {
+Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);
-for (unsigned int j=1; j<_path.size(); ++j) {
+if (curr_cost < min_cost) {
-Cost tmp =
+min_cost = curr_cost;
-costDiff(_path[j-1], _path[j], _notused[i]);
+min_pos = j;
-if (min_val > tmp) {
-min = i;
-min_val = tmp;
-best_insert_tmp = j;
 }
 }
+_ins_cost[u] = min_cost;
-if (insert_val > min_val || insert_notused == -1) {
+_ins_pos[u] = min_pos;
-insert_notused = min;
+}
-insert_val = min_val;
+}
-best_insert_index = best_insert_tmp;
-}
+Cost select() {
-}
+// Select an used node with minimum insertion cost
-_path.insert(_path.begin()+best_insert_index,
+Cost min_cost = 0;
-_notused[insert_notused]);
+int min_node = -1;
-_notused.erase(_notused.begin()+insert_notused);
+for (unsigned int i=0; i<_notused.size(); ++i) {
+Cost curr_cost = _ins_cost[_notused[i]];
-return insert_val;
+if (curr_cost < min_cost || min_node == -1) {
+min_cost = curr_cost;
+min_node = i;
+}
+}
+// Remove the selected node from the unused vector
+Node sn = _notused[min_node];
+_notused[min_node] = _notused.back();
+_notused.pop_back();
+// Insert the selected node into the tour
+const int ipos = _ins_pos[sn];
+_tour.insert(_tour.begin() + ipos, sn);
+// Update the insertion cost and position of the remaining nodes
+for (unsigned int i=0; i<_notused.size(); ++i) {
+Node u = _notused[i];
+Cost curr_cost = _ins_cost[u];
+int curr_pos = _ins_pos[u];
+int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;
+int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;
+Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);
+Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);
+if (nc1 <= curr_cost || nc2 <= curr_cost) {
+// A new position is better than the old one
+if (nc1 <= nc2) {
+curr_cost = nc1;
+curr_pos = ipos;
+} else {
+curr_cost = nc2;
+curr_pos = ipos_next;
+}
+}
+else {
+if (curr_pos == ipos) {
+// The minimum should be found again
+curr_cost = costDiff(_tour.back(), _tour.front(), u);
+curr_pos = 0;
+for (unsigned int j=1; j<_tour.size(); ++j) {
+Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);
+if (tmp_cost < curr_cost) {
+curr_cost = tmp_cost;
+curr_pos = j;
+}
+}
+}
+else if (curr_pos > ipos) {
+++curr_pos;
+}
+}
+_ins_cost[u] = curr_cost;
+_ins_pos[u] = curr_pos;
+}
+return min_cost;
 }
 private:
 const FullGraph &_gr;
 const CostMap &_cost;
-std::vector<Node> &_path;
+std::vector<Node> &_tour;
 std::vector<Node> &_notused;
+FullGraph::NodeMap<Cost> _ins_cost;
+FullGraph::NodeMap<int> _ins_pos;
 };
 // Implementation of the random selection rule
 class RandomSelection {
 public:
 : _notused(notused) {}
 Node select() const {
 const int index = rnd[_notused.size()];
 Node n = _notused[index];
-_notused.erase(_notused.begin()+index);
+_notused[index] = _notused.back();
+_notused.pop_back();
 return n;
 }
 private:
 std::vector<Node> &_notused;
 };
 _cost[_gr.edge(u, v)];
 }
 public:
 DefaultInsertion(const FullGraph &gr, const CostMap &cost,
-std::vector<Node> &path, Cost &total_cost) :
+std::vector<Node> &tour, Cost &total_cost) :
-_gr(gr), _cost(cost), _path(path), _total(total_cost) {}
+_gr(gr), _cost(cost), _tour(tour), _total(total_cost) {}
 void insert(Node n) const {
 int min = 0;
 Cost min_val =
-costDiff(_path.front(), _path.back(), n);
+costDiff(_tour.front(), _tour.back(), n);
-for (unsigned int i=1; i<_path.size(); ++i) {
+for (unsigned int i=1; i<_tour.size(); ++i) {
-Cost tmp = costDiff(_path[i-1], _path[i], n);
+Cost tmp = costDiff(_tour[i-1], _tour[i], n);
 if (tmp < min_val) {
 min = i;
 min_val = tmp;
 }
 }
-_path.insert(_path.begin()+min, n);
+_tour.insert(_tour.begin()+min, n);
 _total += min_val;
 }
 private:
 const FullGraph &_gr;
 const CostMap &_cost;
-std::vector<Node> &_path;
+std::vector<Node> &_tour;
 Cost &_total;
 };
 // Implementation of a special insertion method for the cheapest
 // selection rule

changeset 1036	dff32ce3db71
parent 1034	ef200e268af2
child 1037	d3dcc49e6403