Code source de TP3

#! /usr/bin/env python3
# -*- coding: utf-8; mode: python -*-
""" TP3 au Lycée Lakanal (sujet rédigé par Arnaud Basson).

- *Date :* jeudi 15-10 et 05-11 (2015),
- *Auteur :* Lilian Besson, pour le cours d'informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/),
- *Licence :* MIT Licence (http://lbesson.mit-license.org).
"""

from __future__ import print_function, division

# %% Exercice 1 : Exploration d'un labyrinthe

# Exemple d'un labyrinthe (celui du TP, avec solution)
laby = [
    [0, 1, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 0],
    [0, 1, 0, 1, 0, 0],
    [0, 1, 0, 1, 1, 0],
    [0, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 0]
]


[docs]def parcoursLabyrinthe(laby, full=False): """ Parcours le labyrinthe laby avec l'algorithme détaillé dans le TP. - :math:`O(n^2)` en espace additionnel (dejavues prend :math:`n^2` et p prend au pire :math:`O(n^2)` pour graphe complet), - :math:`O(n^2)` en temps (chaque case ne peut être empilée et dépilée qu'une seule fois). - Si full est ``True``, on renvoie aussi le tableau des cases visitées (dejavues).""" n = len(laby) # Pour savoir quels cases ont déjà été explorées dejavues = [[False] * n for i in range(n)] # Pile des cases à explorer p = [] # Case de départ p.append((0, 1)) dejavues[0][1] = True # On part de là, on l'a vue # Tant que la pile n'est pas vide while p: # print("Pile p =", p) # On peut dépiler une case à explorer et continuer case = p.pop() # On se fiche de l'ordre de dépilement x, y = case # Au mieux 4 cases adjacentes if x == 0: # On ne regarde pas en haut ! indicesAdjacentes = [(x + 1, y), (x, y - 1), (x, y + 1)] else: # On peut regarder en haut indicesAdjacentes = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)] # Quelle case est adjacente et non encore vue ? adjacentes = [] for (i, j) in indicesAdjacentes: # On se fiche de l'ordre de parcours if i >= 0 and j >= 0 and i < n and j < n and laby[i][j] and not dejavues[i][j]: adjacentes += [(i, j)] # On marque comme vue les cases adjacentes non vues et on les empiles for (i, j) in adjacentes: dejavues[i][j] = True # On peut s'arrêter tout de suite, mais pas nécessaire (ça fait juste gagner du temps, environ un facteur 2) # if (i, j) == (n - 1, n - 2): # return True p.append((i, j)) # Si la case de sortie a été visitée, on a gagné ! if full: return dejavues[n - 1][n - 2], dejavues else: return dejavues[n - 1][n - 2]
from numpy import array # Exemple d'un labyrinthe avec solution print("Exemple 1 : Le labyrinthe exemple donne par le TP est :") print(array(laby)) print(" ==> Et il admet une solution car : parcoursLabyrinthe(laby) =", parcoursLabyrinthe(laby)) # Exemple d'un labyrinthe sans solution laby2 = [ [0, 1, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0], [0, 0, 1, 0, 1, 0], [0, 1, 1, 1, 1, 0], [0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0] ] print("Exemple 2 : ce labyrinthe n'a pas de solution :") print(array(laby2)) print(" ==> En effet parcoursLabyrinthe(laby2) =", parcoursLabyrinthe(laby2)) # %% Exercice B :Application à un problème de percolation en milieu aléatoire import random # B.1. Construction du milieu poreux aléatoire.
[docs]def creerMilieu(n, p): """ Créé un labyrinthe **aléatoire** de taille (n, n) représentant un milieu de porosité p.""" # Ces deux vérifications peuvent être ignorées assert 0 < p < 1, "La porosité du milieu p doit être comprise entre 0 et 1 strictement." assert n > 3, "Au moins quatre × quatre cases svp !" milieuPoreux = [[0] * n for i in range(n)] # Remplissons aléatoirement le milieu for i in range(1, n - 1): for j in range(1, n - 1): if random.random() < p: # Vide avec probabilité p milieuPoreux[i][j] = 1 # Seconde et avant-dernière ligne : milieuPoreux[1] = [0] + [1] * (n - 2) + [0] milieuPoreux[n - 2] = [0] + [1] * (n - 2) + [0] # Entrée et sortie du milieu : milieuPoreux[0][1] = milieuPoreux[n - 1][n - 2] = 1 return milieuPoreux
# from numpy import array # Exemples de milieux poreux : if __name__ == '__main__': print("\nPour n = 20 et p = 0.1 :") print(array(creerMilieu(20, 0.1))) print("\nPour n = 20 et p = 0.5 :") print(array(creerMilieu(20, 0.5))) print("\nPour n = 20 et p = 0.9 :") print(array(creerMilieu(20, 0.9))) # %% B.2. Simulation de l'écoulement
[docs]def simulationEcoulement(n, p, nb=20): """ Lance nb (20) simulations pour n, p et affiche le nombre de fois où l'eau s'est écoulée jusqu'en bas.""" nbfois = 0 for k in range(nb): milieuPoreux = creerMilieu(n, p) if parcoursLabyrinthe(milieuPoreux): nbfois += 1 print("Pour n =", n, "et p =", p, "et", nb, "exemples, l'ecoulement a lieu", 100 * (nbfois / nb), "% des fois.")
# On fait quelques simulations, apparemment p_c = 0.6 a 0.01 près if __name__ == '__main__': for n in [50, 100, 200]: for p in [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]: simulationEcoulement(n, p) for p in [0.56, 0.58, 0.59, 0.60, 0.61, 0.62]: simulationEcoulement(n, p) print("==> On a fait quelques simulations, apparemment p_c = 0.6 a 0.01 pres.") # Ces simulations montrent que le seuil est vraiment autour de p = 0.60 : # Pour n = 400 et p = 0.56 et 20 exemples, l'écoulement a lieu 0.0 % des fois. # Pour n = 400 et p = 0.58 et 20 exemples, l'écoulement a lieu 0.0 % des fois. # Pour n = 400 et p = 0.59 et 20 exemples, l'écoulement a lieu 45.0 % des fois. # Pour n = 400 et p = 0.6 et 20 exemples, l'écoulement a lieu 90.0 % des fois. # Pour n = 400 et p = 0.61 et 20 exemples, l'écoulement a lieu 100.0 % des fois. # Pour n = 400 et p = 0.62 et 20 exemples, l'écoulement a lieu 100.0 % des fois. # %% Bonus : Affichage import matplotlib.pyplot as plt from numpy import zeros
[docs]def afficheMilieuPoreux(milieuPoreux, title=None, filename=None): """ Affiche le milieu poreux et l'écoulement d'eau comme dans le TP. - On peut fournir le titre et le nom du fichier vers lequel on sauvegarde l'image.""" n = len(milieuPoreux) # plt.imshow(milieuPoreux, interpolation='none', cmap='gray') # plt.show() _, dejavues = parcoursLabyrinthe(milieuPoreux, full=True) # on récupère la matrice et pas la réponse booléenne image = zeros((n, n, 3)) # RGB image de taille n,n for i in range(n): for j in range(n): if dejavues[i][j]: image[i, j, :] = [127, 204, 255] # lightblue elif milieuPoreux[i][j]: image[i, j, :] = [255, 255, 255] # white else: image[i, j, :] = [0, 0, 0] # black image /= 255 # Les flottants doivent être entre 0.0 et 1.0 plt.imshow(image, interpolation='none', cmap=None) plt.xticks([]) plt.yticks([]) if title: plt.title(title) if filename: plt.savefig(filename) plt.show() return image
# Exemples if __name__ == '__main__': print("Exemple d'un milieu tres peu poreux (p = 0.50) :") t = creerMilieu(200, 0.50) # image = afficheMilieuPoreux(t, title="Exemple d'un milieu très peu poreux (p = 0.50)", filename="TP3__Exemple_milieu_peu_poreux.png") print("Exemple d'un milieu moyennement poreux (p = 0.60) :") t = creerMilieu(200, 0.60) # image = afficheMilieuPoreux(t, title="Exemple d'un milieu moyennement poreux (p = 0.60)", filename="TP3__Exemple_milieu_poreux.png") print("Exemple d'un milieu tres poreux (p = 0.70) :") t = creerMilieu(200, 0.70) # image = afficheMilieuPoreux(t, title="Exemple d'un milieu très poreux (p = 0.70)", filename="TP3__Exemple_milieu_très_poreux.png") # %% Partie C : Généralisation : parcours d’un graphe # C.3) Exemple d'une matrice d'adjacence g = [[0] * 9 for k in range(9)] for (i, j) in [(0, 1), (0, 2), (0, 4), (1, 4), (1, 5), (3, 7), (3, 8), (4, 6), (5, 6)]: g[i][j] = g[j][i] = 1 # from numpy import array print("Le graphe exemple de l'enonce est :") print(array(g)) # C.4) Vérifier un chemin
[docs]def verifierChemin(A, chemin): r""" Vérifie que le chemin donné par la liste des sommets successifs (chemin) est bien un chemin valable pour le graphe A. - :math:`O(1)` en espace, :math:`O(\text{Nb chemin})` en temps.""" return all(A[chemin[i]][chemin[i + 1]] for i in range(len(chemin) - 1))
# Trois exemples if __name__ == '__main__': # print("On considere le graphe g :", g) chemin0 = [0, 1, 4, 6, 5] # (A, B, E, G, F) print("Le chemin", chemin0, "est valable dans le graphe g.") assert verifierChemin(g, chemin0) chemin1 = [0, 1, 4, 5, 6] # (A, B, E, F, G) print("Le chemin", chemin1, "n'est pas valable dans le graphe g.") assert not verifierChemin(g, chemin1) chemin2 = [5, 6, 3, 7, 8] # (F, G, D, H, I) print("Le chemin", chemin2, "n'est pas valable dans le graphe g.") assert not verifierChemin(g, chemin2) chemin3 = [0, 1, 0] # (A, B, A) print("Le chemin", chemin3, "est valable dans le graphe g.") assert verifierChemin(g, chemin3) # C.5)
[docs]def parcoursGraphe(A, j, k): """ Parcours (*en largeur*) du graphe A, en partant de j, et tentant d'atteindre k, renvoie True ou False selon qu'un chemin existe entre j et k dans A. - Mémoire :math:`O(n)`, temps max :math:`O(n^2)` pour n le nombre de sommets.""" n = len(A) # Aucun sommet n'a déjà été visité depuis le sommet j dejaVisites = [False] * n # Pile vide aExplorer = [] # On commence en j dejaVisites[j] = True aExplorer.append(j) # Tant qu'on peut explorer les voisins while aExplorer: i = aExplorer.pop() # on dépile un sommet # Note : si on utilise une file au lieu d'une pile, c'est un parcours en largeur, là c'est en profondeur adjacents = [l for l in range(n) if A[i][l] and not dejaVisites[l]] for l in adjacents: # On marque comme visités ses voisins non encore visités dejaVisites[l] = True # Et on les empile aExplorer.append(l) if l == k: return True return dejaVisites[k] # Will always be False
# Exemple print("Pour le graphe g :") print(array(g)) print("Existe-t-il un chemin entre j = 0 = A et k = G = 6 ?", parcoursGraphe(g, 0, 6), "(oui)") print("Existe-t-il un chemin entre j = 0 = A et k = D = 3 ?", parcoursGraphe(g, 0, 3), "(non)") # %% C.6) Rafinement
[docs]def cheminGraphe(A, j, k): """ Parcours (*en largeur*) du graphe A, en partant de j, et tentant d'atteindre k, renvoyant un chemin valable s'il existe, False sinon. - Mémoire :math:`O(n)`, temps max :math:`O(n^2)` pour n le nombre de sommets.""" n = len(A) # Aucun sommet n'a déjà été visité depuis le sommet j pred = [-1] * n # -1 si non visité, >= 0 si visité # Pile vide aExplorer = [] # On commence en j pred[j] = j # On marque le sommet de départ avec un nombre positif arbitraire (par exemple son propre numéro) car il est visité d’office mais n’a pas de prédécesseur aExplorer.append(j) # Tant qu'on peut explorer les voisins while aExplorer: i = aExplorer.pop() # on dépile un sommet # Note : si on utilise une file au lieu d'une pile, c'est un parcours en largeur, là c'est en profondeur adjacents = [l for l in range(n) if A[i][l] and (pred[l] < 0)] for l in adjacents: # On marque comme visités ses voisins non encore visités pred[l] = i # On vient du sommet i # Et on les empile aExplorer.append(l) # On a finit d'explorer tous les voisins possibles # Maintenant on tente de construire le chemin chemin = [] # On part de la fin sommetCourant = k while pred[sommetCourant] >= 0 and sommetCourant != j: chemin.append(sommetCourant) sommetCourant = pred[sommetCourant] # On remonte le chemin d'une étape if sommetCourant == j: chemin.append(sommetCourant) chemin.reverse() # On les a empilé de la fin return chemin else: return False # Pas de chemin valable
# Exemple print("Pour le graphe g :") print(array(g)) print("Existe-t-il un chemin entre j = 0 = A et k = G = 6 ?") print("Oui, le voici :", cheminGraphe(g, 0, 6)) print(" ([A, B, E, G] ou [A, E, G] ou [A, B, F, G] soit [0, 1, 4, 6] ou [0, 4, 6] ou [0, 1, 6])") print("Existe-t-il un chemin entre j = 0 = A et k = D = 3 ?", cheminGraphe(g, 0, 3), "(non)")