Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
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< IntegerNodeSet

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: