TravelingSalesman

Declared in astar/TravelingSalesman.h; the same class on the site of Doxygen.

class TravelingSalesman

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 \)).

Public Types

using state_type = std::uint64_t: a packed state

using cost_type = double: the cost type

using matrix_type = std::vector<std::vector<double>>: the distances

Public Functions

inline explicit TravelingSalesman(matrix_type dist): constructor, taking the \( n \times n \) distances, \( 2 \leq n \leq 32 \)

inline std::uint64_t initial_state(void) const noexcept

inline bool is_goal(std::uint64_t s) const noexcept

inline std::uint64_t hash(std::uint64_t s) const noexcept

inline double heuristic(std::uint64_t s) const: the cost of a minimum spanning tree of the cities still to be touched

template<class F> inline 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

inline std::size_t num_features(void) const noexcept: the number of features: the visited cities, the current one, the end

template<class F> inline 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

inline std::uint64_t perfect_hash(std::uint64_t s) const noexcept: the perfect hash: the packed state

inline double held_karp(void) const

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:

procedure HELDKARP(d, n)
   C({0}, 0) ← 0;  C(S, j) ← ∞ for each other pair
   for each set S ∋ 0, by increasing value of its bits, do
      for each j ∈ S with C(S, j) < ∞ do
         for each k ∉ S do
            C(S ∪ {k}, k) ← min(C(S ∪ {k}, k), C(S, j) + d(j, k))
   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).

inline int size(void) const noexcept: the number of cities

Public Static Functions

static inline matrix_type random_cities(int n, std::uint64_t seed): the Euclidean distances of n random points of the unit square, drawn from the seed

static inline int city(std::uint64_t s) noexcept: the current city of the state s