#! /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)")