Trouver le plus court chemin reliant tous les noeuds d'un graphe

Signaler
Messages postés
6
Date d'inscription
samedi 21 novembre 2020
Statut
Membre
Dernière intervention
23 novembre 2020
-
Messages postés
637
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
23 novembre 2020
-
Bonjour à tous,
Je suis débutant en python et j'aimerai solliciter votre aide.
Pouvez-vous s'il vous plaît m'aider à comprendre ce que fait ce code python ligne par ligne(en le commentant par exemple)
def permutliste(seq):
"""Retourne la liste de toutes les permutations de la liste seq, qui est une suite de chiffre, mais sans les permutations symétriques ex: si on a [1,2,3] il ne donnera pas [3,2,1]
"""
p = [seq]
n = len(seq)
for k in range(0,n-1):
for i in range(0, len(p)):
z = p[i][:]
for c in range(0,n-k-1):
z.append(z.pop(k))
if (z not in p) and (z[::-1] not in p):
p.append(z[:])
return p

"""autre manière de coder les permutations : recursive"""
def permutation(seq):
n=len(seq)
if n==1:
return [seq]
else :
P=[]
for i in range(n):
A=seq[0:i]+seq[i+1:n]
P1=permutation(A)
for k in range(len(P1)):
P.append([seq[i]]+P1[k])

return P

def permieux(seq):
P = permutation(seq)
for comb in P:
if (comb[::-1] in P):
P.remove(comb[::-1])
return P

"""va tester la longueur de tous les chemins possibles et rendre le chemin pour laquelle elle est min, tous les chemins possibles sont matérialisés par toutes les permutations possibles,, on a enlever les symetries car faire le chemin dans un sens ou dans l'autre c'est la même chose"""


def pluscourtchemin(grap):
l = len(grap[0][:])
seq=[1]
while len(seq) <= l-1:
k = len(seq)
seq.append(k+1)
perm = permieux(seq)
long=0.0
res=[]
for elem in perm:
dist=0.0
for s in range(0,l-1):
x=min(elem[s],elem[s+1])
y=max(elem[s],elem[s+1])
dist = dist + grap[x-1][y-x]
if dist <= long or long==0:
long = dist
res = elem
return(res,long)



"""exemple de graphique à tester"""
gr=[[0, 2, 3, 4], [0, 8, 9], [0, 18]]

"""pour le comprendre : une liste par point : le point A (ou 1) est à une distance 0 de A, 2 de B, 3 de C et 4 de D / le point B est à une distance 0 de B, 8 de C et 9 de D...."""

print()
print(pluscourtchemin(gr))

# Autres exemples de graphes à tester
# grap=[[0, 1, 7.2, 4.1, 8, 12], [0, 3, 9, 6, 2], [0, 7, 11, 3], [0, 5, 5.2], [0, 8.1]]
# graphique= [[0,3,5,7,4,8,9,6],[0,4,8,6,9,5,7],[0,5,8,6,9,7],[0,6,7,9,8],[0,9,7,8],[0,8,9],[0,8]]
# graphique2= [[0,3,5,7,4,8,9],[0,3,5,7,4,8,],[0,4,8,5,7],[0,5,8,7],[0,6,7],[0,9]]
Je vous remercie d'avance,




Configuration: Windows / Chrome 87.0.4280.66

9 réponses

Messages postés
637
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
23 novembre 2020
79
Bonjour Jerry,

L'indentation étant importante en Python, merci de re poster ton code avec les balises de code
mode d'emploi:
https://codes-sources.commentcamarche.net/faq/11288-les-balises-de-code
Visuellement, ça doit ressembler à ceci :

def test():
    print('test')

test()
Messages postés
6
Date d'inscription
samedi 21 novembre 2020
Statut
Membre
Dernière intervention
23 novembre 2020

Bonjour,

Merci pour votre retour. Je vous remet le code avec les indentations respectées.
def permutliste(seq):
    """Retourne la liste de toutes les permutations de la liste seq, qui est une suite de chiffre, mais sans les permutations symétriques ex: si on a [1,2,3] il ne donnera pas [3,2,1]
    """
    p = [seq]
    n = len(seq)
    for k in range(0,n-1):
        for i in range(0, len(p)):
            z = p[i][:]
            for c in range(0,n-k-1):
                z.append(z.pop(k))
                if (z not in p) and (z[::-1] not in p):
                    p.append(z[:])
    return p
    
