Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class ChristofidesPathSolver
Note: This documentation is automatically generated.
| Method |
ChristofidesPathSolver | Arguments: NodeIndex num_nodes, CostFunction costs |
SetMatchingAlgorithm | Return type: void Arguments: MatchingAlgorithm matching Sets the matching algorithm to use. A minimum weight perfect matching
(MINIMUM_WEIGHT_MATCHING) guarantees the 3/2 upper bound to the optimal
solution. A minimal weight perfect matching (MINIMAL_WEIGHT_MATCHING)
finds a locally minimal weight matching which does not offer any bound
guarantee but, as of 1/2017, is orders of magnitude faster than the
minimum matching.
By default, MINIMAL_WEIGHT_MATCHING is selected.
TODO(user): Change the default when minimum matching gets faster.
|
Solve | Return type: bool Runs the Christofides algorithm. Returns true if a solution was found,
false otherwise.
|
TravelingSalesmanCost | Return type: CostType Returns the cost of the approximate TSP tour.
|
TravelingSalesmanPath | Return type: std::vector<NodeIndex> Returns the approximate TSP tour.
|
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["Last updated 2024-08-06 UTC."],[],["The `ChristofidesPathSolver` class provides methods for approximating solutions to the Traveling Salesman Problem (TSP). Key actions include: constructing the solver with `num_nodes` and `costs`; setting the matching algorithm via `SetMatchingAlgorithm` (options: `MINIMUM_WEIGHT_MATCHING` or `MINIMAL_WEIGHT_MATCHING`); running the algorithm with `Solve` and checking its boolean result; retrieving the approximate TSP tour cost using `TravelingSalesmanCost`; and obtaining the approximate TSP tour path via `TravelingSalesmanPath`.\n"]]
