doc/groups.dox
 changeset 1200 62ba43576f85 parent 999 c279b19abc62 child 1202 ef200e268af2
     1.1 --- a/doc/groups.dox	Sat Jan 08 21:59:56 2011 +0100
1.2 +++ b/doc/groups.dox	Sat Jan 08 22:49:09 2011 +0100
1.3 @@ -549,6 +549,31 @@
1.4  \image html planar.png
1.5  \image latex planar.eps "Plane graph" width=\textwidth
1.6  */
1.7 +
1.8 +/**
1.9 +@defgroup tsp Traveling Salesman Problem
1.10 +@ingroup algs
1.11 +\brief Algorithms for the symmetric traveling salesman problem
1.12 +
1.13 +This group contains basic heuristic algorithms for the the symmetric
1.14 +\e traveling \e salesman \e problem (TSP).
1.15 +Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
1.16 +the problem is to find a shortest possible tour that visits each node exactly
1.17 +once (i.e. the minimum cost Hamiltonian cycle).
1.18 +
1.19 +These TSP algorithms should be used with a
1.20 +metric cost function. Otherwise, they could yield worse results.
1.21 +
1.22 +LEMON provides five well-known heuristics for solving symmetric TSP:
1.23 + - \ref NearestNeighborTsp Neareast neighbor algorithm
1.24 + - \ref GreedyTsp Greedy algorithm
1.25 + - \ref InsertionTsp Insertion heuristic (with four selection methods)
1.26 + - \ref ChristofidesTsp Christofides algorithm
1.27 + - \ref Opt2Tsp 2-opt algorithm
1.28 +
1.29 +\image html tsp.png
1.30 +\image latex tsp.eps "Traveling salesman problem" width=\textwidth
1.31 +*/
1.32
1.33  /**
1.34  @defgroup approx_algs Approximation Algorithms