COIN-OR::LEMON - Graph Library

Changeset 1032:62ba43576f85 in lemon-main


Ignore:
Timestamp:
01/08/11 22:49:09 (14 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Doc group for TSP algorithms (#386)

Location:
doc
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • doc/CMakeLists.txt

    r912 r1032  
    3232    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    3333    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     34    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
    3435    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    3536    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
  • doc/Makefile.am

    r865 r1032  
    3131        node_biconnected_components.eps \
    3232        planar.eps \
    33         strongly_connected_components.eps
     33        strongly_connected_components.eps \
     34        tsp.eps
    3435
    3536DOC_EPS_IMAGES = \
  • doc/groups.dox

    r904 r1032  
    550550\image latex planar.eps "Plane graph" width=\textwidth
    551551*/
     552 
     553/**
     554@defgroup tsp Traveling Salesman Problem
     555@ingroup algs
     556\brief Algorithms for the symmetric traveling salesman problem
     557
     558This group contains basic heuristic algorithms for the the symmetric
     559\e traveling \e salesman \e problem (TSP).
     560Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
     561the problem is to find a shortest possible tour that visits each node exactly
     562once (i.e. the minimum cost Hamiltonian cycle).
     563
     564These TSP algorithms should be used with a
     565metric cost function. Otherwise, they could yield worse results.
     566
     567LEMON 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*/
    552577
    553578/**
Note: See TracChangeset for help on using the changeset viewer.