547 embedding and drawing. |
547 embedding and drawing. |
548 |
548 |
549 \image html planar.png |
549 \image html planar.png |
550 \image latex planar.eps "Plane graph" width=\textwidth |
550 \image latex planar.eps "Plane graph" width=\textwidth |
551 */ |
551 */ |
|
552 |
|
553 /** |
|
554 @defgroup tsp Traveling Salesman Problem |
|
555 @ingroup algs |
|
556 \brief Algorithms for the symmetric traveling salesman problem |
|
557 |
|
558 This group contains basic heuristic algorithms for the the symmetric |
|
559 \e traveling \e salesman \e problem (TSP). |
|
560 Given an \ref FullGraph "undirected full graph" with a cost map on its edges, |
|
561 the problem is to find a shortest possible tour that visits each node exactly |
|
562 once (i.e. the minimum cost Hamiltonian cycle). |
|
563 |
|
564 These TSP algorithms should be used with a |
|
565 metric cost function. Otherwise, they could yield worse results. |
|
566 |
|
567 LEMON provides five well-known heuristics for solving symmetric TSP: |
|
568 - \ref NearestNeighborTsp Neareast neighbor algorithm |
|
569 - \ref GreedyTsp Greedy algorithm |
|
570 - \ref InsertionTsp Insertion heuristic (with four selection methods) |
|
571 - \ref ChristofidesTsp Christofides algorithm |
|
572 - \ref Opt2Tsp 2-opt algorithm |
|
573 |
|
574 \image html tsp.png |
|
575 \image latex tsp.eps "Traveling salesman problem" width=\textwidth |
|
576 */ |
552 |
577 |
553 /** |
578 /** |
554 @defgroup approx_algs Approximation Algorithms |
579 @defgroup approx_algs Approximation Algorithms |
555 @ingroup algs |
580 @ingroup algs |
556 \brief Approximation algorithms. |
581 \brief Approximation algorithms. |