|
| Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
#include <hamiltonian_path.h>
Public Types | |
| typedef uint32 | NodeSet |
| HamiltonianPathSolver computes a minimum Hamiltonian path over a graph defined by a cost matrix. | |
Public Member Functions | |
| HamiltonianPathSolver (const std::vector< std::vector< T > > &cost) | |
| ~HamiltonianPathSolver () | |
| void | ChangeCostMatrix (const std::vector< std::vector< T > > &cost) |
| Replaces the cost matrix while avoiding re-allocating memory. | |
| T | HamiltonianCost () |
| Returns the Hamiltonian path cost. | |
| void | HamiltonianPath (std::vector< PathNodeIndex > *path) |
| Returns the Hamiltonian path in the vector pointed to by the argument. | |
| T | TravelingSalesmanCost () |
| Returns the cost of the TSP tour. | |
| void | TravelingSalesmanPath (std::vector< PathNodeIndex > *path) |
| Returns the TSP tour in the vector pointed to by the argument. | |
| bool | IsRobust () |
| Returns true if there won't be precision issues. | |
| bool | VerifiesTriangleInequality () |
| Returns true if the cost matrix verifies the triangle inequality. | |
Definition at line 93 of file hamiltonian_path.h.
| typedef uint32 operations_research::HamiltonianPathSolver< T >::NodeSet |
HamiltonianPathSolver computes a minimum Hamiltonian path over a graph defined by a cost matrix.
The cost matrix need not be symmetric. The Hamiltonian path can be closed, in this case it's a Hamiltonian cycle, i.e. the algorithm solves the Travelling Salesman Problem. Example: std::vector<std::vector<int> > cost_mat; ... fill in cost matrix HamiltonianPathSolver<int> mhp(cost_mat); ///< no computation done printf("%d\n", mhp.TravelingSalesmanCost()); ///< computation done and stored Currently in 2010, 26 is the maximum you can solve with 24 Gigs of RAM, and it takes several minutes. Considering the complexity of the algorithm (n*2^n), and that there are very good ways to solve TSP with more than 32 cities, we limit ourselves to 32 cites. This is why we define the type NodeSet to be 32-bit wide.
Definition at line 112 of file hamiltonian_path.h.
| operations_research::HamiltonianPathSolver< T >::HamiltonianPathSolver | ( | const std::vector< std::vector< T > > & | cost | ) | [inline, explicit] |
Definition at line 179 of file hamiltonian_path.h.
| operations_research::HamiltonianPathSolver< T >::~HamiltonianPathSolver | ( | ) | [inline] |
Definition at line 192 of file hamiltonian_path.h.
| void operations_research::HamiltonianPathSolver< T >::ChangeCostMatrix | ( | const std::vector< std::vector< T > > & | cost | ) | [inline] |
Replaces the cost matrix while avoiding re-allocating memory.
Definition at line 211 of file hamiltonian_path.h.
| T operations_research::HamiltonianPathSolver< T >::HamiltonianCost | ( | ) | [inline] |
| void operations_research::HamiltonianPathSolver< T >::HamiltonianPath | ( | std::vector< PathNodeIndex > * | path | ) | [inline] |
Returns the Hamiltonian path in the vector pointed to by the argument.
Definition at line 373 of file hamiltonian_path.h.
| T operations_research::HamiltonianPathSolver< T >::TravelingSalesmanCost | ( | ) | [inline] |
| void operations_research::HamiltonianPathSolver< T >::TravelingSalesmanPath | ( | std::vector< PathNodeIndex > * | path | ) | [inline] |
Returns the TSP tour in the vector pointed to by the argument.
Definition at line 455 of file hamiltonian_path.h.
| bool operations_research::HamiltonianPathSolver< T >::IsRobust | ( | ) | [inline] |
Returns true if there won't be precision issues.
This is always true for integers, but not for floating-point types.
Definition at line 234 of file hamiltonian_path.h.
| bool operations_research::HamiltonianPathSolver< T >::VerifiesTriangleInequality | ( | ) | [inline] |
Returns true if the cost matrix verifies the triangle inequality.
Definition at line 242 of file hamiltonian_path.h.