TSP_naif_Rcpp: TSP Naive Algorithm (C++ Implementation)

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

TSP Naive Algorithm (C++ Implementation)

Description

This function implements a naive heuristic approach for solving the Traveling Salesman Problem (TSP) in C++ and is exported to R using Rcpp. The algorithm uses a simple insertion method to construct a tour by adding cities one by one, minimizing the distance at each step (greedy strategy).

The algorithm starts from a specified city and iteratively adds the nearest non-visited city to the tour, updating the tour until all cities are visited. In "all" mode, the best tour is selected by testing all possible starting cities and computing the total distance for each tour.

Usage

TSP_naif_Rcpp(data, type = "one")

Arguments

data	A numeric matrix or data frame where each row represents a city and each column represents the coordinates of that city (e.g., x and y coordinates in 2D space).
type	A character string specifying how the starting city is chosen. Options include: "one" (default): Randomly selects a single starting city. "all": Tests all cities as possible starting points and selects the best tour.

Details

The algorithm is a heuristic approach and does not guarantee the global optimal solution, but aims to find a good solution in a reasonable amount of time.

• Time Complexity: O(n²), where 'n' is the number of cities. The algorithm computes the pairwise distances for each pair of cities.

• Space Complexity: O(n²) due to the storage of the distance matrix.

The result is a tour with the shortest found distance, based on the starting point(s) and insertion method.

Value

A numeric vector representing the order of cities in the shortest found tour. The vector is assigned the class "TSP".

Examples

n <- 40
villes <- matrix(runif(2*n), n, 2)
TSP_naif_Rcpp(villes, type = "one")

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