TSP_naif: Algorithme Naïf pour le Problème du Voyageur de Commerce...

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

Algorithme Naïf pour le Problème du Voyageur de Commerce (TSP)

Description

Résout le problème du voyageur de commerce (TSP) en utilisant une approche heuristique naïve basée sur l'insertion des villes dans le trajet à chaque étape. Le meilleur trajet est déterminé en testant un ou tous les points de départ possibles (option type).

Usage

TSP_naif(data, type = "one")

Arguments

data	Une matrice ou un data.frame représentant les coordonnées des villes. Les lignes doivent correspondre aux villes et les colonnes aux coordonnées (par exemple, x et y dans un espace 2D).
type	Un caractère indiquant la manière de choisir le point de départ : "one" (par défaut) : Une ville de départ est choisie aléatoirement. "all" : Teste toutes les villes comme point de départ et choisit le meilleur trajet.

Details

L'algorithme fonctionne en choisissant un point de départ (soit aléatoirement, soit en testant toutes les villes) et en insérant les villes restantes à chaque étape. La ville qui minimise la distance totale est ajoutée à chaque étape du trajet jusqu'à ce que toutes les villes soient visitées.

Une fois tous les trajets testés (en fonction de la stratégie de départ choisie), la fonction retourne le trajet avec la distance totale la plus courte.

Value

Un vecteur représentant l'ordre des villes à visiter pour obtenir le trajet le plus court, dans le cadre du problème du voyageur de commerce. Ce vecteur a un attribut class défini à "TSP".

Examples

n <- 10
villes <- matrix(runif(2*n), n, 2)
TSP_naif(villes, type = "one")

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