doc/groups.dox
changeset 1202 ef200e268af2
parent 1200 62ba43576f85
child 1204 dff32ce3db71
equal deleted inserted replaced
61:8a9f6f26797d 62:ad286ff90710
   559 \e traveling \e salesman \e problem (TSP).
   559 \e traveling \e salesman \e problem (TSP).
   560 Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
   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
   561 the problem is to find a shortest possible tour that visits each node exactly
   562 once (i.e. the minimum cost Hamiltonian cycle).
   562 once (i.e. the minimum cost Hamiltonian cycle).
   563 
   563 
   564 These TSP algorithms should be used with a
   564 These TSP algorithms are intended to be used with a \e metric \e cost
   565 metric cost function. Otherwise, they could yield worse results.
   565 \e function, i.e. the edge costs should satisfy the triangle inequality.
       
   566 Otherwise the algorithms could yield worse results.
   566 
   567 
   567 LEMON provides five well-known heuristics for solving symmetric TSP:
   568 LEMON provides five well-known heuristics for solving symmetric TSP:
   568  - \ref NearestNeighborTsp Neareast neighbor algorithm
   569  - \ref NearestNeighborTsp Neareast neighbor algorithm
   569  - \ref GreedyTsp Greedy algorithm
   570  - \ref GreedyTsp Greedy algorithm
   570  - \ref InsertionTsp Insertion heuristic (with four selection methods)
   571  - \ref InsertionTsp Insertion heuristic (with four selection methods)