Seance 6 Dijkstra 1 Recapforcebrute Corrige

Mini- projet : algorithmes de parcours de graphes pondérés¶

1ème partie: à la recherche du plus court chemin¶

VERSION corrigée

Séance 6 (1/2) — Graphes pondérés et algorithme de Dijkstra : recap force brute¶

Jusqu'ici, nos graphes indiquaient seulement l'existence d'un lien entre deux individus (Séances 2 et 3). Mais en sociologie, toutes les relations ne se valent pas : deux personnes peuvent se croiser une fois par an ou se parler tous les jours. On peut représenter cette intensité par un poids sur chaque arête (voir FONDAMENTAUX.md, §2.3) — par exemple le temps qu'il faut pour transmettre une information d'une personne à l'autre, ou l'inverse de la fréquence de contact.

Question sociologique posée par cette séance : dans un réseau où chaque lien a un coût (temps, distance, effort), quel est le chemin le moins coûteux entre deux individus ? C'est exactement le problème que résout l'algorithme de Dijkstra, que nous découvrirons juste après cette activité de recap (méthode "force brute").

L'exercice ci-dessous l'illustre sur un cas logistique concret (circuits courts en Bretagne) : le raisonnement — trouver le chemin de poids minimal dans un graphe pondéré — est rigoureusement le même que pour calculer, par exemple, le canal de diffusion le plus rapide d'une information dans un réseau social pondéré par la force des liens.

Pour aller plus loin : la preuve formelle de l'algorithme de Dijkstra (terminaison, invariant de boucle) et l'analyse de sa complexité sont regroupées dans une annexe optionnelle (Annexe_Dijkstra_Preuve_Complexite_Corrige.ipynb), à explorer si vous êtes à l'aise et que le temps le permet.

Introduction¶

Lors de cette activité, vous allez travailler sur un algorithme permettant la détermination du chemin le plus court entre deux points d'un graphe. Vous allez réinvestir vos notions de programmation et d'algorithme (définition, correction et optimisation).

Énoncé¶

Un site web propose une plateforme reliant producteurs et consommateurs en Bretagne. Leur objectif étant de proposer des circuits courts et ainsi de contribuer au développement écologique et économique de la région. Afin d’aider les consommateurs a préparer leurs courses, les responsables du site web souhaitent développer un algorithme qui optimise leur trajet pour l’achat des différent vivres. En cochant les cases des produits que le consommateur souhaite acheter (fruits, légumes, produits carnés, produits laitiers, produits de la pêche,…) l’algorithme proposera le chemin le plus court pour faire l’ensemble des achats. Regardons l’exemple ci-dessous :

Question 1¶

Rechercher le chemin le plus court entre le point A et le point G. Notez les différentes étapes, ainsi que la distance parcouru en total.

Réponse 1¶

Le chemin le plus court entre le point A et le point G est A,C,D,G, la distance parcouru est de 9

On représente ce graphe dans un premier temps sous forme de tableau:

	A	B	C	D	E	F	G	H
A	0	4	2	-	-	-	-	-
B	4	0	6	-	5	-	-	-
C	2	6	0	3	-	-	-	5
D	-	-	3	0	-	3	4	1
E	-	5	-	-	0	2	-	-
F	-	-	-	3	2	0	7	-
G	-	-	-	4	-	7	0	10
H	-	-	5	1	-	-	10	0

Puis on décide de modéliser ce graphe sous Python à l'aide d'une liste de listes:

In [2]:

# Déclaration de notre graphe sous forme de liste de liste
graphe = [
    [0 ,4 ,2 ,99,99,99,99,99],
    [4 ,0 ,6 ,99,5 ,99,99,99],
    [2 ,6 ,0 ,3 ,99,99,5 ,99],
    [99,99,3 ,0 ,99,3 ,4 ,1 ],
    [99,5 ,99,99,0 ,2 ,99,99],
    [99,99,99,3 ,2 ,0 ,7 ,99],
    [99,99,99,4 ,99,7 ,0 ,10],
    [99,99,5 ,1 ,99,99,10,0 ]
]

graphe # Vérification de notre sortie

