|
| | TravelingSalesman (matrix_type dist) |
| | constructor, taking the \( n \times n \) distances, \( 2 \leq n \leq 32 \)
|
| std::uint64_t | initial_state (void) const noexcept |
| bool | is_goal (std::uint64_t s) const noexcept |
| std::uint64_t | hash (std::uint64_t s) const noexcept |
| double | heuristic (std::uint64_t s) const |
| | the cost of a minimum spanning tree of the cities still to be touched
|
| template<class F> |
| void | for_each_successor (std::uint64_t s, double, F &&f) const |
| | calls f( t , c , h( t ) ) for each unvisited city, or for the way back to the city 0 once all are visited
|
| std::size_t | num_features (void) const noexcept |
| | the number of features: the visited cities, the current one, the end
|
| template<class F> |
| void | for_each_feature (std::uint64_t s, F &&f) const |
| | calls f( k ) for each visited city \( k \), f( n + c ) for the current city \( c \) and f( 2 n ) if the tour is closed
|
| std::uint64_t | perfect_hash (std::uint64_t s) const noexcept |
| | the perfect hash: the packed state
|
| double | held_karp (void) const |
| | the cost of an optimal tour by the dynamic program of Held and Karp
|
| int | size (void) const noexcept |
| | the number of cities
|
the traveling salesperson problem on at most 32 cities
The tour starts and ends at the city 0. A state is the current city and the set of the visited ones, packed as the visited cities in the bits \( 0 , \ldots , 31 \), the current city in the bits \( 32 , \ldots , 36 \) and, in the bit 37, whether the tour has gone back to the city 0; the word is also its perfect hash. The heuristic is the cost of a minimum spanning tree (by the algorithm of Prim) of the unvisited cities together with the current and the first one, which is admissible because the rest of the tour is a path through all of them.
The features of Zobrist hashing are the visit of the city \( k \) (numbered \( k < n \)), the current city \( c \) (numbered \( n + c \)) and the closing of the tour (numbered \( 2 n \)).
| double held_karp |
( |
void | | ) |
const |
|
inlinenodiscard |
the cost of an optimal tour by the dynamic program of Held and Karp
With \( d_{jk} \) the distance from the city \( j \) to the city \( k \) and \( C( S , j ) \) the least cost of a path that starts at the city 0, visits exactly the cities of the set \( S \ni 0 \) and ends at \( j \in S \), the dynamic program of Held and Karp (Journal of the Society for Industrial and Applied Mathematics, 1962) rests on the recurrence
\[ C( S \cup \{ k \} , k ) = \min_{j \in S} \{ C( S , j ) + d_{jk} \} ,
\qquad k \notin S ,
\]
and the cost of an optimal tour is \( \min_{j \neq 0} \{ C( V , j ) + d_{j0} \} \), \( V \) being the set of all the cities:
1 procedure HELDKARP(d, n)
2 C({0}, 0) ← 0; C(S, j) ← ∞ for each other pair
3 for each set S ∋ 0, by increasing value of its bits, do
4 for each j ∈ S with C(S, j) < ∞ do
5 for each k ∉ S do
6 C(S ∪ {k}, k) ← min(C(S ∪ {k}, k), C(S, j) + d(j, k))
7 return min over j ≠ 0 of C(V, j) + d(j, 0)
Line 3 visits each set after all its subsets, since adding a city raises the value of the bits; the table has \( 2^n n \) entries and lines 3 to 6 take \( O( 2^n n^2 ) \) time, and therefore the method is meant for checking the searches on small instances (the example TravelingSalesman uses it up to 20 cities).
1.15.0