COIN-OR::LEMON - Graph Library

Changes in / [1030:4936be66d2f5:1038:a2d142bb5d3c] in lemon-main


Ignore:
Files:
7 added
3 edited

Legend:

Unmodified
Added
Removed
  • doc/CMakeLists.txt

    r983 r1038  
    4747    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    4848    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     49    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
    4950    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    5051    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
  • doc/groups.dox

    r1003 r1038  
    559559\image latex planar.eps "Plane graph" width=\textwidth
    560560*/
     561 
     562/**
     563@defgroup tsp Traveling Salesman Problem
     564@ingroup algs
     565\brief Algorithms for the symmetric traveling salesman problem
     566
     567This group contains basic heuristic algorithms for the the symmetric
     568\e traveling \e salesman \e problem (TSP).
     569Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
     570the problem is to find a shortest possible tour that visits each node exactly
     571once (i.e. the minimum cost Hamiltonian cycle).
     572
     573These TSP algorithms are intended to be used with a \e metric \e cost
     574\e function, i.e. the edge costs should satisfy the triangle inequality.
     575Otherwise the algorithms could yield worse results.
     576
     577LEMON provides five well-known heuristics for solving symmetric TSP:
     578 - \ref NearestNeighborTsp Neareast neighbor algorithm
     579 - \ref GreedyTsp Greedy algorithm
     580 - \ref InsertionTsp Insertion heuristic (with four selection methods)
     581 - \ref ChristofidesTsp Christofides algorithm
     582 - \ref Opt2Tsp 2-opt algorithm
     583
     584\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
     585solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     586
     587\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
     588approximation factor: 3/2.
     589
     590\ref Opt2Tsp usually provides the best results in practice, but
     591it is the slowest method. It can also be used to improve given tours,
     592for example, the results of other algorithms.
     593
     594\image html tsp.png
     595\image latex tsp.eps "Traveling salesman problem" width=\textwidth
     596*/
    561597
    562598/**
  • test/CMakeLists.txt

    r1030 r1038  
    5353  suurballe_test
    5454  time_measure_test
     55  tsp_test
    5556  unionfind_test
    5657)
Note: See TracChangeset for help on using the changeset viewer.