Bonjour,
Je suis confronté au problème suivant : j'ai les coordonnées GPS de 25 villes et les temps de parcours en véhicule entre ces 25 villes (donc une matrice symétrique de 25x25).
Objectif : représenter sur une carte 2D ces 25 villes, non pas avec les coordonnées GPS mais grâce aux distances entre les différentes communes.
A titre d'exemple, si on consièdre trois communes, les trois distances permettraient de tracer le triangle correspondant.
Merci par avance pour votre aide !
Salut !
et bien : tu commence par prendre trois villes au hasard, tu traces le triangle correspondant, puis tu considère une 4e ville, et avec les distances aux trois villes déjà placer il y a au mieux un nombres finies d'endroit au tu peux la mettre : en général il n'y en aura qu'un (enfin si la matrices est remplies avec des fausses données il y en aura en général 0...) et si il y en a plusieur c'est que les trois villes placé précèdement avec un axes de symétrie et donc c'est pas très important...
et tu recommence avec la 5e ville etc etc... (sauf que cette fois si il y a plusieur possibilité tu choisit entre les possibilités par rapport aux distances à toutes les villes déjà placé, pas seulement les 3 première...
Effectivement, je suis d'accord avec la méthode mathématique.
Je précise donc le besoin : existe t-il un logiciel qui à partir d'une matrice de distance réalise la représentation graphique ?
En effet, si je généralise à 1000 villes, l'exercice manuel n'est pas aisé!
Je doute très fortement qu'il existe un logiciel qui propose cela comme fonction de base (etant donné que en génèral c'est impossible à faire ^^, et que je vois pas trop à quoi ca servirait... )
en revanche il y a plein de logiciel qui te permetront de programer toi même quelques choses qui le fera : Excel, Maple, Matlab. ou encore tu peux aussi le coder dans n'importe qu'elle 'vrai' language de programation ca sera pas extrémement compliqué à faire. L'ideal étant d'en choisir un que tu connais déjà ^^
bonsoir,
il existe une méthode statistique qui répond je pense à ta question: le positionnement multidimensionnel (multidimensional scaling en Anglais). Etant donnée une matrice de distances entre n objets (ou plutôt entre les n(n-1)/2 paires d'objets distincts), il s'agit de trouver pour chaque entier k<=n une représentation en dimension k, c'est-à-dire les positions (coordonnées) de n points de R^k de sorte que les distances entre ces points reconstruisent "au mieux" les distances données. "Au mieux" étant pris comme minimisant la somme des carrés des écarts entre distances données et distances reconstruites. Evidemment ces positions sont définies à une isométrie près. Moyennant le choix arbitraire d'un centre et d'une orientation, on a pour chaque k une solution explicite. Ca vient de la décomposition de l'inertie.
Il y a des logiciels qui font ça très bien, par exemple sous R, il y a la fonction cmdscale.
est-ce vraiment utilisable pour 1000pts?
le fait de savoir qu'il existe une réponse permet d'utiliser la méthode de Ksilver. Je ne sais pas comment le programme proposé par ambrosio marche mais ça m'étonnerais pas (vu qu'il cherche un optimum etc...) que ce programme prenne beaucoup beaucoup de temps pour 1000 points.
Merci pour cette réponse ; je vais tester cette fonction.
Au vu d'une lecture rapide, il semblerait que ce soit la méthode adaptée : http://www.personality-project.org/R/mds.html
je viens de tester, sur mon ordinateur poussif vieux de 4 ans, le temps d'exécution de cmdscale avec 1000 points est d'environ 5 secondes, donc c'est très jouable.
On doit pouvoir calculer la complexité exactement. En fait le problème revient à trouver les k premiers vecteurs propres d'une matrice nxn, où n est le nombre de points. On n'a pas besoin de diagonaliser complètement la matrice. Pour dessiner une carte, ce qui est la question initiale, il faut prendre k=2. Je crois qu'on trouve ces vecteurs propres en considérant les puissances successives d'une certaine matrice. Donc il faut exécuter un certain nombre produits de matrices nxn, jusqu'à convergence. On va dire que ce nombre est du même ordre que n (ça c'est pas bien sûr...). Le calcul du produit de deux matrices nxn comporte de l'ordre de n^3 opérations, et donc la complexité serait de l'ordre de n^4 (à la louche et à confirmer par quelqu'un qui s'y connaît).
Le logiciel RGui et la fonction cmdscale fonctionne parfaitement.
Le calcul pour une matrice 25*25 est instantané.
Voila le résultat obtenu avec une matrice de temps de trajet.
