operations_research::PruningHamiltonianSolver< CostType, CostFunction > Class Template Reference

#include <hamiltonian_path.h>

Public Types
typedef uint32_t	Integer
typedef Set< Integer >	NodeSet

Public Member Functions
	PruningHamiltonianSolver (CostFunction cost)
	PruningHamiltonianSolver (int num_nodes, CostFunction cost)
CostType	HamiltonianCost (int end_node)
	Returns the cost of the Hamiltonian path from 0 to end_node.

Detailed Description

template<typename CostType, typename CostFunction>
class operations_research::PruningHamiltonianSolver< CostType, CostFunction >

Definition at line 876 of file hamiltonian_path.h.

Member Typedef Documentation

Integer

template<typename CostType , typename CostFunction >

uint32_t operations_research::PruningHamiltonianSolver< CostType, CostFunction >::Integer

PruningHamiltonianSolver computes a minimum Hamiltonian path from node 0 over a graph defined by a cost matrix, with pruning. For each search state, PruningHamiltonianSolver computes the lower bound for the future overall TSP cost, and stops further search if it exceeds the current best solution. For the heuristics to determine future lower bound over visited nodeset S and last visited node k, the cost of minimum spanning tree of (V \ S) ∪ {k} is calculated and added to the current cost(S). The cost of MST is guaranteed to be smaller than or equal to the cost of Hamiltonian path, because Hamiltonian path is a spanning tree itself.

Todo

(user): Use generic map-based cache instead of lattice-based one.

(user): Use SaturatedArithmetic for better precision.

Definition at line 892 of file hamiltonian_path.h.

NodeSet

template<typename CostType , typename CostFunction >

Set<Integer> operations_research::PruningHamiltonianSolver< CostType, CostFunction >::NodeSet

Definition at line 893 of file hamiltonian_path.h.

Constructor & Destructor Documentation

PruningHamiltonianSolver() [1/2]

template<typename CostType , typename CostFunction >

operations_research::PruningHamiltonianSolver< CostType, CostFunction >::PruningHamiltonianSolver ( CostFunction cost )

explicit

Definition at line 931 of file hamiltonian_path.h.

PruningHamiltonianSolver() [2/2]

template<typename CostType , typename CostFunction >

operations_research::PruningHamiltonianSolver< CostType, CostFunction >::PruningHamiltonianSolver	(	int	num_nodes,
		CostFunction	cost )

Definition at line 936 of file hamiltonian_path.h.

Member Function Documentation

HamiltonianCost()

template<typename CostType , typename CostFunction >

CostType operations_research::PruningHamiltonianSolver< CostType, CostFunction >::HamiltonianCost

(

int

end_node

)

Returns the cost of the Hamiltonian path from 0 to end_node.

Definition at line 1005 of file hamiltonian_path.h.

---

The documentation for this class was generated from the following file:

• ortools/graph/hamiltonian_path.h