# Déclaration de notre graphe sous forme de liste de liste graphe = [ [0 ,4 ,2 ,99,99,99,99,99], [4 ,0 ,6 ,99,5 ,99,99,99], [2 ,6 ,0 ,3 ,99,99,5 ,99], [99,99,3 ,0 ,99,3 ,4 ,1 ], [99,5 ,99,99,0 ,2 ,99,99], [99,99,99,3 ,2 ,0 ,7 ,99], [99,99,99,4 ,99,7 ,0 ,10], [99,99,5 ,1 ,99,99,10,0 ] ] graphe # Vérification de notre sortie

Out[2]:

Question 2:¶

1. Quel choix a fait le développeur pour indiquer la non existence d'un arc entre deux sommets ?
2. Ce choix vous semble t-il judicieux ? Argumentez.
3. Que proposeriez-vous au développeur ?

Réponse 2¶

1. Le développeur a choisi d'utiliser le nombre 99 pour indiquer la non existence d'un arc entre deux sommets.
2. Dans le contexte de ce graphe ce choix peut être défendu, car la somme de toutes les distances de ce graphe ne dépasse pas 52. Le choix de ce codage "en dur" empêche toutefois l'évolution du programme vers des graphes plus étendues.
3. Le développeur pourrait calculer la somme des distances de l'ensemble du graphe et l'utiliser cette valeur pour indiquer qu'aucun arc n'existe.

Calcul de la distance entre deux sommets¶

Le calcul de la distance entre deux noeuds se fait à l'aide d'une fonction intitulé distance dont le code est donne ci dessous:

In [3]:

def distance(départ, arrivée) -> int:
    # on vérifie que les valeurs de départ et arrivée sont bien des entiers
    assert type(départ) == int, "la valeur départ n'est pas un entier"
    assert type(arrivée) == int, "la valeur départ n'est pas un entier"
    assert graphe[départ][arrivée] != 99, "les noeuds ne sont pas adjacent"
 
    return(graphe[départ][arrivée])

def distance(départ, arrivée) -> int: # on vérifie que les valeurs de départ et arrivée sont bien des entiers assert type(départ) == int, "la valeur départ n'est pas un entier" assert type(arrivée) == int, "la valeur départ n'est pas un entier" assert graphe[départ][arrivée] != 99, "les noeuds ne sont pas adjacent" return(graphe[départ][arrivée])

Question 3¶

1. Que renvoie l'instruction $distance(2,3)$ ?
2. 6
3. "La valeur n'est pas un entier"
4. 3
5. 99
6. Démonstration de la correction de cette fonction.

• Dans un premier temps montrez que la fonction se termine (pour rappel cela consiste a verifier que les calculs effectuées par l'algorithme s'arretent bien):

1. Il n'y a aucune boucle dans la fonction, elle se termine forcément
2. La fonction ne vérifie pas tout les cas possibles, elle ne se termine jamais dans certains cas
3. Une fonction ne se termine que lorsqu'il y a une boucle "while"

