Problème du voyageur

Version imprimable

14/01/2016, 10h24
python_prog

Problème du voyageur

Bonjour,
je dois écrire un programme sous python 2.7 , faisant intervenir les classes et objets.
Mon problème est : à partir de coordonnées GPS ( longitude et Latitude), trouver le meilleurs trajet entre 12 Villes différentes.
Merci de votre aide,
Cordialement,
Une étudiante qui débute python.
14/01/2016, 10h41
marco056

L'objectif du forum, c'est l'entraide, pas le travail bénévole pour les autres.
Tu présentes ton code (avec les balises de code) et les participants t'aiguillent.

prog_voyageur

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
###!/usr/bin/python
### -*- coding: utf-8 -*-
 
from math import *
from copy import *
 
class cVille():
    def __init__(self,n):
       self.posX = [6,1,2,4,9,8]
       self.posY = [5,3,7,10,3,6]
       self.nom = n
 
    def calculerDistance(self):
        n=0
        i=1
        fib=[]
        fib1=[]
 
        while(n<5):
            fib=[]
            while(i<6-n):
 
                val=sqrt(abs(self.posY[i+n]-self.posY[n])+abs(self.posX[i+n]-self.posX[n]))
                fib.append(val)
                i +=1
            n+=1
            i=1
            fib1=copy(fib)
            print "\n"
            print "Distance(s):",n,fib1
 
paris=cVille("Paris")
lyon=cVille("Lyon")
marseille=cVille("Marseille")
bordeaux=cVille("Bordeaux")
nantes=cVille("Nantes")
lille=cVille("Lille")
 
print " NOM", " X" " Y"
print paris.nom,paris.posX[0],paris.posY[0]
print lyon.nom,lyon.posX[1],lyon.posY[1]
print marseille.nom,marseille.posX[2],marseille.posY[2]
print bordeaux.nom,bordeaux.posX[3],bordeaux.posY[3]
print nantes.nom,nantes.posX[4],nantes.posY[4]
print lille.nom,lille.posX[5],lille.posY[5]
print "\n"
paris.calculerDistance()

Salut,

sans vouloir être méchant ou même désagréable, il manque les bases de la programmation objet là...

d'après ton code, chaque instance de cVille contient les positions de toutes les villes, ça n'a pas de sens. Chaque ville devrait connaitre uniquement sa propre position qui serait fournie à l'instanciation:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class cVille(): def __init__(self,name, pos_x, pos_y): self.pos_x = pos_y self.pos_y = pos_y self.nom = name ... paris=cVille("Paris", 6, 5) lyon=cVille("Lyon", 1, 3) marseille=cVille("Marseille", 2, 7) ... print " NOM", " X", " Y" print paris.nom, paris.posX, paris.posY print lyon.nom, lyon.posX, lyon.posY ...
pour la méthode calculerDistance, je suis pas certain de comprendre ce qu'elle est censée faire; ça serait bien de nous l'expliquer.
mais intuitivement, je pense que ça sera toujours utile que ta classe cVille possède une méthode qui permette de calculer la distance avec une autre ville fournie en paramètre. pour ce qui est des itinéraires, on verra ça après.

14/01/2016, 14h37
python_prog

calculer_distance

La fonction calculer_distance, avec deux boucles While, permet de calculer et de mettre dans un tableau, les valeurs des distances entre 2 villes ( calcule vectoriel avec les coordonnées des villes), et de montrer sous forme de "Score" la distance pour chaque cas de mon algorithme génétique, pour l'instant, seul la combinaison { Paris-Lyon-Marseille-Bordeaux-Nantes-Lille } fonctionne , il faut faire cela pour toutes les combinaison possible soit 6! ( 6 factorielle) => (Paris-Lyon-Marseille-Lille-Nantes-Bordeaux ou Lyon-Bordeaux-Nantes-Paris-Lille ou etc...) le but étant de trouver la meilleure combinaison de villes pour faire le moins de distance possible.
Ps: Je n'ai jamais codé en python avant aujourd'hui et encore moins en orienté objet, j'avoue être un peu perdu... x)
14/01/2016, 14h43
wiztricks

Citation:

Envoyé par python_prog

Ps: Je n'ai jamais codé en python avant aujourd'hui et encore moins en orienté objet, j'avoue être un peu perdu... x)

