Discussion :

[galostroy]

Bonjour, je travaille actuellement sur R, j'ai quelques bases mais je rencontre quelques difficultés à coder.
Je souhaite positionner 7 objets sur une surface donnée (A,B,C,D,E,F,G). En considérant l'objet A comme point de départ et point d'arrivée, j'aimerais connaître la distance à parcourir pour passer une fois par chaque objet (uniquement une fois, donc pas de répétition) et en choisissant toujours d'aller à l'objet le plus proche de celui où je me trouve (se rapproche du problème du voyageur de commerce et donc de l'algorithme de Dijkstra). Malheureusement, mes bases ne me suffisent pas et j'ai besoin d'aide. Voici le code que j'ai écrit pour le moment qui me permet de générer 7 points aléatoirement sur ma surface donnée et d'obtenir les coordonnées x et y pour chaque point, le tout résumé dans la matrice train. À partir de cela, quelqu'un pourrait-il m'aider à mettre en place un code permettant d'obtenir cette distance ? Par avance merci pour votre aide.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
library(spatstat) 
Flow=runifpoint(7,win=owin(c(0,470),c(0,670))) #génère 7 points aléatoirement sur une surface donnée
plot(Flow) #graphique de la conformation
X=Flow$x #définit le vecteur X comme contenant les coordonnées x des points générés par runifpoint
Y=Flow$y #définit le vecteur Y comme contenant les coordonnées y des points générés par runifpoint
 
A=c(X[1],Y[1])
B=c(X[2],Y[2])
C=c(X[3],Y[3])
D=c(X[4],Y[4])
E=c(X[5],Y[5])
F=c(X[6],Y[6])
G=c(X[7],Y[7])
train=rbind(A,B,C,D,E,F,G)

[Emmanuel R]

Bonjour,
Pour ma part, je ne me servirais pas de ta matrice train. Je ne vais pas te donner de code tout prêt, mais seulement une idée de méthodologie :

• Coder une matrice des distances à partir de tes vecteurs X et Y. Cette matrice est carrée, dans ton cas de taille 7*7. Elle donne la distance entre deux points.
• Coder une fonction qui calcule la distance d'un chemin, à partir d'un chemin donné et de ta matrice des distances.
• Coder une fonction qui, à partir d'un point donné, regarde le point le plus proche (grâce à ta matrice des distances, en fixant une ligne) non visité (pour cela tu peux t'aider d'un vecteur avec des 1 et des 0...). N'oublie pas de revenir au point initial une fois que tous tes points ont été visités. Tu peux renvoyer, dans une liste, le chemin ainsi que la distance totale.
• Coder une fonction qui appelle la fonction ci-dessus pour tous tes points, et renvoie le chemin minimisant la distance totale.

Bon courage.