"""autre manière de coder les permutations : recursive"""
def permutation(seq):
    n=len(seq)
    if n==1:
        return [seq]
    else :
        P=[]
        for i in range(n):
            A=seq[0:i]+seq[i+1:n]
            P1=permutation(A)
            for k in range(len(P1)):
                P.append([seq[i]]+P1[k])
                
    return P

def permieux(seq):
    P = permutation(seq)
    for comb in P:
        if (comb[::-1] in P):
            P.remove(comb[::-1])
    return P

"""va tester la longueur de tous les chemins possibles et rendre le chemin pour laquelle elle est min, tous les chemins possibles sont matérialisés par toutes les permutations possibles,, on a enlever les symetries car faire le chemin dans un sens ou dans l'autre c'est la même chose"""  

  
def pluscourtchemin(grap):
    l = len(grap[0][:]) 
    seq=[1]
    while len(seq) <= l-1:
        k = len(seq)
        seq.append(k+1) 
    perm = permieux(seq) 
    long=0.0 
    res=[] 
    for elem in perm: 
        dist=0.0
        for s in range(0,l-1):
            x=min(elem[s],elem[s+1])
            y=max(elem[s],elem[s+1])
            dist = dist + grap[x-1][y-x]
        if dist <= long or long==0:
            long = dist
            res = elem
    return(res,long)
        
        
    
"""exemple de graphique à tester"""
gr=[[0, 2, 3, 4], [0, 8, 9], [0, 18]]

"""pour le comprendre : une liste par point : le point A (ou 1) est à une distance 0 de A, 2 de B, 3 de C et 4 de D / le point B est à une distance 0 de B, 8 de C et 9 de D...."""

print()
print(pluscourtchemin(gr))


# Autres exemples de graphes à tester
# grap=[[0, 1, 7.2, 4.1, 8, 12], [0, 3, 9, 6, 2], [0, 7, 11, 3], [0, 5, 5.2], [0, 8.1]]
# graphique= [[0,3,5,7,4,8,9,6],[0,4,8,6,9,5,7],[0,5,8,6,9,7],[0,6,7,9,8],[0,9,7,8],[0,8,9],[0,8]]
# graphique2= [[0,3,5,7,4,8,9],[0,3,5,7,4,8,],[0,4,8,5,7],[0,5,8,7],[0,6,7],[0,9]]
Messages postés
637
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
23 novembre 2020
79
Déjà la fonction permutliste(seq) est inutile: elle n'est pas appelée dans ce programme

Ensuite le programme affiche le plus court chemin d'un graphe (et non d'un graphique)

avec la distance : ([3, 2, 1, 4], 14.0)
Messages postés
6
Date d'inscription
samedi 21 novembre 2020
Statut
Membre
Dernière intervention
23 novembre 2020

Merci beaucoup! Oui c'est une faute de frappe on cherche justement le plus court chemin d'un graphe. Pouvez-vous s'il vous plaît m'aider à commenter ce code pour que je puisse comprendre chaque fonction( chaque ça serait encore mieux), je sais que c'est trop vous demander mais je vous remercie d'avance . Aussi les autres personnes qui lisent ce poste et qui peuvent m'aider, svp je demande votre aide.

Merci d'avance!
Messages postés
637
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
23 novembre 2020
79
Tiens, déjà, j'ai fait des modifs pour éclaircir un peu:

suppression de la fonction inutile
placement des docs de fonction à l'intérieur des fonctions (c'est logique)
aération du code
affichage plus sympa

# -*- coding:Latin-1 -*-

def permutation(seq):
    """ coder recursivement les permutations """

    n=len(seq)

    if n==1:
        return [seq]
    else :
        P=[]
        for i in range(n):
            A=seq[0:i]+seq[i+1:n]
            P1=permutation(A)
            for k in range(len(P1)):
                P.append([seq[i]]+P1[k])
                
    return P

def permieux(seq):

    P = permutation(seq)

    for comb in P:
        if (comb[::-1] in P):
            P.remove(comb[::-1])

    return P