Ben dans ce cas, il faudrait que vous preniez le temps d'ouvrir un tutoriel. Ils ont aussi été écrits pour vous.

- W
14/01/2016, 14h54
python_prog

J'en ai lu beaucoup...

Bonjour, j'ai lu pas mal de tutoriel, cela n'aide en rien, le fait que je n'arrive pas à orienter ce que j'ai lu, par rapport à mon problème, je me tourne donc vers le forum pour m'éclairer.

Citation:

Envoyé par python_prog

Ps: Je n'ai jamais codé en python avant aujourd'hui et encore moins en orienté objet, j'avoue être un peu perdu... x)

pour simplifier enormément, on peut dire que la programmation objet cherche à modéliser le monde tel qu'il est.
par exemple, une voiture a des caractéristiques: 4 roues, un moteur, 2 sièges (parce que c'est une sportive), un reservoir d'essence, une couleur, etc
une voiture a aussi des "comportements": démarrer, accélérer, freiner, tourner, écraser un piéton, etc...

si on veut faire une classe qui représente une voiture, on va modéliser (dans une certaine mesure) cette réalité. les caractéristique de la voiture deviennent des attributs et les comportements deviennent des méthodes.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Voiture(object): def __init__(self, niveau, couleur, moteur): self.niveau_essence = niveau self.couleur = couleur self.moteur = moteur def démarrer(self): # code def accélérer(self): # code def freiner(self): # code def écraser(self, piéton): # code
tout ça pour dire qu'on ne fait pas des classe en mettant tout et n'importe quoi dedans sans réfléchir et que d'une manière générale on met ensemble les données et les traitements sur ces données.

après, cette présentation est très schématisé et je te conseillerai de trouver des tutos sur la programmation orientée objet si tu veux bosser correctement avec des classes. EDIT: après survol (très) rapide, celui-ci a l'air pas mal

dans ton cas particulier ça se traduit par ce que je t'ai déjà dit: chaque ville ne devrait avoir connaissance que de ses propres caractéristiques (nom et coordonnées) et n'effectuer que des traitements qui la concernent (calculer sa distance par rapport à une autre ville par exemple).
ensuite, si tu veux calculer un itinéraire, il faudra probablement faire une classe Itinéraire qui aura des caractéristiques (une ville de départ, une ville d'arrivée, une liste d'étapes possibles, etc...) et des traitements associés comme "trouver la route la plus courte entre le départ et l'arrivée en passant par toutes les étapes" par exemple...

Programme un peu complété

Dans la déclaration de variable, c'est self.nom pas self.name ? ainsi que la coordonnée en X, self.pos_x et non self.pos_y.
Voila mon programme, je ne vois pas du tout comment procéder pour la résolution des 720 chemins différents du parcours de 6 villes. ( qui doit avoir un squelette identiques si on met 12 villes)
j'ai fait un random, pour tirer les villes aléatoirement dans un tableau, sans pour autant savoir, si mon tableau n'existe pas deja, en gros :" il peut y avoir des doublons." ='(

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#!/usr/bin/python
# -*- coding: utf-8 -*-
 
from math import *
from copy import *
from random import *
 
 #--------------------------------CLASSE VILLE------------------------------------------------------------------------------------------------   
class cVille():                                                                                             
    def __init__(self, nom, pos_x, pos_y):
       self.pos_x = pos_x
       self.pos_y = pos_y
       self.posYZ = []
       self.premier=[]
       self.nom = name
       self.ville =["Paris","Lyon","Marseille","Bordeaux","Nantes","Lille"]
 
 
    def randomTrajet(self):
        paris=[0,1]
        i=0
 
        while (i<2):
           self.pos_x.insert(0,paris[i])
           self.pos_y.insert(0,paris[i])
 
        print self.pos_x
        print self.pos_y
 
    cpt=0
    while cpt<2:
           cpt +=1
           shuffle(self.ville)
           print self.ville
 
 
 
    def calculerDistance(self):                                         
        n=0
        i=1
        fib=[]
        fib1=[]
        while(n<5):
            fib=[]
 
            while(i<6-n):
                    val=sqrt(abs(self.posY[i+n]-self.posY[n])+abs(self.posX[i+n]-self.posX[n]))
                    fib.append(val)
                    i+=1     
            n+=1
            i=1
            fib1=copy(fib)
            self.premier.append(fib[0])
            print "Distance(s)avec :",fib1,fib[0]
            print "\n"
        print self.premier
        print "Somme:",sum(self.premier)
 
 
 
#-----------------------------------------------------------------------------
 
 
paris=cVille("Paris", 6, 5)
lyon=cVille("Lyon", 1, 3)
marseille=cVille("Marseille", 2, 7)
bordeaux=cVille("Bordeaux", 4, 10)
nantes=cVille("Nantes", 9, 3)
lille=cVille("Lille", 8, 6)
trajet=cVille("test")
print " NOM", " X" " Y"
 
print "\n"
paris.calculerDistance()
trajet.randomTrajet()

salut,

j'en profite pour rebondir -ça reste dans la continuité du sujet- comme je ne code pas des masses orienté objet et que je me pose la question également;

Citation:

Envoyé par Tryph

chaque ville ne devrait avoir connaissance que de ses propres caractéristiques (nom et coordonnées) et n'effectuer que des traitements qui la concernent (calculer sa distance par rapport à une autre ville par exemple).

alors justement, sachant que dans la liste des villes il y a déjà celle qui concerne l'objet instancié, c'est vraiment nécessaire -ou du moins une bonne pratique- d'avoir self.posX et self.posY alors qu'on peut retrouver les valeurs via la liste globale des villes (ou peut-être qu'on s'en fout et que c'est vraiment un détail) ?

de la même façon, cette liste, est-ce qu'il vaut mieux la mettre en dehors de toute classe (mais dans le module quand même) en "global" ou est-ce qu'il vaut mieux la déclarer dans la classe (auquel cas on a une copie de la liste à chaque fois qu'on instancie un objet si j'ai bien compris) ?

typiquement est-ce qu'une structure du genre est une bonne idée ou pas :
Code:

1 2 3 4 5 6 7 8 9 10 ville = { 'Paris': {'x': 6, 'y': 5, 'obj': None}, # 'obj' servira à récupérer l'objet instancié 'Lyon': {'x': 1, 'y': 3, 'obj': None}, 'Marseille': {'x': 2, 'y': 7, 'obj': None} } for nom in ville.keys(): ville[nom]['obj'] = cVille(nom) ville['Paris']['obj'].mymethod()

Salut,

Juste mon grain de sel ...

Code:

1
2
3
val = sqrt(abs(self.posY[i+n] - self.posY[n]) ** 2 + \
           abs(self.posX[i+n] - self.posX[n]) ** 2)

Non ?

Citation:

Envoyé par BufferBob

alors justement, sachant que dans la liste des villes il y a déjà celle qui concerne l'objet instancié, c'est vraiment nécessaire -ou du moins une bonne pratique- d'avoir self.posX et self.posY alors qu'on peut retrouver les valeurs via la liste globale des villes (ou peut-être qu'on s'en fout et que c'est vraiment un détail) ?

Techniquement, on aura le même résultat... donc c'est un détail.
Mais çà fabrique des mots "villes": une collection, "ville": la chose avec son nom et des coordonnées auxquels on va pouvoir coller des "verbes" (les méthodes).
Ca peut être important si ces mots reflètent la conception de la solution car çà va permettre de retrouver comment ont été traduits certains concepts.

Citation:

Envoyé par BufferBob

de la même façon, cette liste, est-ce qu'il vaut mieux la mettre en dehors de toute classe (mais dans le module quand même) en "global" ou est-ce qu'il vaut mieux la déclarer dans la classe (auquel cas on a une copie de la liste à chaque fois qu'on instancie un objet si j'ai bien compris) ?

Dans une classe Python, on peut faire coexister des attributs/méthodes de classe et des attributs/méthodes d'instances.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Ville: _instances = {} def __new__(cls, nom, x, y): z = cls._instances.get(nom) if not z: z = cls._instances[nom] = super().__new__(cls) return z @classmethod def get(cls, nom): return cls._instances.get(nom) @classmethod def distance(cls, a, b): u = cls.get(a) v = cls.get(b) d = *tbd*(u, v) return d
Citation:
Envoyé par BufferBob
typiquement est-ce qu'une structure du genre est une bonne idée ou pas :
Code:

1 2 3 4 5 6 7 8 9 10 ville = { 'Paris': {'x': 6, 'y': 5, 'obj': None}, # 'obj' servira à récupérer l'objet instancié 'Lyon': {'x': 1, 'y': 3, 'obj': None}, 'Marseille': {'x': 2, 'y': 7, 'obj': None} } for nom in ville.keys(): ville[nom]['obj'] = cVille(nom) ville['Paris']['obj'].mymethod()
Je dirais que ce n'est pas une bonne idée car çà mélange des données (constantes) avec des objets crées par la suite.
Partir de:
Code:

1 2 3 4 5 6 7 VILLES = ( ('Paris', 5, 6), ('Lyon', 1, 2), ('Marseille', 2, 7), } for nom, x, y in VILLES: ville(nom, x, y)
ou de:
Code:

1 2 3 ville('Paris', 5, 6) ville('Lyon', 1, 2) ville('Marseille', 2, 7)
permet de dire: voilà à partir de là, j'ai transformé les données brutes en informations, on va pouvoir commencer à bosser sérieusement.

Citation:

Envoyé par python_prog

Dans la déclaration de variable, c'est self.nom pas self.name ? ainsi que la coordonnée en X, self.pos_x et non self.pos_y.
Voila mon programme, je ne vois pas du tout comment procéder pour la résolution des 720 chemins différents du parcours de 6 villes. ( qui doit avoir un squelette identiques si on met 12 villes)
j'ai fait un random, pour tirer les villes aléatoirement dans un tableau, sans pour autant savoir, si mon tableau n'existe pas deja, en gros :" il peut y avoir des doublons." ='(

S'il vous est possible d'utiliser la fonction permutations du module itertools, c'est pas bien compliqué.

- W

Citation:

Envoyé par python_prog

Dans la déclaration de variable, c'est self.nom pas self.name ? ainsi que la coordonnée en X, self.pos_x et non self.pos_y.

dans l'exemple que je t'ai donné, j'ai mis des nom plus "pythoniques" (c'est à dire des noms qui respectent les conventions de codage Python), mais tu peux mettre les noms que tu veux, ça fonctionnera pareil.

Citation:

Envoyé par python_prog

Voila mon programme, je ne vois pas du tout comment procéder pour la résolution des 720 chemins différents du parcours de 6 villes. ( qui doit avoir un squelette identiques si on met 12 villes)
j'ai fait un random, pour tirer les villes aléatoirement dans un tableau, sans pour autant savoir, si mon tableau n'existe pas deja, en gros :" il peut y avoir des doublons." ='(

alors j'aurais beaucoup de chose à dire sur la nouvelle version de ton programme qui ne tient pas tellement compte de ce que j'ai pu raconter plus haut (peut être que je vais m'abstenir, pas sûre ;) ), mais pour ce qui est des 720 chemins possible je peux déjà te parler d'itertools.permutations qui va grandement te simplifier la tache:
Code:

1 2 3 4 >>> from itertools import permutations >>> une_liste = [1, 2, 3] >>> [permutation for permutation in permutations(une_liste)] [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
pour expliquer simplement, la fonction permutations te retourne un itérateur (et pas directement une liste) qui va te sortir successivement toutes les permutations possibles à partir de la liste que tu lui fournis en paramètre, sans en oublier une et sans doublon. c'est cool hein?

ensuite, pour commenter ton code et redire ce que j'ai déjà mais plus clairement... selon moi, ta classe Ville ne devrait avoir que:

un attribut nom (ou name, ou autre qui décrit bien ce qu'il contient)
un atribut pos_x (ou posX, ou autre du moment que son nom est bien choisi et qu'il respecte, de préférence, la PEP8)
un attribut pos_y
une méthode distance(self, ville) qui accepte un objet de type Ville en paramètre et qui renvoie la distance entre la ville courante (self) et la ville fournie en paramètre
rien d'autre! (dans un premier temps au moins) tout le reste devrait se trouver ailleur (= dans une(des) autre(s) classe(s))

comme je l'ai dit, dans la réalité, une ville à une position, un nom et elle est à une distance donnée de chaque autre ville, mais le calcul d'un itinéraire ne concerne pas UNE SEULE ville, il concerne un ensemble de villes qui ne peut être un objet Ville ni être un attribut de Ville (enfin y a toujours moyen de trouver une façon de faire comme ça... comme y a toujours moyen de faire un trajet Marseille-Lille en marche arrière si on veut).

tu aurais donc besoin d'une classe Itinéraire pour gérer un chemin entre 2 villes, qui aurait un attribut qui consisterait en une liste de villes à traverser et qui saurait calculer sa propre longueur (et pas la longueur de quoi que ce soit d'autre)
tu aurais probablement aussi besoin d'une structure listant les Itinéraires possibles et sachant trouver le plus court, peut être une classe qui aurait un attribut qui serait une liste d'itinéraires et une méthode qui saurait trouver le plus court

enfin tout ça c'est si tu veux faire les chose "bien" (ce n'est que mon point de vue mais il est partagé par pas mal de monde ;)) avec des classes.
sinon, si tu ne te sens pas à l'aise avec l'orienté objet, tu peux faire ça entièrement en procédural, sans utiliser de classes. c'est même pas moins bien, c'est juste une autre façon de faire. mais dans ce cas tu n'as pas besoin de classes.

Citation:

Envoyé par BufferBob

alors justement, sachant que dans la liste des villes il y a déjà celle qui concerne l'objet instancié, c'est vraiment nécessaire -ou du moins une bonne pratique- d'avoir self.posX et self.posY alors qu'on peut retrouver les valeurs via la liste globale des villes (ou peut-être qu'on s'en fout et que c'est vraiment un détail) ?

beaucoup de gens considèrent que c'est une mauvaise pratique d'avoir quoi que ce soit qui soit global. de mon point de vue, on peut avoir une liste globale pour instancier des objets, mais une fois les objet créés et rangés dans une structure quelconque, on ne devrait plus se servir de la liste globale. l'un des grand intérêt des classes et de la prog orientée objet en général, c'est que ça permet d'organiser son code en regroupant les données qui concernent une entité quelconque et les traitement qui concernent ces données dans un même objet.
je sais pas trop si ça répond à ta question, mais en même temps je suis pas certain de l'avoir bien comprise ;)

Citation:

Envoyé par BufferBob

de la même façon, cette liste, est-ce qu'il vaut mieux la mettre en dehors de toute classe (mais dans le module quand même) en "global" ou est-ce qu'il vaut mieux la déclarer dans la classe (auquel cas on a une copie de la liste à chaque fois qu'on instancie un objet si j'ai bien compris) ?

j'ai mis la réponse au dessus, mais je la répète: une classe Ville ne devrait contenir que des infos sur UNE SEULE ville. donc la liste de toutes les villes ne devrait pas se trouver dans une classe Ville. des exemples de classes qui pourraient avoir une légitimité à contenir une liste de villes pourraient être une Région, un Itinéraire, un Pays, une CollectionDeChefLieux, etc...
Citation:
Envoyé par BufferBob
typiquement est-ce qu'une structure du genre est une bonne idée ou pas :
Code:

1 2 3 4 5 ville = { 'Paris': {'x': 6, 'y': 5, 'obj': None}, # 'obj' servira à récupérer l'objet instancié 'Lyon': {'x': 1, 'y': 3, 'obj': None}, 'Marseille': {'x': 2, 'y': 7, 'obj': None} }
un dictionnaire qui associe ses coordonnées à chaque nom de ville est une bonne idée pour instancier tous les objets Ville dont on a besoin car:
- on peut instancier toutes les villes avec une simple boucle au lieu de répeter l'instanciation pour chaque ville
- ça met toutes les infos au même endroit, c'est plus clair

par contre je pense qu'une telle liste est bien pour faire de l'initialisation, pas plus. Elle ne devrait donc pas avoir de place libre pour y mettre l'instance de Ville car effectivement dans ce cas l'info est redondante.
si on veut garder toutes les références aux villes dans une structure, on peut utiliser une simple liste d'objets Ville (qui contient donc toutes les infos utiles) ou éventuellement un dictionnaire qui associe à chaque nom de ville son objet (le nom de la ville est alors redondant mais ça permet de retrouver plus facilement l'objet qu'on veut). encore mieux: cette collection de ville peut être un attribut d'une classe qui, puisqu'elle connait toutes les villes, va pouvoir faire des traitements dessus comme trouver la ville la plus proche d'une autre villes, trouver toutes les villes dans un rayon donné à partir d'un point donné, etc...

14/01/2016, 20h27
Tryph
Citation:
Envoyé par VinsS

Salut,

Juste mon grain de sel ...

Code:

1 2 3 val = sqrt(abs(self.posY[i+n] - self.posY[n]) ** 2 + \ abs(self.posX[i+n] - self.posX[n]) ** 2)

Non ?
c'est bien possible oui. et donc on n'a plus besoin du abs()
14/01/2016, 23h18
VinsS

Citation:

Envoyé par Tryph

c'est bien possible oui. et donc on n'a plus besoin du abs()

Bien vu.

Bonjour

Voila l'avancé de mon programme, sous Python.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#!/usr/bin/python
# -*- coding: utf-8 -*-
 
from math import *
from copy import *
from itertools import *
 
#class cTrajet():
#    def __init__(self,trajet):
#
#    def distance(self):
#       X= sum(
 
class cVille(cTrajet):                                                                                             
    def __init__(self,n, pos_x, pos_y):
       self.posX = pos_x
       self.posY = pos_y
       self.nom = n
 
    def calculerDistance(self,n):                                         
        val=sqrt(abs(n.posY-self.posY)+abs(n.posX-self.posX))
 
        print"Distance(s):",val
 
 
class cItineraires():
    def __init__(self,traj):
        self.Traj=traj      
    def trajectoire(self,n):
        tab=list(permutations(self.Traj))
 
 
 
 
 
paris=cVille("Paris",6 ,5)
lyon=cVille("Lyon",1 ,3)
marseille=cVille("Marseille",2 ,7)
bordeaux=cVille("Bordeaux",5 ,9)
nantes=cVille("Nantes",3 ,8)
lille=cVille("Lille",9 ,10)
print paris.nom,paris.posX,paris.posY
print lyon.nom,lyon.posX,lyon.posY
print marseille.nom,marseille.posX,marseille.posY
print bordeaux.nom,bordeaux.posX,bordeaux.posY
print nantes.nom,nantes.posX,nantes.posY
print lille.nom,lille.posX,lille.posY
print "\n"
Itineraire=cItineraires(["paris","lyon","marseille","bordeaux","nantes","lille"])
Itineraire.trajectoire(lille)

Bonjour, je ne sais pas comment coder la classe Trajet, pour avoir la distance de chaque liste, de plus je ne pense pas avoir toutes les possibilités de liste de ville.
Merci d'avance.

ça commence à être mieux mais j'ai encore quelques remarques/questions:

pourquoi veux-tu que cVille hérite de cTrajet? je pense que cVille doit hériter d'object, mais je veux bien que tu explique ce que tu as voulu faire
ta méthode cVille.calculerDistance ne tient pas compte de la remarque de VinsS sur la formule du calcul entre 2 points, c'est volontaire?
la méthode cVille.calculerDistance devrais retourner le résultat plutôt que de l'afficher
une astuce pour moins s'embêter à afficher les objets cVille, c'est d'y ajouter une méthode __str__ qui permet de récupérer une représentation de l'objet sous forme de chaine (explication plus bas)
ce que tu dois fournir à ta classe cItineraires n'est pas une liste de noms de villes, mais une liste d'objets cVille
à quoi est censé servir le paramètre "n" de ta méthode cItineraires.trajectoire? à première vue, je pensais que cette méthode servait à récupérer tous chemins possibles passant par chacune des villes.
ta classe cItineraires devrait contenir une liste d'itinérairess en plus de la liste de villes
n'hésite pas à donner des noms explicites à tes variables, la relecture et la compréhension du code sera plus simple
ça serait bien que tu mettes des commentaires dans ton code pour expliquer ce que tu cherches à faire car là on a l'impression que tu essaies des choses un peu au hasard; du coup c'est pas facile de te dire exactement ce qui ne va pas dans ta façon de faire.

j'ai bien d'autres remarques mais on va y aller progressivement ;)

point 4:
ajoute une méthode __str__ à ta classe cVille (c'est pas obligatoire, mais tu vas voir que c'est pratique):
Code:

1 2 3 4 class cVille(object): ... def __str__(self): return "{} ({}; {})".format(self.nom, self.posX, self.posY)
cette méthode va te permettre d'afficher tes villes de cette manière:
Code:

1 2 3 print paris # affiche Paris (6; 5) print lyon # affiche Lyon (1; 3) print marseille # affiche Marseille (2; 7)
pour plus d'infos sur la méthode de formatage de chaine utilisée, je te laisse consulter sa documentation

point 5:
ta classe cItineraires ne va pas pouvoir faire grand chose avec une liste de noms de villes. une liste d'objects cVille lui sera bien plus utile.

Code:

Itineraires = cItineraires([paris, lyon, marseille, bordeaux, nantes, lille])

point 7:
ta classe cItineraires (au pluriel) peut avoir de liste de villes afin de calculer toutes les permutations possible, mais elle devrait aussi avoir une liste d'itinéraires (= la liste des permutations).
Code:

1 2 3 4 class cItineraires(): def __init__(self, villes): self.villes = villes self.permutations = list(permutations(self.villes)) # attention quand même, cette liste peut prendre beaucoup de place en mémoire
un itinéraire particulier pourrait être modélisé par une classe cItineraire (au singulier) qui contiendrait une permutation particulière et qui saurait calculer sa distance, mais c'est pas obligatoire. tu peux te contenter de mettre une méthode distance_itineraire(indice) dans la classe cItineraires pour calculer la distance d'UN itinéraire:
Code:

1 2 3 4 5 6 7 8 9 10 11 class cItineraires(): ... def distance_itineraire(indice): itineraire = self.permutations[indice] etape_iterator = iter(itineraire) # récupère une itérateur qui va te permette de parcourir la liste des étapes de ton itinéraire etape_precedante = etape_iterator.next() # permet de garder la première etape de coté distance = 0 # initialise le compteur de distance for etape_courante in etape_iterator: distance += etape_courante.calculerDistance(etape_precedante) # calcule la distance entre 2 villes consécutive et l'ajoute à la distance de l'itinéraire etape_precedante = etape_courante return distance
j'ai pas du tout essayé d'exécuter ce code alors il est possible que quelques erreurs se cachent dedans, mais ça donne une idée assez précise de comment faire.

quand tu auras fait tout ça ton code sera en mesure de calculer tous les itinéraires possibles passant par toutes tes villes et calculer la longueur de chacun.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#!/usr/bin/python
# -*- coding: utf-8 -*-
 
from math import *
from copy import *
from itertools import *
 
 
class cTrajet():
    def __init__(self, villes):
        self.villes = villes
        self.permutations = list(permutations(self.villes))
 
    def distance(self,indice):
        itineraire = self.permutations[indice]
        etape_iterator = iter(itineraire)  
        etape_precedante = etape_iterator.next()  
        distance = 0
        for etape_courante in etape_iterator:
            distance += etape_courante.calculerDistance(etape_precedante)
            etape_precedante = etape_courante
        return distance
 
class cVille():                                                                                             
    def __init__(self,n, pos_x, pos_y):
       self.posX = pos_x
       self.posY = pos_y
       self.nom = n
 
    def calculerDistance(self,n):                                         
       val=sqrt(abs(n.posY-self.posY)+abs(n.posX-self.posX))
       print"Distance(s):",val
 
paris=cVille("Paris",6,5)
lyon=cVille("Lyon",1,3)
marseille=cVille("Marseille",2,7)
bordeaux=cVille("Bordeaux",5,9)
nantes=cVille("Nantes",3,8)
lille=cVille("Lille",9,10)
 
print paris.nom,paris.posX,paris.posY
print lyon.nom,lyon.posX,lyon.posY
print marseille.nom,marseille.posX,marseille.posY
print bordeaux.nom,bordeaux.posX,bordeaux.posY
print nantes.nom,nantes.posX,nantes.posY
print lille.nom,lille.posX,lille.posY
print "\n"
Trajet=cTrajet([paris,lyon,marseille,bordeaux,nantes,lille])
 
i=0
while(i<720):
    Trajet.distance(i)
    i+=1

Par rapport à votre programme que vous m'avez envoyé lors du dernier message , cette ligne rencontre un problème
distance += etape_courante.calculerDistance(etape_precedante)
J'ai l'erreur unsupported operand type(s) for +=: 'int' and 'NoneType'. Vous pouvez m'expliquez ce problème ? Merci .

15/01/2016, 11h57
Tryph

le problème vient de fait que la méthode cVille.calculerDistance affiche la distance au lieu de la retourner.

ajoute la ligne suivante à la fin de la méthode pour régler le problème:

Code:

return val

Ta fonction ne retourne rien. Plus exactement, elle retourne None, d'où l'erreur.

Code:

1
2
3
 
    def calculerDistance(self, n):                                         
       return sqrt((n.posY-self.posY) ** 2 + (n.posX-self.posX) ** 2)