Visualiser une solution du problème du voyageur

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour tout le monde,

Je fais mon TIPE sur des métaheuistiques pour le problème du voyageur de commerce, et pour l'instant j'utilise une instance de test à 15 villes. Pour montrer un vrai résultat, j'ai trouvé le défi des 250 villes, qui fournit une liste de 250 villes au format CSV. Elles sont indiquées avec des coordonnées planes, toutes dans le carré du point $(0,0)$ à $(1,1)$. Pour visualiser ma solution, j'aimerais bien les afficher sur un graphique et relier les points entre eux suivant ma solution afin de bien visualiser le cycle obtenu. J'ai plusieurs possibilités:

  • Utiliser matplotlib. Si je me trompe pas, il faudrait ordonner les villes puis séparer les abscisses et les ordonnées en 2 tableaux et faire appel à plt.plot() qui s'occuperait de me tracer les segments entre les villes dans l'ordre ?

  • Utiliser Pillow. J'ai vu dans le dernier CdS que certains l'utilisaient pour faire la visualisation du feu de forêt, mais je me demande si c'est réellement une bonne idée si matplotlib fait l'affaire, je réinventerais un peu la roue

  • Utiliser une bibliothèque SVG

Que me conseilleriez-vous ?

P.S: je fais mes schémas en SVG avec Inkscape, est-ce que c'est une bonne idée pour le rapport en LaTeX ?

+0 -0
Auteur du sujet

J'avais pensé à Graphviz mais dans ce cas j'ai besoin de mettre les villes à des positions précises, alors que Graphviz (je crois) fait le placement à ta place. Ceci dit c'est pratique ce logiciel, je m'en sers pour les illustrations aussi.

Je vais essayer avec matplotlib alors.

+0 -0

Cette réponse a aidé l'auteur du sujet

Avec matplotlib, une technique simple (un peu moche, mais sûrement améliorable) :

1
2
3
4
5
6
7
8
import matplotlib.pyplot as plt

l = [(0.1,0.1), (0.9,0.7), (0.4,0.5), (0.6,0.3)]   # exemple bidon
x, y = zip(*l)

plt.scatter(x, y)   # dessine les villes
plt.plot(x, y)      # dessine le chemin
plt.show()

Édité par yoch

+0 -0
Auteur du sujet

J'ai réussi avec matplotlib ! Voilà le résultat:

test

Le code:

1
2
3
4
5
6
7
import matplotlib.pyplot as plt
l = [(0,1),(1,-1),(-1,-1), (0,1)]
x,y = zip(*l)
plt.plot(x,y, '--ro')
plt.xlim([-1.2,1.2])
plt.ylim([-1.2, 1.2])
plt.show()

Problème résolu, merci à vous deux !

Édité par anonyme

+0 -0
Auteur du sujet

Ça pourrait marcher effectivement. Après je trouve que c'est plus adapté d'utiliser matplotlib, je l'utilise déjà et avoir la fenêtre avec le zoom et tout est très pratique vu que y'a 250 villes concentrées dans un carré de côté 1.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte