Python : Problème du voyageur de commerce

[invitec01a7eac]

Bonsoir!

Dans le cadre du TIPE de cette année portant sur le thème du Transport, mon groupe a choisi d'étudier le problème du voyageur de commerce. Cela consiste à, étant donné un nombre de ville, partir d'une ville et trouver le meilleur chemin qui passe une fois par toutes les autres villes et revenir à la ville de départ, le TSP en somme.
J'ai donc choisi l'heuristique gloutonne : On veut rajouter une ville C dans le chemin entre 2 villes A et B du chemin telle que, si l'on note d(X,Y) la distance de la ville X à la ville Y, le nombre d(A,C)+d(B,C)-d(A,B) soit minimal.

Mise en situation : Nous avons choisi les 20 villes les plus peuplées de France, et avec une ville choisie au hasard parmi celles-ci, nous devons trouver le chemin optimal. Ces 20 villes sont stockées dans une liste (que l'on notera M), sont numérotées et leurs coordonnées sont indiquées. Nous disposons d'un programme permettant de calculer la distance entre 2 villes.

Début : J'ai écris un programme choisissant une ville au hasard parmi les 20 villes et trouvant la ville la plus proche afin d'avoir le début du chemin. Ces 2 villes sont stockées dans une nouvelle liste, la liste des villes appartenant au chemin (que l'on notera L) et leurs coordonnées sont stockées dans une autre liste (que l'on notera N). Ces villes sont ensuite supprimées de la liste initiale (via "pop")

Ensuite, j'ai écris un programme choisissant la ville suivante selon l'heuristique gloutonne, nous permettant d'avoir le triangle de base. Cette ville et ses coordonnées sont ajoutées respectivement au liste L et N. Cette ville est aussi "pop" de la liste initiale.

Puis mon but a été de continuer sur cette voie en ajoutant les villes une par une et en les supprimant progressivement de la liste de départ. Mais j'ai des soucis quant aux "pop" et ne sait pas comment gérer les indexations des éléments de la liste.

Pourriez-vous m'aider?

PS : J'ajoute à la suite les programmes que j'ai pus écrire.
-----

[invitec01a7eac]

La liste initiale est sous la forme suivante :

[[0, 'PARIS', 'Paris', 48.857257, 2.344311],
[1, 'MARSEILLE', 'Marseille', 43.2958, 5.366067],
[2, 'LYON', 'Lyon', 45.762006, 4.832372],
[3, 'TOULOUSE', 'Toulouse', 43.606148, 1.435585],
[4, 'NICE', 'Nice', 43.712104, 7.255905],
[5, 'NANTES', 'Nantes', 47.219316, -1.556968],
[6, 'MONTPELLIER', 'Montpellier', 43.610498, 3.877936],
[7, 'STRASBOURG', 'Strasbourg', 48.574935, 7.748352],
[8, 'BORDEAUX', 'Bordeaux', 44.837663, -0.577904],
[9, 'LILLE', 'Lille', 50.62974, 3.054711],
[10, 'RENNES', 'Rennes', 48.117241, -1.677809],
[11, 'REIMS', 'Reims', 49.257329, 4.034491],
[12, 'LEHAVRE', 'Le Havre', 49.493329, 0.103028],
[13, 'SAINT-ETIENNE', 'Saint-Etienne', 45.439955, 4.389153],
[14, 'TOULON', 'Toulon', 43.124326, 5.927245],
[15, 'GRENOBLE', 'Grenoble', 45.18887, 5.727048],
[17, 'NIMES', 'Nimes', 43.833463, 4.351784],
[18, 'ANGERS', 'Angers', 47.471287, -0.551617],
[19, 'VILLEURBANNE', 'Villeurbanne', 45.771987, 4.89017]]

Les 2 villes de départ :

def choix_ville (M):            # M la liste des villes de base
    N = []                      # N la liste des coordonnées des villes appartenant au chemin
    L = []                      # L la liste des villes appartenant au chemin
    x = M.pop(randint(0,len(M)))
    L += [x[1]]
    N += [[x[3],x[4]]]
    mind = D(C((x[3],x[4])), C((M[0][3],M[0][4])))
    z = 0
    for k in range(1,len(M)):
        l = D(C((x[3],x[4])), C((M[k][3],M[k][4])))
        if l < mind :
            mind = l
            z = k
    y = M.pop(z)
    N += [[y[3],y[4]]]
    L += [y[1]]
    return N,L,M,x,y

Le triangle de base:

def triangle_base (N,L,M,x,y):
    min = D(C((N[0][0],N[0][1])), C((M[0][3],M[0][4])))
    V = M[0]
    for k in range(2):
        for l in range(k+1,len(M)):
            a = D(C((N[k][0],N[k][1])), C((M[l][3],M[l][4])))
            if a < min:
                a = min
                V = M[l]
    L += [V[1]]
    N += [[V[3],V[4]]]
    d = D(C((N[0][0],N[0][1])),C((N[1][0],N[1][1]))) + D(C((N[1][0],N[1][1])),C((N[2][0],N[2][1]))) + D(C((N[2][0],N[2][1])),C((N[0][0],N[0][1])))
    if V[0] < x[0] and V[0] < y[0]:
        M.pop(V[0])
        i = 0
    elif (V[0] < x[0] and V[0] > y[0] ) or (V[0] < x[0] and V[0] > y[0]):
        M.pop(V[0]-1)
        i = 1
    elif V[0] > x[0] and V[0] > y[0]:
        M.pop(V[0]-2)
        i = 2
    print(M)
    return N,L,M,i

Le reste :

def chemin_definitif (N,L,M):
    distancetot = D(C(N[0]),C(N[1])) + D(C(N[1]),C(N[2]) ) + D(C(N[2]),C(N[0]))
    min = D(C(N[0]),C((M[0][3],M[0][4]))) + D(C(N[1]),C((M[0][3],M[0][4]))) - D(C(N[0]),C(N[1]))
    VA = M[0]
    L1 = []   
    L2 = []
    N1 = []
    N2 = []
    for e in range (len(M)):
        for k in range (3,len(N)-1):
            for l in range (k+1,len(M)):
                a = D(C(N[k]),C((M[l][3],M[l][4])))
                b = D(C(N[k+1]),C((M[l][3],M[l][4])))
                c = D(C(N[k]),C(N[k+1]))
                z = a+b-c
                if z <= min :
                    min = z
                    VA = M[l]
                    L1 = [L[x] for x in range (k)]
                    L2 = [L[x] for x in range (k,len(L))]
                    N1 = [N[x] for x in range (k)]
                    N2 = [N[x] for x in range (k,len(L))]
        distancetot += min
        L = L1 + [VA[1]] + L2
        N = N1 + [[VA[3],VA[4]]] + N2
        M.pop(VA[0])
    return distancetot,N,L,M

Devrais-je supprimer "triangle_base" vu que c'est le même principe sur toute la suite?

[CM63]

Bonjour,

Tu as bien présenté ton problème et exposé quelle était ta difficulté. Si je comprends bien , il faut que nous développions cette phrase:

Mais j'ai des soucis quant aux "pop" et ne sait pas comment gérer les indexations des éléments de la liste.

Est-ce que cela veut dire : je voudrais pouvoir calculer l'indice d'un élément de tableau, connaissant le nombre de "pop" que j'ai fait dans ce tableau?
Si c'est bien cela, peux-tu nous donnez un exemple où tu rencontres ce problème et peut-être que nous verrons un moyen de faire autrement: peut-être qu'il n'est pas nécessaire de calculer l'indice.

Oups, je viens de poster, et là, je n'ai pas le temps de lire le deuxième message, mille excuses.

[invitec01a7eac]

Alors le soucis que j'ai est que rien que pour le triangle de base, la ville à ajouter appelle 3 cas différents :
- l'indice de la ville est compris entre les indices des 2 villes du chemin initial
- Cet indice est plus petit que les 2 indices
- Cet indice est plus grand que les 2 indices

Avec ce soucis, je me vois mal écrire un code lisible pour la suite du chemin, sachant qu'à chaque itération il y aura une disjonction de cas, ce qui rend le problème infernal.
Devrais-je sinon utiliser une approche différente?

[A voir en vidéo sur Futura]

[CM63]

Désolé, la complexité du problème me dépasse un peu, mais à ta place au lieu d'utiliser des listes de listes, j'utiliserais une liste d'objet, et chaque objet aurait les données membres : nom, distance, deuxième nombre (je ne sais pas ce que c'est) et pour paris, ce serait nom="Paris",distance=48.857257 , autre_val=2.344311