• Dans un deuxieme temps montrer la correction partielle (pour rappel: l'algorithme donne bien le bon résultat)

1. Pour chaque couple de sommets la fonction retourne bien la distance demandée
2. Le développeur n'a pas prévu le cas où l'on passe le même sommet en arrivée et départ
3. L'algorithme ne donne pas le bon résultat.
4. Quel est le niveau de complexité de cette fonction ?
5. Il s'agit du parcours séquentiel d'un tableau, $n \log(n)$
6. $1$
7. $n^2$
8. $0$

Réponse 3¶

1. (C) L'instruction $distance(2,3)$ renvoie la valeur 3. Il s'agit de la valeur dans la troisième ligne, quatrième colonne.
2. (A) La fonction se termine car il n'y a aucune boucle dans la fonction, elle se termine forcément par le renvoi d'une valeur ou d'un message d'erreur. Comme il s'agit d'un simple renvoi d'une valeur dans la liste de listes, la fonction retournera le bon résultat.
3. (B) Le niveau de complexité de cette fonction est de 1, il s'agit d'un simple renvoi de valeur.

Création d'une liste de sommets adjacents¶

Maintenant que nous savons déterminer la distance entre deux noeuds, on a besoin de connaitre les différents parcours entre un point de départ et un point d'arrivée. On crée d'abord une fonction qui retourne la liste des noeuds adjacents par rapport à un noeud de référence.

In [4]:

def determine_adjacents(sommet) -> list:
    #************************************************************************
    # A partir d'un noeud en entrée, la fonction donne la liste des noeuds adjacents
    # Entrée : Le noeud de départ
    # Sortie : la liste des noeuds adjacents
    #************************************************************************
    # On sélectionne la ligne contenant les noeuds adjacent par rapport a notre point de départ
    ligne = graphe[sommet]

    # on détermine le nombre de noeuds adjacents pour ce point
    nb_adjacent = len(ligne)-ligne.count(99)-ligne.count(0)

     # Puis on crée la variable parcours sous forme de liste de listes
    liste_adjacents = [[] for i in range(0,nb_adjacent)]

    a = 0
    for i in range(0,len(ligne)):
        if (ligne[i] != 0 and ligne[i] != 99):
            liste_adjacents[a].append(sommet)
            liste_adjacents[a].append(i)
            a += 1
            
    # On retourne la liste des sommet adjacents
    return(liste_adjacents)

#****************************************************************************
# Proposition de code dans le cadre de la correction

for i in range (0,len(graphe)):
    adjacents = determine_adjacents(i)
    print("Les sommets adjacents au sommet", chr(65+i), "sont :")
    for j in range(0,len(adjacents)):
        print(chr(adjacents[j][0]+65),",",chr(adjacents[j][1]+65))

def determine_adjacents(sommet) -> list: #************************************************************************ # A partir d'un noeud en entrée, la fonction donne la liste des noeuds adjacents # Entrée : Le noeud de départ # Sortie : la liste des noeuds adjacents #************************************************************************ # On sélectionne la ligne contenant les noeuds adjacent par rapport a notre point de départ ligne = graphe[sommet] # on détermine le nombre de noeuds adjacents pour ce point nb_adjacent = len(ligne)-ligne.count(99)-ligne.count(0) # Puis on crée la variable parcours sous forme de liste de listes liste_adjacents = [[] for i in range(0,nb_adjacent)] a = 0 for i in range(0,len(ligne)): if (ligne[i] != 0 and ligne[i] != 99): liste_adjacents[a].append(sommet) liste_adjacents[a].append(i) a += 1 # On retourne la liste des sommet adjacents return(liste_adjacents) #**************************************************************************** # Proposition de code dans le cadre de la correction for i in range (0,len(graphe)): adjacents = determine_adjacents(i) print("Les sommets adjacents au sommet", chr(65+i), "sont :") for j in range(0,len(adjacents)): print(chr(adjacents[j][0]+65),",",chr(adjacents[j][1]+65))

Les sommets adjacents au sommet A sont :
A , B
A , C
Les sommets adjacents au sommet B sont :
B , A
B , C
B , E
Les sommets adjacents au sommet C sont :
C , A
C , B
C , D
C , G
Les sommets adjacents au sommet D sont :
D , C
D , F
D , G
D , H
Les sommets adjacents au sommet E sont :
E , B
E , F
Les sommets adjacents au sommet F sont :
F , D
F , E
F , G
Les sommets adjacents au sommet G sont :
G , D
G , F
G , H
Les sommets adjacents au sommet H sont :
H , C
H , D
H , G

Question 4¶

1. Faites fonctionner la fonction $determine\_adjacents$ pour l'ensemble des sommets du graphe, imprimez le résultat.
2. Vérifier qu'il n'y ait pas d'erreur dans la transcription du graphe. Le corriger le cas échéant.

Réponse 4¶

1. Le code est rajouté ci dessus
2. L'impression des sommets adjacents au sommet C indique une erreur. En effet, sur le graphe, les sommets C et G ne sont pas adjacents. En vérifiant la définition de graphe on remarque en troisième liste une inversion des deux dernieres valeurs par rapport à la matrice initiale de l'énoncé. On l'a corrigée dans le programme principal ci-dessous.

Composition d'une liste de listes avec l'ensemble des chemins possibles entre un point de départ et un point d'arrivée.¶

Pour commencer cet exercice, nous allons d'abord nous intéresser au nombre de noeuds adjacents par rapport à notre point de départ, puis, à partir de cette liste, nous allons bâtir l'ensemble des chemins possibles.

In [4]:

def recursive2(liste) -> list:
    #************************************************************************
    # La fonction récursive établit la liste exhaustive des chemins possibles
    # Entrée : La liste de chemins déja établie
    # Sortie : la liste de chemins jusqu'au noeuds suivants
    #************************************************************************
   
    sommets_adjacents = []
    # On détermine le nombre d'arcs adjacents aux noeuds
    for i in range(0,len(liste)):                         # on boucle dans notre liste existante
        for element in determine_adjacents(liste[i][-1]): # pour chaque sommet dans la liste des adjacents
            if element not in sommets_adjacents:          # si le sommet n'est pas encore dans notre liste
                 sommets_adjacents.append(element)        # alors on le rajoute
   
    # On identifie les chemins qu'on doit créer, en ignorant les chemins:
        # - où on revient sur un noeud déja visité
        # - déja existant dans la liste
        # Puis on renseigne les chemins possibles

    entrees_a_supprimer = []                              # On va garder en mémoire les entrées a supprimer
    for i in range(0,len(liste)) :                        # on boucle dans notre liste existante
        if liste[i][-1] != arrivée:                       # on ignore les chemins menant déja au point d'arrivée
            for j in range(0,len(sommets_adjacents)):     # on boucle dans la liste qu'on vient d'obtenir
                if (sommets_adjacents[j][0] == liste[i][-1] and
                    sommets_adjacents[j][-1] != liste[i][0] and
                    sommets_adjacents[j][-1] not in liste[i]
                    ):
                    liste.append(liste[i] + sommets_adjacents[j][1:len(sommets_adjacents)])
            entrees_a_supprimer.append(i)                 # On va garder en mémoire les entrées a supprimer
            
    for i in range(0,len(entrees_a_supprimer)):           # avant de retourner notre résultat on supprime les entrées superflus
        del liste[entrees_a_supprimer[i]-i]
    return(liste)

def recursive2(liste) -> list: #************************************************************************ # La fonction récursive établit la liste exhaustive des chemins possibles # Entrée : La liste de chemins déja établie # Sortie : la liste de chemins jusqu'au noeuds suivants #************************************************************************ sommets_adjacents = [] # On détermine le nombre d'arcs adjacents aux noeuds for i in range(0,len(liste)): # on boucle dans notre liste existante for element in determine_adjacents(liste[i][-1]): # pour chaque sommet dans la liste des adjacents if element not in sommets_adjacents: # si le sommet n'est pas encore dans notre liste sommets_adjacents.append(element) # alors on le rajoute # On identifie les chemins qu'on doit créer, en ignorant les chemins: # - où on revient sur un noeud déja visité # - déja existant dans la liste # Puis on renseigne les chemins possibles entrees_a_supprimer = [] # On va garder en mémoire les entrées a supprimer for i in range(0,len(liste)) : # on boucle dans notre liste existante if liste[i][-1] != arrivée: # on ignore les chemins menant déja au point d'arrivée for j in range(0,len(sommets_adjacents)): # on boucle dans la liste qu'on vient d'obtenir if (sommets_adjacents[j][0] == liste[i][-1] and sommets_adjacents[j][-1] != liste[i][0] and sommets_adjacents[j][-1] not in liste[i] ): liste.append(liste[i] + sommets_adjacents[j][1:len(sommets_adjacents)]) entrees_a_supprimer.append(i) # On va garder en mémoire les entrées a supprimer for i in range(0,len(entrees_a_supprimer)): # avant de retourner notre résultat on supprime les entrées superflus del liste[entrees_a_supprimer[i]-i] return(liste)

Question 5¶

En étudiant la fonction $recursive2$ ci-dessus, répondez aux questions suivantes:

1. Identifier la ligne de code qui ajoute les chemins possible a la liste.
2. Ecrivez le commentaire de cette ligne de code en langage naturel ou pseudocode.
3. Quel est le coût de cette fonction ?
4. Il s'agit du parcours séquentiel d'un tableau, le coût est linéaire ;
5. Il s'agit d'un tri par insertion, au pire le coût de cette fonction est quadratique ($n^2$) ;
6. Il s'agit d'un succession d'instructions simple, le cout est de 1.

Réponse 5¶

1. la ligne liste.append(liste[i] + sommets_adjacents[j][1:len(sommets_adjacents)]) permet l'ajout des chemins possibles
2. On rajoute à notre liste l'index actuel + le sommet adjacent
3. (A) Il s'agit du parcours séquentiel d'un tableau, le coût est linéaire et dépend de la taille de la liste passée en entrée;

Programme principal¶

In [1]:

#************************************************************************
# Transcription du graphe sous forme de liste de listes
#************************************************************************

graphe = [
    [0 ,4 ,2 ,99,99,99,99,99],
    [4 ,0 ,6 ,99,5 ,99,99,99],
    [2 ,6 ,0 ,3 ,99,99,99,5 ],
    [99,99,3 ,0 ,99,3 ,4 ,1 ],
    [99,5 ,99,99,0 ,2 ,99,99],
    [99,99,99,3 ,2 ,0 ,7 ,99],
    [99,99,99,4 ,99,7 ,0 ,10],
    [99,99,5 ,1 ,99,99,10,0 ]
    ]

def distance(Noeud_A, Noeud_B) -> int:
    #************************************************************************
    # Donne la distance entre deux noeuds adjacents Noeud_A et Noeud_B
    # Entrée : Le noeud de départ
    # Sortie : la liste des noeuds adjacents
    #************************************************************************
    # on vérifie que les valeurs de départ et arrivée sont bien des entiers
    assert type(Noeud_A) == int, "la valeur départ n'est pas un entier"
    assert type(Noeud_B) == int, "la valeur départ n'est pas un entier"
    assert graphe[Noeud_A][Noeud_B] != 99, "les noeuds ne sont pas adjacent"
    
    # On retourne la distance entre les deux noeuds
    return(graphe[Noeud_A][Noeud_B])


def determine_adjacents(noeud) -> list:
    #************************************************************************
    # A partir d'un noeud en entrée, la fonction donne la liste des noeuds adjacents
    # Entrée : Le noeud de départ
    # Sortie : la liste des noeuds adjacents
    #************************************************************************
    # On sélectionne la ligne contenant les noeuds adjacent par rapport a notre point de départ
    ligne = graphe[noeud]

    # on détermine le nombre de noeuds adjacents pour ce point
    nb_adjacent = len(ligne)-ligne.count(99)-ligne.count(0)

     # Puis on crée la variable parcours sous forme de liste de listes
    liste_adjacents = [[] for i in range(0,nb_adjacent)]

    a = 0
    for i in range(0,len(ligne)):
        if (ligne[i] != 0 and ligne[i] != 99):
            liste_adjacents[a].append(noeud)
            liste_adjacents[a].append(i)
            a += 1
            
    # On retourne la liste des noeuds adjacents
    return(liste_adjacents)

def recursive2(liste) -> list:
    #************************************************************************
    # La fonction récursive établit la liste exhaustive des chemins possibles
    # Entrée : La liste de chemins déja établie
    # Sortie : la liste de chemins jusqu'au noeuds suivants
    #************************************************************************
   
    sommets_adjacents = []
    # On détermine le nombre d'arcs adjacents aux noeuds
    for i in range(0,len(liste)): # on boucle dans notre liste existante
        for element in determine_adjacents(liste[i][-1]): # pour chaque sommet dans la liste des adjacents
            if element not in sommets_adjacents:          # si le sommets n'est pas encore dans notre liste
                 sommets_adjacents.append(element)        # alors on le rajoute
   
    # On identifie les chemins qu'on doit créer, en ignorant les chemins:
        # - où on revient sur un noeud déja visité
        # - déja existant dans la liste
        # Puis on renseigne les chemins possibles

    entrees_a_supprimer = []                              # On va garder en mémoire les entrées a supprimer
    for i in range(0,len(liste)) :                        # on boucle dans notre liste existante
        if liste[i][-1] != arrivée:                       # on ignore les chemins menant déja au point d'arrivée
            for j in range(0,len(sommets_adjacents)):     # on boucle dans la liste qu'on vient d'obtenir
                if (sommets_adjacents[j][0] == liste[i][-1] and
                    sommets_adjacents[j][-1] != liste[i][0] and
                    sommets_adjacents[j][-1] not in liste[i]
                    ):
                    liste.append(liste[i] + sommets_adjacents[j][1:len(sommets_adjacents)])
            entrees_a_supprimer.append(i)                 # On va garder en mémoire les entrées a supprimer
            
    for i in range(0,len(entrees_a_supprimer)):           # avant de retourner notre résultat on supprime les entrées superflus
        del liste[entrees_a_supprimer[i]-i]
    return(liste)


#********************************************************************************
# Début du programme principal
#********************************************************************************

# on définit un point de départ et d'arrivée
départ = 0
arrivée = 6


# On détermine le nombre d'arcs partant de notre sommet départ
liste_arcs_départs = determine_adjacents(départ)


# Construction de la liste de chemins possibles
for i in range(0,len(graphe)):
    liste_arcs_départs = recursive2(liste_arcs_départs)

# On imprime le nombre de chemins et les chemins possibles
print("Il y a",len(liste_arcs_départs),"chemins possibles:",liste_arcs_départs)

# On identifie le chemin le plus court
this_distance = 0
court_distance = 9999
court_chemin =[]

for element in liste_arcs_départs:
    this_distance = 0
    for i in range(0,len(element)-1):
        this_distance += distance(element[i],element[i+1])
    if this_distance < court_distance:
        court_distance = this_distance
        court_chemin = element
        
# Ecrivez votre réponse à la question 6.1 ici
print("Le chemin le plus court est:", court_chemin)
print("La distance a parcourir est:", court_distance)

#************************************************************************ # Transcription du graphe sous forme de liste de listes #************************************************************************ graphe = [ [0 ,4 ,2 ,99,99,99,99,99], [4 ,0 ,6 ,99,5 ,99,99,99], [2 ,6 ,0 ,3 ,99,99,99,5 ], [99,99,3 ,0 ,99,3 ,4 ,1 ], [99,5 ,99,99,0 ,2 ,99,99], [99,99,99,3 ,2 ,0 ,7 ,99], [99,99,99,4 ,99,7 ,0 ,10], [99,99,5 ,1 ,99,99,10,0 ] ] def distance(Noeud_A, Noeud_B) -> int: #************************************************************************ # Donne la distance entre deux noeuds adjacents Noeud_A et Noeud_B # Entrée : Le noeud de départ # Sortie : la liste des noeuds adjacents #************************************************************************ # on vérifie que les valeurs de départ et arrivée sont bien des entiers assert type(Noeud_A) == int, "la valeur départ n'est pas un entier" assert type(Noeud_B) == int, "la valeur départ n'est pas un entier" assert graphe[Noeud_A][Noeud_B] != 99, "les noeuds ne sont pas adjacent" # On retourne la distance entre les deux noeuds return(graphe[Noeud_A][Noeud_B]) def determine_adjacents(noeud) -> list: #************************************************************************ # A partir d'un noeud en entrée, la fonction donne la liste des noeuds adjacents # Entrée : Le noeud de départ # Sortie : la liste des noeuds adjacents #************************************************************************ # On sélectionne la ligne contenant les noeuds adjacent par rapport a notre point de départ ligne = graphe[noeud] # on détermine le nombre de noeuds adjacents pour ce point nb_adjacent = len(ligne)-ligne.count(99)-ligne.count(0) # Puis on crée la variable parcours sous forme de liste de listes liste_adjacents = [[] for i in range(0,nb_adjacent)] a = 0 for i in range(0,len(ligne)): if (ligne[i] != 0 and ligne[i] != 99): liste_adjacents[a].append(noeud) liste_adjacents[a].append(i) a += 1 # On retourne la liste des noeuds adjacents return(liste_adjacents) def recursive2(liste) -> list: #************************************************************************ # La fonction récursive établit la liste exhaustive des chemins possibles # Entrée : La liste de chemins déja établie # Sortie : la liste de chemins jusqu'au noeuds suivants #************************************************************************ sommets_adjacents = [] # On détermine le nombre d'arcs adjacents aux noeuds for i in range(0,len(liste)): # on boucle dans notre liste existante for element in determine_adjacents(liste[i][-1]): # pour chaque sommet dans la liste des adjacents if element not in sommets_adjacents: # si le sommets n'est pas encore dans notre liste sommets_adjacents.append(element) # alors on le rajoute # On identifie les chemins qu'on doit créer, en ignorant les chemins: # - où on revient sur un noeud déja visité # - déja existant dans la liste # Puis on renseigne les chemins possibles entrees_a_supprimer = [] # On va garder en mémoire les entrées a supprimer for i in range(0,len(liste)) : # on boucle dans notre liste existante if liste[i][-1] != arrivée: # on ignore les chemins menant déja au point d'arrivée for j in range(0,len(sommets_adjacents)): # on boucle dans la liste qu'on vient d'obtenir if (sommets_adjacents[j][0] == liste[i][-1] and sommets_adjacents[j][-1] != liste[i][0] and sommets_adjacents[j][-1] not in liste[i] ): liste.append(liste[i] + sommets_adjacents[j][1:len(sommets_adjacents)]) entrees_a_supprimer.append(i) # On va garder en mémoire les entrées a supprimer for i in range(0,len(entrees_a_supprimer)): # avant de retourner notre résultat on supprime les entrées superflus del liste[entrees_a_supprimer[i]-i] return(liste) #******************************************************************************** # Début du programme principal #******************************************************************************** # on définit un point de départ et d'arrivée départ = 0 arrivée = 6 # On détermine le nombre d'arcs partant de notre sommet départ liste_arcs_départs = determine_adjacents(départ) # Construction de la liste de chemins possibles for i in range(0,len(graphe)): liste_arcs_départs = recursive2(liste_arcs_départs) # On imprime le nombre de chemins et les chemins possibles print("Il y a",len(liste_arcs_départs),"chemins possibles:",liste_arcs_départs) # On identifie le chemin le plus court this_distance = 0 court_distance = 9999 court_chemin =[] for element in liste_arcs_départs: this_distance = 0 for i in range(0,len(element)-1): this_distance += distance(element[i],element[i+1]) if this_distance < court_distance: court_distance = this_distance court_chemin = element # Ecrivez votre réponse à la question 6.1 ici print("Le chemin le plus court est:", court_chemin) print("La distance a parcourir est:", court_distance)

Il y a 19 chemins possibles: [[0, 2, 3, 6], [0, 2, 7, 6], [0, 1, 2, 3, 6], [0, 1, 2, 7, 6], [0, 1, 4, 5, 6], [0, 2, 3, 5, 6], [0, 2, 3, 7, 6], [0, 2, 7, 3, 6], [0, 1, 2, 3, 5, 6], [0, 1, 2, 3, 7, 6], [0, 1, 2, 7, 3, 6], [0, 1, 4, 5, 3, 6], [0, 2, 1, 4, 5, 6], [0, 2, 7, 3, 5, 6], [0, 1, 2, 7, 3, 5, 6], [0, 1, 4, 5, 3, 7, 6], [0, 2, 1, 4, 5, 3, 6], [0, 1, 4, 5, 3, 2, 7, 6], [0, 2, 1, 4, 5, 3, 7, 6]]
Le chemin le plus court est: [0, 2, 3, 6]
La distance a parcourir est: 9

Question 6¶

1. Le programme ci dessous n'affiche pas le résultat attendu. Modifiez le pour qu'on vous affiche le chemin le plus court, et la distance à parcourir. (Il n'est pas attendu d'afficher le résultat sous la forme A,B,C, vous pouvez utiliser les valeurs numériques.)
2. Implementez la fonction $timeit$ et $memit$ afin de connaître le temps d'exécution et la mémoire occupé par la fonction "recursive2"
3. Est-ce que les résultats confirment votre réponse à la question 5.3 ?

Réponse 6¶

1. Le programme est modifié pour afficher le chemin le plus court et la distance parcouru
2. Les fonctions timeit et memit sont implémentés ci dessous
3. Le temps nécessaire à l'exécution ne varie que légèrement en fonction de la taille de la liste, il s'agit donc bien d'une complexité linéaire.

In [6]:

pip install memory_profiler

pip install memory_profiler

Collecting memory_profiler
  Downloading memory_profiler-0.58.0.tar.gz (36 kB)
Collecting psutil
  Downloading psutil-5.8.0-cp37-cp37m-win_amd64.whl (244 kB)
Installing collected packages: psutil, memory-profiler
    Running setup.py install for memory-profiler: started
    Running setup.py install for memory-profiler: finished with status 'done'
Successfully installed memory-profiler-0.58.0 psutil-5.8.0
Note: you may need to restart the kernel to use updated packages.

WARNING: You are using pip version 20.0.2; however, version 21.0.1 is available.
You should consider upgrading via the 'C:\EduPython666\App\Python\python.exe -m pip install --upgrade pip' command.

In [7]:

%load_ext memory_profiler

%load_ext memory_profiler

In [8]:

# Déclaration des variables en fonction des itérations (1, 3 et 5)
chemins_it1 = [[0, 1], [0, 2]]
chemins_it3 = [[0, 1, 2, 3], [0, 1, 2, 7], [0, 1, 4, 5], [0, 2, 1, 4], [0, 2, 3, 5], [0, 2, 3, 6], [0, 2, 3, 7], [0, 2, 7, 3], [0, 2, 7, 6]]
chemins_it5 = [[0, 2, 3, 6], [0, 2, 7, 6], [0, 1, 2, 3, 6], [0, 1, 2, 7, 6], [0, 1, 4, 5, 6], [0, 2, 3, 5, 6], [0, 2, 3, 7, 6], [0, 2, 7, 3, 6], [0, 1, 2, 3, 5, 4], [0, 1, 2, 3, 5, 6], [0, 1, 2, 3, 7, 6], [0, 1, 2, 7, 3, 5], [0, 1, 2, 7, 3, 6], [0, 1, 4, 5, 3, 2], [0, 1, 4, 5, 3, 6], [0, 1, 4, 5, 3, 7], [0, 2, 1, 4, 5, 3], [0, 2, 1, 4, 5, 6], [0, 2, 3, 5, 4, 1], [0, 2, 7, 3, 5, 4], [0, 2, 7, 3, 5, 6]]
            
# Time and memory Profile
# # Ecrivez votre réponse à la question 6.2 ici
print("Itération 1")
%timeit recursive2(chemins_it1)
%memit recursive2(chemins_it1)

print("Itération 3")
%timeit recursive2(chemins_it3)
%memit recursive2(chemins_it3)

print("Itération 5")
%timeit recursive2(chemins_it5)
%memit recursive2(chemins_it5)

# Déclaration des variables en fonction des itérations (1, 3 et 5) chemins_it1 = [[0, 1], [0, 2]] chemins_it3 = [[0, 1, 2, 3], [0, 1, 2, 7], [0, 1, 4, 5], [0, 2, 1, 4], [0, 2, 3, 5], [0, 2, 3, 6], [0, 2, 3, 7], [0, 2, 7, 3], [0, 2, 7, 6]] chemins_it5 = [[0, 2, 3, 6], [0, 2, 7, 6], [0, 1, 2, 3, 6], [0, 1, 2, 7, 6], [0, 1, 4, 5, 6], [0, 2, 3, 5, 6], [0, 2, 3, 7, 6], [0, 2, 7, 3, 6], [0, 1, 2, 3, 5, 4], [0, 1, 2, 3, 5, 6], [0, 1, 2, 3, 7, 6], [0, 1, 2, 7, 3, 5], [0, 1, 2, 7, 3, 6], [0, 1, 4, 5, 3, 2], [0, 1, 4, 5, 3, 6], [0, 1, 4, 5, 3, 7], [0, 2, 1, 4, 5, 3], [0, 2, 1, 4, 5, 6], [0, 2, 3, 5, 4, 1], [0, 2, 7, 3, 5, 4], [0, 2, 7, 3, 5, 6]] # Time and memory Profile # # Ecrivez votre réponse à la question 6.2 ici print("Itération 1") %timeit recursive2(chemins_it1) %memit recursive2(chemins_it1) print("Itération 3") %timeit recursive2(chemins_it3) %memit recursive2(chemins_it3) print("Itération 5") %timeit recursive2(chemins_it5) %memit recursive2(chemins_it5)

Itération 1
87.7 µs ± 828 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
peak memory: 51.88 MiB, increment: 0.90 MiB
Itération 3
85.7 µs ± 859 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
peak memory: 51.88 MiB, increment: 0.00 MiB
Itération 5
86.9 µs ± 1.29 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
peak memory: 51.92 MiB, increment: 0.04 MiB

In [ ]: