Changes in / [1030:4936be66d2f5:1038:a2d142bb5d3c] in lemonmain
 Files:

 7 added
 3 edited
Legend:
 Unmodified
 Added
 Removed

doc/CMakeLists.txt
r983 r1038 47 47 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} r18 sOutputFile=genimages/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps 48 48 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} r18 sOutputFile=genimages/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps 49 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} r18 sOutputFile=genimages/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps 49 50 COMMAND ${CMAKE_COMMAND} E remove_directory html 50 51 COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox 
doc/groups.dox
r1003 r1038 559 559 \image latex planar.eps "Plane graph" width=\textwidth 560 560 */ 561 562 /** 563 @defgroup tsp Traveling Salesman Problem 564 @ingroup algs 565 \brief Algorithms for the symmetric traveling salesman problem 566 567 This group contains basic heuristic algorithms for the the symmetric 568 \e traveling \e salesman \e problem (TSP). 569 Given an \ref FullGraph "undirected full graph" with a cost map on its edges, 570 the problem is to find a shortest possible tour that visits each node exactly 571 once (i.e. the minimum cost Hamiltonian cycle). 572 573 These 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. 575 Otherwise the algorithms could yield worse results. 576 577 LEMON provides five wellknown 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 2opt algorithm 583 584 \ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest 585 solution methods. Furthermore, \ref InsertionTsp is usually quite effective. 586 587 \ref ChristofidesTsp is somewhat slower, but it has the best guaranteed 588 approximation factor: 3/2. 589 590 \ref Opt2Tsp usually provides the best results in practice, but 591 it is the slowest method. It can also be used to improve given tours, 592 for example, the results of other algorithms. 593 594 \image html tsp.png 595 \image latex tsp.eps "Traveling salesman problem" width=\textwidth 596 */ 561 597 562 598 /** 
test/CMakeLists.txt
r1030 r1038 53 53 suurballe_test 54 54 time_measure_test 55 tsp_test 55 56 unionfind_test 56 57 )
Note: See TracChangeset
for help on using the changeset viewer.