build_tour_greedy {gor} | R Documentation |
Building a tour for a TSP using the greedy heuristic
Description
Greedy heuristic tour-building algorithm for the Traveling Salesperson Problem
Usage
build_tour_greedy(d, n)
Arguments
d |
Distance matrix of the TSP. |
n |
Number of vertices of the TSP complete graph. |
Details
The greedy heuristic begins by sorting the edges by increasing distance. The tour is constructed by adding an edge under the condition that the final tour is a connected spanning cycle.
Value
A list with two components: $tour contains a permutation of the 1:n sequence representing the tour constructed by the algorithm, and $distance contains the value of the distance covered by the tour.
Author(s)
Cesar Asensio
See Also
build_tour_nn uses the nearest heighbor heuristic, build_tour_nn_best repeats the previous algorithm with all possible starting points, compute_tour_distance computes tour distances, compute_distance_matrix computes a distance matrix, plot_tour plots a tour, build_tour_2tree constructs a tour using the double tree 2-factor approximation algorithm.
Examples
## Regular example with obvious solution (minimum distance 48)
m <- 10 # Generate some points in the plane
z <- cbind(c(rep(0,m), rep(2,m), rep(5,m), rep(7,m)), rep(seq(0,m-1),4))
n <- nrow(z)
d <- compute_distance_matrix(z)
b <- build_tour_greedy(d, n)
b$distance # Distance 50
plot_tour(z,b)
## Random points
set.seed(1)
n <- 25
z <- cbind(runif(n,min=1,max=10),runif(n,min=1,max=10))
d <- compute_distance_matrix(z)
b <- build_tour_greedy(d, n)
b$distance # Distance 36.075
plot_tour(z,b)