Changeset 1038:a2d142bb5d3c in lemon-main for doc/groups.dox
- Timestamp:
- 03/01/13 17:59:08 (12 years ago)
- Branch:
- default
- Parents:
- 1030:4936be66d2f5 (diff), 1037:d3dcc49e6403 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
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 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 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 /** -
doc/groups.dox
r1036 r1038 407 407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. 408 408 409 In general NetworkSimplex is the most efficient implementation, 410 but in special cases other algorithms could be faster. 409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient 410 implementations. 411 \ref NetworkSimplex is usually the fastest on relatively small graphs (up to 412 several thousands of nodes) and on dense graphs, while \ref CostScaling is 413 typically more efficient on large graphs (e.g. hundreds of thousands of 414 nodes or above), especially if they are sparse. 415 However, other algorithms could be faster in special cases. 411 416 For example, if the total supply and/or capacities are rather small, 412 CapacityScaling is usually the fastest algorithm (without effective scaling). 417 \ref CapacityScaling is usually the fastest algorithm (without effective scaling). 418 419 These classes are intended to be used with integer-valued input data 420 (capacities, supply values, and costs), except for \ref CapacityScaling, 421 which is capable of handling real-valued arc costs (other numerical 422 data are required to be integer). 413 423 */ 414 424 … … 449 459 450 460 This group contains the algorithms for finding minimum mean cycles 451 \ref clrs01algorithms, \ref amo93networkflows.461 \ref amo93networkflows, \ref karp78characterization. 452 462 453 463 The \e minimum \e mean \e cycle \e problem is to find a directed cycle … … 465 475 466 476 LEMON contains three algorithms for solving the minimum mean cycle problem: 467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, 468 \ref dasdan98minmeancycle. 477 - \ref KarpMmc Karp's original algorithm \ref karp78characterization. 469 478 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 470 version of Karp's algorithm \ref dasdan98minmeancycle.479 version of Karp's algorithm \ref hartmann93finding. 471 480 - \ref HowardMmc Howard's policy iteration algorithm 472 \ref dasdan98minmeancycle .473 474 In practice, the \ref HowardMmc "Howard" algorithm provedto be by far the481 \ref dasdan98minmeancycle, \ref dasdan04experimental. 482 483 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the 475 484 most efficient one, though the best known theoretical bound on its running 476 485 time is exponential. … … 540 549 541 550 /** 542 @defgroup planar Planar ityEmbedding and Drawing551 @defgroup planar Planar Embedding and Drawing 543 552 @ingroup algs 544 553 \brief Algorithms for planarity checking, embedding and drawing
Note: See TracChangeset
for help on using the changeset viewer.