# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1294531012 -3600
# Node ID ef200e268af2e361f17337a8535e52dc90a035fe
# Parent 9a51db0382284a09f447b6d148d29e681cb23e98
Unifications and improvements in TSP algorithms (#386)
diff -r 9a51db038228 -r ef200e268af2 doc/groups.dox
--- a/doc/groups.dox Sat Jan 08 22:51:16 2011 +0100
+++ b/doc/groups.dox Sun Jan 09 00:56:52 2011 +0100
@@ -561,8 +561,9 @@
the problem is to find a shortest possible tour that visits each node exactly
once (i.e. the minimum cost Hamiltonian cycle).
-These TSP algorithms should be used with a
-metric cost function. Otherwise, they could yield worse results.
+These TSP algorithms are intended to be used with a \e metric \e cost
+\e function, i.e. the edge costs should satisfy the triangle inequality.
+Otherwise the algorithms could yield worse results.
LEMON provides five well-known heuristics for solving symmetric TSP:
- \ref NearestNeighborTsp Neareast neighbor algorithm
diff -r 9a51db038228 -r ef200e268af2 lemon/christofides_tsp.h
--- a/lemon/christofides_tsp.h Sat Jan 08 22:51:16 2011 +0100
+++ b/lemon/christofides_tsp.h Sun Jan 09 00:56:52 2011 +0100
@@ -31,13 +31,15 @@
namespace lemon {
+ /// \ingroup tsp
+ ///
/// \brief Christofides algorithm for symmetric TSP.
///
/// ChristofidesTsp implements Christofides' heuristic for solving
/// symmetric \ref tsp "TSP".
///
/// This a well-known approximation method for the TSP problem with
- /// \ref checkMetricCost() "metric cost function".
+ /// metric cost function.
/// It yields a tour whose total cost is at most 3/2 of the optimum,
/// but it is usually much better.
/// This implementation runs in O(n<sup>3</sup>log(n)) time.
@@ -54,7 +56,7 @@
///
/// \tparam CM Type of the cost map.
///
- /// \warning \& CM::Value must be signed type.
+ /// \warning CM::Value must be a signed number type.
template <typename CM>
class ChristofidesTsp
{
@@ -195,7 +197,7 @@
/// \brief Returns a const reference to the node sequence of the
/// found tour.
///
- /// This function returns a const reference to the internal structure
+ /// 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.
diff -r 9a51db038228 -r ef200e268af2 lemon/greedy_tsp.h
--- a/lemon/greedy_tsp.h Sat Jan 08 22:51:16 2011 +0100
+++ b/lemon/greedy_tsp.h Sun Jan 09 00:56:52 2011 +0100
@@ -30,6 +30,8 @@
namespace lemon {
+ /// \ingroup tsp
+ ///
/// \brief Greedy algorithm for symmetric TSP.
///
/// GreedyTsp implements the greedy heuristic for solving
@@ -42,9 +44,8 @@
/// not increase the degree of any node above two.
///
/// This method runs in O(n<sup>2</sup>log(n)) time.
- /// It quickly finds an effectively short tour for most TSP
- /// instances, but in special cases, it could yield a really bad
- /// (or even the worst) solution.
+ /// It quickly finds a short tour for most TSP instances, but in special
+ /// cases, it could yield a really bad (or even the worst) solution.
///
/// \tparam CM Type of the cost map.
template <typename CM>
@@ -193,7 +194,7 @@
/// \brief Returns a const reference to the node sequence of the
/// found tour.
///
- /// This function returns a const reference to the internal structure
+ /// 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.
diff -r 9a51db038228 -r ef200e268af2 lemon/insertion_tsp.h
--- a/lemon/insertion_tsp.h Sat Jan 08 22:51:16 2011 +0100
+++ b/lemon/insertion_tsp.h Sun Jan 09 00:56:52 2011 +0100
@@ -30,6 +30,8 @@
namespace lemon {
+ /// \ingroup tsp
+ ///
/// \brief Insertion algorithm for symmetric TSP.
///
/// InsertionTsp implements the insertion heuristic for solving
@@ -74,9 +76,9 @@
///
/// During the algorithm, nodes are selected for addition to the current
/// subtour according to the applied rule.
- /// In general, the FARTHEST yields the best tours, thus it is the
- /// default option. RANDOM usually gives somewhat worse results, but
- /// it is much faster than the others and it is the most robust.
+ /// In general, the FARTHEST method yields the best tours, thus it is the
+ /// default option. The RANDOM rule usually gives somewhat worse results,
+ /// but it is much faster than the others and it is the most robust.
///
/// The desired selection rule can be specified as a parameter of the
/// \ref run() function.
@@ -178,7 +180,7 @@
/// \brief Returns a const reference to the node sequence of the
/// found tour.
///
- /// This function returns a const reference to the internal structure
+ /// 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.
diff -r 9a51db038228 -r ef200e268af2 lemon/nearest_neighbor_tsp.h
--- a/lemon/nearest_neighbor_tsp.h Sat Jan 08 22:51:16 2011 +0100
+++ b/lemon/nearest_neighbor_tsp.h Sun Jan 09 00:56:52 2011 +0100
@@ -24,12 +24,15 @@
/// \brief Nearest neighbor algorithm for symmetric TSP
#include <deque>
+#include <vector>
#include <limits>
#include <lemon/full_graph.h>
#include <lemon/maps.h>
namespace lemon {
+ /// \ingroup tsp
+ ///
/// \brief Nearest neighbor algorithm for symmetric TSP.
///
/// NearestNeighborTsp implements the nearest neighbor heuristic for solving
@@ -41,9 +44,8 @@
/// Finally, it connects the two end points of the path to form a tour.
///
/// This method runs in O(n<sup>2</sup>) time.
- /// It quickly finds an effectively short tour for most TSP
- /// instances, but in special cases, it could yield a really bad
- /// (or even the worst) solution.
+ /// It quickly finds a short tour for most TSP instances, but in special
+ /// cases, it could yield a really bad (or even the worst) solution.
///
/// \tparam CM Type of the cost map.
template <typename CM>
@@ -63,7 +65,7 @@
const FullGraph &_gr;
const CostMap &_cost;
Cost _sum;
- std::deque<Node> _path;
+ std::vector<Node> _path;
public:
@@ -85,28 +87,30 @@
/// \return The total cost of the found tour.
Cost run() {
_path.clear();
-
- if (_gr.nodeNum() == 0) return _sum = 0;
+ if (_gr.nodeNum() == 0) {
+ return _sum = 0;
+ }
else if (_gr.nodeNum() == 1) {
_path.push_back(_gr(0));
return _sum = 0;
}
+ std::deque<Node> path_dq;
Edge min_edge1 = INVALID,
min_edge2 = INVALID;
min_edge1 = mapMin(_gr, _cost);
Node n1 = _gr.u(min_edge1),
n2 = _gr.v(min_edge1);
- _path.push_back(n1);
- _path.push_back(n2);
+ path_dq.push_back(n1);
+ path_dq.push_back(n2);
FullGraph::NodeMap<bool> used(_gr, false);
used[n1] = true;
used[n2] = true;
min_edge1 = INVALID;
- while (int(_path.size()) != _gr.nodeNum()) {
+ while (int(path_dq.size()) != _gr.nodeNum()) {
if (min_edge1 == INVALID) {
for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
if (!used[_gr.runningNode(e)] &&
@@ -127,7 +131,7 @@
if (_cost[min_edge1] < _cost[min_edge2]) {
n1 = _gr.oppositeNode(n1, min_edge1);
- _path.push_front(n1);
+ path_dq.push_front(n1);
used[n1] = true;
min_edge1 = INVALID;
@@ -136,7 +140,7 @@
min_edge2 = INVALID;
} else {
n2 = _gr.oppositeNode(n2, min_edge2);
- _path.push_back(n2);
+ path_dq.push_back(n2);
used[n2] = true;
min_edge2 = INVALID;
@@ -146,9 +150,15 @@
}
}
- _sum = _cost[_gr.edge(_path.back(), _path.front())];
- for (int i = 0; i < int(_path.size())-1; ++i) {
- _sum += _cost[_gr.edge(_path[i], _path[i+1])];
+ n1 = path_dq.back();
+ n2 = path_dq.front();
+ _path.push_back(n2);
+ _sum = _cost[_gr.edge(n1, n2)];
+ for (int i = 1; i < int(path_dq.size()); ++i) {
+ n1 = n2;
+ n2 = path_dq[i];
+ _path.push_back(n2);
+ _sum += _cost[_gr.edge(n1, n2)];
}
return _sum;
@@ -171,11 +181,11 @@
/// \brief Returns a const reference to the node sequence of the
/// found tour.
///
- /// This function returns a const reference to the internal structure
+ /// 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::deque<Node>& tourNodes() const {
+ const std::vector<Node>& tourNodes() const {
return _path;
}
diff -r 9a51db038228 -r ef200e268af2 lemon/opt2_tsp.h
--- a/lemon/opt2_tsp.h Sat Jan 08 22:51:16 2011 +0100
+++ b/lemon/opt2_tsp.h Sun Jan 09 00:56:52 2011 +0100
@@ -21,13 +21,15 @@
/// \ingroup tsp
/// \file
-/// \brief 2-opt algorithm for symmetric TSP
+/// \brief 2-opt algorithm for symmetric TSP.
#include <vector>
#include <lemon/full_graph.h>
namespace lemon {
+ /// \ingroup tsp
+ ///
/// \brief 2-opt algorithm for symmetric TSP.
///
/// Opt2Tsp implements the 2-opt heuristic for solving
@@ -114,7 +116,7 @@
return start();
}
- /// \brief Runs the algorithm from the given tour.
+ /// \brief Runs the algorithm starting from the given tour.
///
/// This function runs the algorithm starting from the given tour.
///
@@ -156,16 +158,16 @@
return start();
}
- /// \brief Runs the algorithm from the given tour.
+ /// \brief Runs the algorithm starting from the given tour.
///
- /// This function runs the algorithm starting from the given tour.
+ /// This function runs the algorithm starting from the given tour
+ /// (node sequence).
///
- /// \param tour The tour as a node sequence. It must be a standard
- /// sequence container storing all <tt>Node</tt>s in the desired order.
+ /// \param tour A vector that stores all <tt>Node</tt>s of the graph
+ /// in the desired order.
///
/// \return The total cost of the found tour.
- template <template <typename> class Container>
- Cost run(const Container<Node>& tour) {
+ Cost run(const std::vector<Node>& tour) {
_path.clear();
if (_gr.nodeNum() == 0) return _sum = 0;
@@ -180,7 +182,7 @@
}
_plist.resize(2*_gr.nodeNum());
- typename Container<Node>::const_iterator it = tour.begin();
+ typename std::vector<Node>::const_iterator it = tour.begin();
int first = _gr.id(*it),
prev = first,
curr = _gr.id(*(++it)),
@@ -217,7 +219,7 @@
/// \brief Returns a const reference to the node sequence of the
/// found tour.
///
- /// This function returns a const reference to the internal structure
+ /// 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.