gor (version 2.0)

gauge_tour: Gauging a tour

Description

Gauging a tour for easy comparison.

Usage

gauge_tour(To, n)

Value

The gauged tour.

Arguments

To

The tour to be gauged, a vector containing a permutation of the 1:n sequence

n

Number of elements of the tour To

Author

Cesar Asensio

Details

A tour of \(n\) vertices is a permutation of the ordered sequence 1:\(n\), and it is represented as a vector containing the integers from 1 to \(n\) in the permuted sequence. As a subgraph of the complete graph with \(n\) vertices, it is assumed that each vertex is adjacent with the anterior and posterior ones, with the first and last being also adjacent.

With respect to the TSP, a tour is invariant under cyclic permutation and inversion, so that there exists \((n-1)!/2\) different tours in a complete graph of \(n\) vertices. When searching for tours it is common to find the same tour under a different representation. Therefore, we need to establish whether two tours are equivalent or not. To this end, we can "gauge" the tour by permuting cyclically its elements until the first vertex is at position 1, and fix the orientation so that the second vertex is less than the last. Two equivalent tours will have the same "gauged" representation.

This function is used in search_tour_genetic to discard repeated tours which can be found during the execution of the algorithm.

See Also

search_tour_genetic implements a version of the genetic algorithm for the TSP.

Examples

set.seed(2)
T0 <- sample(1:9,9)   #        T0 = 2 6 5 9 7 4 1 8 3
gauge_tour(T0, 9)     # gauged T0 = 1 4 7 9 5 6 2 3 8