Ce serait déjà plus clair, mais sais-tu utiliser les classes?

Je ne sais pas quel est le cadre de tes études. Si le cadre est plutôt informatique, et que le but du TIPE est d'être à l'aise avec les listes, évidemment tu n'as pas le choix. Mais si le cadre est tel que l'informatique n'est qu'un outil, dans ce cas ce serait mieux d'utiliser une liste d'objets avec une classe Ville et des données membres. Je ne sais pas si tu as vu les classes.

J'entrevoie le problème: il faudrait pouvoir placer un élément dans une liste, selon qu'il doit être au milieu de la liste, ou avant le premier élément, ou après le dernier, et ce, de façon récursive. Mais dans ce cas, ne serait-il pas possible de calculer une fonction "coût" pour tous les éléments, puis de classer la liste par coût croissant?

[invitec01a7eac]

J'avais déjà des doutes quant à la complexité de mon programme, et j'ai l'impression que l'approche que j'ai choisie n'est pas la bonne.
Cependant il ne m'a pas semblé avoir étudié les classes ni les objets. Dans le cadre du programme, nous n'avons vu que les listes (d'aussi loin que je me souvienne).
Malheureusement, je ne pense pas être assez à l'aise avec la récursivité pour écrire ce programme récursivement.

[Ikhar84]

Si mes yeux ne sont pas trop fatigués, les deux nombres représentent la latitude et la longitude de chaque ville.

Avant de pouvoir parler "plus court chemin", il va falloir calculer une distance "en vol d'oiseau" entre deux villes choisies à partir de leur coordonnées. En tenant compte du rayon moyen de la Terre.

Je pense que avant d'aller plus loin, il faudrait déjà bien définir les données et les attendus exactes, présenté comme ça cela me semble bien plus complexe que ça en a l'air de prime abord...

Pour ce qui est de l'algo, classiquement, Dijkstra est pas mal à mon avis, avez vous essayé de le comprendre ?

Ensuite ce n'est plus "qu'un" calcul de matrices.

Désolé si HS, trop fatigué pour lire le code donné et de toute façon pas un pythonien...

Edit:
Voilà un pdf corrigé de l'algo de Djikstra en python, si ça peut aider à la reflexion...

[polo974]

Si mes yeux ne sont pas trop fatigués, les deux nombres représentent la latitude et la longitude de chaque ville.

Avant de pouvoir parler "plus court chemin", il va falloir calculer une distance "en vol d'oiseau" entre deux villes choisies à partir de leur coordonnées. En tenant compte du rayon moyen de la Terre.
...

Inutile de tenir compte du rayon de la terre, un rayon de 1 est suffisant (éviter les rayons négatifs quand même ).

Sinon, donner des vrais noms aux variables, c'est quand même plus lisible.

Enfin, utiliser des dictionnaires ou des objets permet aussi de donner des noms plutôt que des indices de listes au variables, car franchement:

    d = D(C((N[0][0],N[0][1])),C((N[1][0],N[1][1]))) + D(C((N[1][0],N[1][1])),C((N[2][0],N[2][1]))) + D(C((N[2][0],N[2][1])),C((N[0][0],N[0][1])))

ça pique grave les yeux...

Par ailleurs, tu sépares trop tes données:
L et N contiennent (apparemment) les données différentes des villes dans le même ordre (L[1] est le nom de la ville de coordonnées N[1]...
et si D() est bien la fonction de calcul de distance, il est évident que tu ne payes pas 1 euro à chaque fois que tu appelles cette fonction...

un tableau des distances permettrait de disposer de celles-ci (tableau dont la diagonale est tout à 0 et dont x[a][b] = x[b][a])...

[CM63]

Oui, Polo974 a raison, tu devrais utiliser des noms de variables plutôt que des positions dans des tableaux, c'est plus parlant, c'est pour cela que je parlais de classes, mais le passage par les classes n'est pas obligatoire.
Effectivement, pour les calculs de distance, il n'est pas nécessaire de tenir compte de la rotondité de la terre, tu peux travailler dans le plan, pour des distances en France (et dans ce cas le rayon est non pas 1 mais l'infini).
Sinon, effectivement, les distances tu peux les mettre dans un tableau à deux indices, tu ne remplis que la partie triangulaire supérieure, en face ce sont les mêmes valeurs.

[invitec01a7eac]

Bonsoir, tout d'abord merci de vos réponses, et veuillez excuser mon absence, cela fait quelques jours que j'ai attrapé la grippe.

Mes camarades m'ont également suggéré de donner des noms aux variables pour de la visibilité, mais j'ai pensé que le programme serait un poil long dans ce cas. Je vais le faire quand je le pourrai.

Ensuite, nous avons écris des programmes permettant de calculer les distances en tenant compte de la rotondité de la Terre, les voici :

def conversion_radians(coordonnees ):
return (((coordonnees[0]*pi) / 180), ((coordonnees[1]*pi) / 180))

def distance_gps(a, b):
rayon_terre = 6378137
angle = acos(sin(a[0])*sin(b[0]) + cos(a[0])*cos(b[0])*cos(abs(b[1]-a[1])))
return (angle*rayon_terre)*(10**-3)

Donc me conseilleriez-vous d'opter pour l'algorithme de Djikstra et d'utiliser un tableau stockant les distances pour une complexité optimale?