Pour trouver le plus court chemin

Question

J'ai la latitude et la longitude de 50 nœuds ou plus. Ce n'est pas connecté les uns aux autres. Nous considérerons un noeud comme début et fin à la fois.

J'ai besoin de trouver le chemin le plus court à travers ce nœud qui commence à 'start', se termine au même point de départ et traverse tous les nœuds.

Note: Sans utiliser google maps api

Answer 1

Le problème que vous décrivez est le Euclidean TSP, qui est NP-dur.

Pour les très petites entrées, vous pouvez le faire en utilisant la force brute. Pour des entrées plus importantes, un algorithme d'approximation peut être utilisé (tel que celui mentionné dans le lien, ce qui garantit une 2-approximation).

Answer 2

Cependant, vous ne disposez pas de données d'échantillons ici, je pense que cela peut fonctionner:

names<-#read your nodes 
rest<-list() 
A<-list() 
n=1 
for (i in 1:50){ 
    A<-get.all.shortest.paths(aracne_graph, names[i], names[i], mode = c("all"), weights=NULL) 
    rest[[n]]<-A$res 
    n<-n+1 
    } 
}