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

Detailed Description

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

Definition at line 882 of file hamiltonian_path.h.

#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.

Member Typedef Documentation

Integer

template<typename CostType, typename CostFunction>

typedef 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 898 of file hamiltonian_path.h.

NodeSet

template<typename CostType, typename CostFunction>

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

Definition at line 899 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 937 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 942 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 1011 of file hamiltonian_path.h.

---

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

• ortools/graph/hamiltonian_path.h