TSP_nearest: Nearest Neighbor Algorithm for Solving the Traveling Salesman...

In vrunge/M2algorithmique: Example of an Rcpp package for M2 Data Science students

Nearest Neighbor Algorithm for Solving the Traveling Salesman Problem (TSP)

Description

This function solves the Traveling Salesman Problem (TSP) using the nearest neighbor heuristic. It starts from either one city or all cities (iteratively) as possible starting points, and at each step, it selects the nearest unvisited city and inserts it into the tour.

Usage

TSP_nearest(data, type = "one")

Arguments

data	A numeric matrix or data frame of coordinates where each row represents a city and each column represents the x and y coordinates (for a 2D TSP).
type	A character string specifying the type of starting city selection. If 'type = "one"', the starting city is randomly chosen. If 'type = "all"', the algorithm tests all possible starting cities and selects the best one.

Value

A numeric vector representing the order of cities in the optimal tour, with the class attribute set to "TSP".

Examples

# Generate a random set of 5 cities
cities <- matrix(runif(10), ncol = 2)
# Solve TSP using nearest neighbor starting from one city
best_tour <- TSP_nearest(cities, type = "one")
# Solve TSP using nearest neighbor testing all starting cities
best_tour_all <- TSP_nearest(cities, type = "all")

vrunge/M2algorithmique documentation built on April 5, 2025, 4:06 a.m.