equal
deleted
inserted
replaced
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) |