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.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["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. |"]]
