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."],[[["\u003cp\u003eThe \u003ccode\u003eChristofidesPathSolver\u003c/code\u003e class provides an approximate solution to the Traveling Salesman Problem (TSP) using the Christofides algorithm.\u003c/p\u003e\n"],["\u003cp\u003eIt allows selecting between two matching algorithms: \u003ccode\u003eMINIMUM_WEIGHT_MATCHING\u003c/code\u003e (guarantees a 3/2 approximation bound) and \u003ccode\u003eMINIMAL_WEIGHT_MATCHING\u003c/code\u003e (faster but without bound guarantees).\u003c/p\u003e\n"],["\u003cp\u003eThe \u003ccode\u003eSolve()\u003c/code\u003e method executes the algorithm and returns \u003ccode\u003etrue\u003c/code\u003e if a solution is found.\u003c/p\u003e\n"],["\u003cp\u003eUsers can retrieve the cost and path of the approximate TSP tour using \u003ccode\u003eTravelingSalesmanCost()\u003c/code\u003e and \u003ccode\u003eTravelingSalesmanPath()\u003c/code\u003e, respectively.\u003c/p\u003e\n"]]],["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"],null,["# ChristofidesPathSolver\n\nC++ Reference: class ChristofidesPathSolver\n===========================================\n\n\nNote: This documentation is automatically generated.\n\n| Method ||\n|-----------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`ChristofidesPathSolver`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/christofides.h#L61) | \u003cbr /\u003e Arguments: `NodeIndex num_nodes, CostFunction costs` \u003cbr /\u003e |\n| [`SetMatchingAlgorithm`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/christofides.h#L71) | 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. |\n| [`Solve`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/christofides.h#L83) | Return type: `bool ` Runs the Christofides algorithm. Returns true if a solution was found, false otherwise. |\n| [`TravelingSalesmanCost`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/christofides.h#L76) | Return type: `CostType ` Returns the cost of the approximate TSP tour. |\n| [`TravelingSalesmanPath`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/christofides.h#L79) | Return type: `std::vector\u003cNodeIndex\u003e ` Returns the approximate TSP tour. |"]]