def plus_court_chemin(graphe):
    """ teste la longueur de tous les chemins possibles et rend le chemin pour laquelle elle est min,
       tous les chemins possibles sont matérialisés par toutes les permutations possibles,
       on a enlevé les symetries car faire le chemin dans un sens ou dans l'autre c'est la même chose """

    l_graphe = len(graphe[0][:]) 
    seq=[1]

    while len(seq) <= l_graphe - 1:
        k = len(seq)
        seq.append(k+1)

    perm = permieux(seq) 
    longueur=0.0 
    res=[]

    for elem in perm: 
        dist=0.0

        for s in range(0,l_graphe - 1):
            x=min(elem[s],elem[s+1])
            y=max(elem[s],elem[s+1])
            dist = dist + graphe[x-1][y-x]

        if dist <= longueur or longueur==0:
            longueur = dist
            res = elem

    return(res,longueur)

"""exemple de graphe à tester
une liste par point : le point A (ou 1) est à une distance 0 de A,
2 de B, 3 de C et 4 de D / le point B est à une distance 0 de B, 8 de C et 9 de D... """
gr=[[0, 2, 3, 4], [0, 8, 9], [0, 18]]

resultat = plus_court_chemin(gr)
chemin, distance = resultat[0], resultat[1]
print('\nLe plus court chemin : {}, distance : {}'.format(chemin, distance))
Messages postés
6
Date d'inscription
samedi 21 novembre 2020
Statut
Membre
Dernière intervention
23 novembre 2020

Merci beaucoup pour votre contribution Phil_1857. Toutefois, mais j'ai encore du mal à comprendre par exemple(et pas que) ce que fait la boucle for dans permutation() ou dans permieux()( Je suis débutant en python et c'est super important que je comprenne le code). Pouvez-vous svp si ce n'est trop vous demandez me faire un commentaire ligne par ligne bien sûr quand cela reste possible pour vous.
Messages postés
637
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
23 novembre 2020
79
La fonction permutation trouve toutes les combinaisons possibles de la liste seq passée en argument:

seq = [1,2,3,4]
combinaisons: [1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], etc ...

permieux enlève les symétries comme [2, 3, 4, 1] qui est le même chemin que [1,4,3,2], mais dans l'autre sens

Après, pour savoir comment ça marche, il faut mettre des print() dans les fonctions pour connaitre le contenu des variables à chaque étape ...
Messages postés
637
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
23 novembre 2020
79
Bonjour Jerry,

Il y a un problème avec ton graphe gr=[[0, 2, 3, 4], [0, 8, 9], [0, 18]]

D'après les explications A est a 0 de A, 2 de B, 3 de C, etc ...

B est a 8 de C

Dans la 3eme liste, C est à 0 de C et 18 de B

Etonnant, non ? ou bien j'interprète mal le commentaire ...

Un affichage plus sympa:
chemin, distance = plus_court_chemin(gr)
print('\nLe plus court chemin :')
for el in chemin:
	print(chr(65+el-1),end = ' ')
print('\ndistance : {}'.format(distance))
Messages postés
6
Date d'inscription
samedi 21 novembre 2020
Statut
Membre
Dernière intervention
23 novembre 2020

Bonjour Phil_1857 je confirme qu'il y a un problème aussi, mais je sais pas pourquoi.
Messages postés
13226
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 novembre 2020
740
bonjour à tous,
merci de tenir compte de ceci:
https://www.commentcamarche.net/faq/10925-demander-de-l-aide-pour-vos-exercices-sur-ccm
résoudre un exercice à la place de l'étudiant ne va pas lui permettre d'apprendre et de progresser.
Messages postés
6
Date d'inscription
samedi 21 novembre 2020
Statut
Membre
Dernière intervention
23 novembre 2020

Bonjour yg_be, il ne s'agit pas de résoudre un problème à ma place mais j'ai juste demandé de l'aide parce que je ne comprend pas. Merci
Messages postés
637
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
23 novembre 2020
79
Bonjour yg_be,

Tu as raison

Mais pour l'instant, on n'a pas donné de réponse toute faite à sa question, qui était de lui commenter le code ligne par ligne

Je lui ai juste redonné son code dans une forme plus sympa, mais c'est tout ...