import heapq
import copy
import random
import [Link] as plt
import [Link] as mpatches
import networkx as nx
# Parametres globaux du labyrinthe et de la
simulation
N = 11 # taille de la grille
(impair recommande pour le labyrinthe)
SOURCE = (0, 0)
DESTINATION = (N-1, N-1)
NB_OBSTACLES_SUPP = 3 # nombre de cases
supplementaires bloquees
def generer_labyrinthe(n, seed=None,
taux_ouverture=0.18):
"""
Genere un labyrinthe imparfait sur
grille n x n.
Etape 1 : backtracking recursif ->
labyrinthe parfait (arbre, chemin unique).
Etape 2 : ouverture aleatoire de murs
interieurs -> creation de boucles.
Sans cette etape, bloquer une
case coupe forcement le chemin.
taux_ouverture : fraction de murs
interieurs supprimes (0.15-0.25 conseille).
Retourne une grille n x n avec 0=mur,
1=passage.
"""
if seed is not None:
[Link](seed)
grille = [[0] * n for _ in range(n)]
import sys
[Link](10000)
def creuser(i, j):
grille[i][j] = 1
directions = [(0,2),(0,-2),(2,0),
(-2,0)]
[Link](directions)
for di, dj in directions:
ni, nj = i+di, j+dj
if 0 <= ni < n and 0 <= nj < n
and grille[ni][nj] == 0:
grille[i+di//2][j+dj//2] =
1
creuser(ni, nj)
creuser(0, 0)
grille[0][0] = 1
grille[n-1][n-1] = 1
# Ouverture de murs pour creer des
boucles (chemins alternatifs)
murs_candidats = []
for i in range(1, n-1):
for j in range(1, n-1):
if grille[i][j] == 0:
if grille[i][j-1] == 1 and
grille[i][j+1] == 1:
murs_candidats.append((i, j))
elif grille[i-1][j] == 1
and grille[i+1][j] == 1:
murs_candidats.append((i, j))
[Link](murs_candidats)
nb_a_ouvrir = max(1,
int(len(murs_candidats) * taux_ouverture))
for mi, mj in
murs_candidats[:nb_a_ouvrir]:
grille[mi][mj] = 1
return grille
def ajouter_obstacles(grille, chemin, nb):
"""
Ajoute nb obstacles sur des passages
libres du labyrinthe,
choisis aleatoirement parmi TOUS les
passages (pas seulement
sur le chemin initial). Au moins un
obstacle doit bloquer
le chemin initial pour declencher un
recalcul.
Conditions :
- ni source ni destination ne peuvent
etre bloques
- la destination doit rester
accessible depuis la source
- au moins un obstacle coupe le
chemin initial
Retourne (nouvelle_grille,
liste_obstacles).
"""
n = len(grille)
src, dst = chemin[0], chemin[-1]
chemin_set = set(chemin)
# Tous les passages libres, hors source
et destination
tous_passages = [
(i, j) for i in range(n) for j in
range(n)
if grille[i][j] == 1 and (i,j) !=
src and (i,j) != dst
]
# On melange et on essaie de placer nb
obstacles
[Link](tous_passages)
g = [Link](grille)
obstacles = []
for nd in tous_passages:
if len(obstacles) >= nb:
break
g_test = [Link](g)
g_test[nd[0]][nd[1]] = 0
G_test = construire_graphe(g_test,
n)
# La destination doit rester
accessible
if (src in G_test.nodes() and dst
in G_test.nodes()
and nx.has_path(G_test,
src, dst)):
g[nd[0]][nd[1]] = 0
[Link](nd)
# Verifier qu'au moins un obstacle est
sur le chemin initial
# (sinon le robot ne detectera rien et
il n'y a rien a recalculer)
bloque_chemin = any(nd in chemin_set
for nd in obstacles)
if not bloque_chemin:
# Forcer un obstacle sur le chemin
(premier candidat valide)
for nd in chemin[1:-1]:
g_test = [Link](g)
g_test[nd[0]][nd[1]] = 0
G_test =
construire_graphe(g_test, n)
if (src in G_test.nodes() and
dst in G_test.nodes()
and nx.has_path(G_test,
src, dst)):
g[nd[0]][nd[1]] = 0
[Link](nd)
break
return g, obstacles
# Convertit la grille (0=mur, 1=passage) en
graphe NetworkX (liste d'adjacence)
def construire_graphe(grille, n):
G = [Link]()
for i in range(n):
for j in range(n):
if grille[i][j] == 0:
continue
G.add_node((i, j))
for di, dj in [(-1,0),(1,0),
(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0 <= ni < n and 0 <= nj
< n and grille[ni][nj] != 0:
G.add_edge((i,j),
(ni,nj), weight=1)
return G
# Heuristique de Manhattan, utilisee par A*
et D* Lite pour guider la recherche
def h(u, v):
return abs(u[0]-v[0]) + abs(u[1]-v[1])
def detecter_point_deviation(chemin_init,
obstacles):
"""
Le robot suit chemin_init pas a pas et
regarde
un noeud en avance (perception locale).
S'arrete sur le dernier noeud
accessible avant l'obstacle.
Retourne (point_deviation,
portion_parcourue).
"""
obs_set = set(obstacles)
parcours = []
for k, noeud in enumerate(chemin_init):
if noeud in obs_set:
dev = chemin_init[k-1] if k > 0
else chemin_init[0]
return dev, parcours
[Link](noeud)
if k+1 < len(chemin_init) and
chemin_init[k+1] in obs_set:
return noeud, parcours
return None, parcours
# Remonte la chaine des predecesseurs pour
reconstruire un chemin complet
def reconstruire_chemin(pred, source,
destination):
chemin, noeud = [], destination
while noeud is not None:
[Link](noeud)
noeud = pred[noeud]
[Link]()
return chemin if chemin and chemin[0]
== source else []
# Strategie 1 : Dijkstra naif — recalcul
complet depuis le point de deviation,
# sans reutiliser aucune information du
calcul initial
def dijkstra_naif(G, source, destination):
dist = {u: float('inf') for u in
[Link]()}
pred = {u: None for u in [Link]()}
exp = set()
dist[source] = 0
file = [(0, source)]
while file:
d, u = [Link](file)
if d > dist[u]: continue
[Link](u)
for v in [Link](u):
w = G[u][v]['weight']
if dist[u]+w < dist[v]:
dist[v] = dist[u]+w
pred[v] = u
[Link](file,
(dist[v], v))
return reconstruire_chemin(pred,
source, destination), dist[destination],
len(exp)
# Precalcule l'arbre des plus courts
chemins depuis la destination,
# sur le graphe deja perturbe. Utilise par
les strategies intelligentes.
def dijkstra_precalcul(G, destination):
dist = {u: float('inf') for u in
[Link]()}
pred = {u: None for u in [Link]()}
dist[destination] = 0
file = [(0, destination)]
while file:
d, u = [Link](file)
if d > dist[u]: continue
for v in [Link](u):
w = G[u][v]['weight']
if dist[u]+w < dist[v]:
dist[v] = dist[u]+w
pred[v] = u
[Link](file,
(dist[v], v))
return dist, pred
# Strategie 2 : Dijkstra intelligent —
explore depuis le point de deviation
# et s'arrete des qu'il rejoint un noeud
deja connu dans l'arbre precalcule
def dijkstra_intelligent(G, source,
destination, arbre_dist, arbre_pred):
dist_loc = {u: float('inf') for u in
[Link]()}
pred_loc = {u: None for u in [Link]()}
dist_loc[source] = 0
file = [(0, source)]
exp = 0
jonc = None
while file:
d, u = [Link](file)
if d > dist_loc[u]: continue
exp += 1
if arbre_dist.get(u, float('inf'))
< float('inf'):
jonc = u
break
for v in [Link](u):
w = G[u][v]['weight']
if dist_loc[u]+w < dist_loc[v]:
dist_loc[v] = dist_loc[u]+w
pred_loc[v] = u
[Link](file,
(dist_loc[v], v))
if jonc is None:
return [], float('inf'), exp
debut = reconstruire_chemin(pred_loc,
source, jonc)
fin = reconstruire_chemin(arbre_pred,
destination, jonc)
[Link]()
return debut+fin[1:],
dist_loc[jonc]+arbre_dist[jonc], exp
# Strategie 3 : A* naif — guide par
l'heuristique vers la destination,
# sans aucune reutilisation d'un calcul
precedent
def astar(G, source, destination):
g = {u: float('inf') for u in
[Link]()}
pred = {u: None for u in [Link]()}
exp = set()
g[source] = 0
file = [(h(source,destination), 0,
source)]
while file:
f, gs, u = [Link](file)
if u in exp: continue
[Link](u)
if u == destination: break
for v in [Link](u):
w = G[u][v]['weight']
if g[u]+w < g[v]:
g[v] = g[u]+w
pred[v] = u
[Link](file,
(g[v]+h(v,destination), g[v], v))
return reconstruire_chemin(pred,
source, destination), g[destination],
len(exp)
def astar_intelligent(G, source,
destination, arbre_dist, arbre_pred):
"""
A* intelligent : recherche guidee par
l'heuristique depuis la source,
mais s'arrete des qu'elle rejoint un
noeud deja connu dans l'arbre
precalcule depuis la destination (meme
arbre que dijkstra_intelligent).
Combine guidage heuristique +
reutilisation explicite du chemin connu.
"""
g = {u: float('inf') for u in
[Link]()}
pred = {u: None for u in [Link]()}
g[source] = 0
exp = 0
jonc = None
file = [(h(source,destination), 0,
source)]
visited = set()
while file:
f, gs, u = [Link](file)
if u in visited: continue
[Link](u)
exp += 1
if arbre_dist.get(u, float('inf'))
< float('inf'):
jonc = u
break
for v in [Link](u):
w = G[u][v]['weight']
if g[u]+w < g[v]:
g[v] = g[u]+w
pred[v] = u
[Link](file,
(g[v]+h(v,destination), g[v], v))
if jonc is None:
return [], float('inf'), exp
debut = reconstruire_chemin(pred,
source, jonc)
fin = reconstruire_chemin(arbre_pred,
destination, jonc)
[Link]()
return debut+fin[1:],
g[jonc]+arbre_dist[jonc], exp
# Strategie 4 : D* Lite (version optimisee,
Koenig & Likhachev, AAAI 2002, fig. 4)
# Recherche depuis la destination vers la
source. Maintient deux estimations
# par sommet (g et rhs) ; seuls les sommets
localement incoherents (g != rhs)
# sont traites, ce qui permet une mise a
jour incrementale apres perturbation.
class DStarLite:
def __init__(self, G, source,
destination):
self.G=G; self.s=source;
[Link]=destination
[Link]=0; self.s_last=source
self.g = {u: float('inf') for u
in [Link]()}
[Link] = {u: float('inf') for u
in [Link]()}
[Link][destination] = 0
self.U=[]; self.U_set={};
[Link]=0
self._insert(destination,
self._calc_key(destination))
def _calc_key(self, s):
m = min(self.g[s], [Link][s])
return (m+h(self.s,s)+[Link], m)
def _insert(self, s, k):
[Link](self.U,(k,s));
self.U_set[s]=k
def _top_key(self):
while self.U:
k,s = self.U[0]
if s in self.U_set and
self.U_set[s]==k: return k
[Link](self.U)
return (float('inf'),float('inf'))
def _pop(self):
while self.U:
k,s = [Link](self.U)
if s in self.U_set and
self.U_set[s]==k:
del self.U_set[s]; return
k,s
return None,None
def _update_vertex(self, u):
if u != [Link]:
succs =
list([Link](u))
[Link][u] = (min(self.G[u][v]
['weight']+self.g[v]
for v in
succs) if succs else float('inf'))
if u in self.U_set: del
self.U_set[u]
if self.g[u] != [Link][u]:
self._insert(u, self._calc_key(u))
def compute_shortest_path(self):
# Boucle principale : traite les
sommets incoherents par ordre de cle
# croissante, jusqu'a ce que la
source devienne coherente
while (self._top_key() <
self._calc_key(self.s)
or [Link][self.s] !=
self.g[self.s]):
kv, u = self._pop()
if u is None: break
[Link] += 1
kn = self._calc_key(u)
if kv < kn:
self._insert(u, kn)
elif self.g[u] > [Link][u]:
# sommet sur-coherent : on
accepte sa nouvelle valeur
self.g[u] = [Link][u]
for s in
[Link](u):
self._update_vertex(s)
else:
# sommet sous-coherent : on
invalide et on propage
gold = self.g[u]; self.g[u]
= float('inf')
for s in
list([Link](u))+[u]:
if (s!=[Link] and
self.G.has_edge(s,u) and
abs([Link][s]-(self.G[s][u]
['weight']+gold))<1e-9):
self._update_vertex(s)
elif s==u:
self._update_vertex(s)
def appliquer_perturbation(self,
noeuds):
# Supprime les noeuds bloques et
propage l'incoherence aux voisins
for nb in noeuds:
if nb not in [Link]():
continue
vois =
list([Link](nb))+list(self.G.s
uccessors(nb))
self.G.remove_node(nb)
self.g[nb]=[Link][nb]=float('inf')
if nb in self.U_set: del
self.U_set[nb]
for v in vois:
if v in [Link]():
self._update_vertex(v)
def get_path(self):
if self.g[self.s]==float('inf'):
return []
ch=[self.s]; u=self.s; vis=set()
while u!=[Link]:
if u in vis: return []
[Link](u)
succs=[v for v in
[Link](u)]
if not succs: return []
u=min(succs, key=lambda v:
self.G[u][v]['weight']+self.g[v])
[Link](u)
return ch
def recalculer_depuis(self, P):
"""
Deplace le robot en P et recalcule.
Retourne aussi le cout MARGINAL
(explores_delta) : le nombre de
noeuds traites specifiquement pour
cette perturbation, en excluant
le calcul initial deja effectue
avant. C'est ce delta qui represente
le veritable cout de reaction a
CETTE perturbation, comparable
equitablement au cout des autres
strategies (qui ne sont elles
non plus jamais facturees pour le
calcul de l'itineraire initial).
"""
avant = [Link]
[Link]+=h(self.s_last,P);
self.s_last=P; self.s=P
self.compute_shortest_path()
ch=self.get_path()
delta = [Link] - avant
return ch, (self.g[self.s] if
self.g[self.s]<float('inf') else
float('inf')), delta
def dstar_lite_naif(G, source,
destination):
"""
D* Lite "naif" : aucune reutilisation.
On reconstruit une structure
D* Lite entierement neuve, directement
sur le point de deviation,
sans aucun etat herite d'un calcul
precedent. C'est equivalent a
relancer une recherche complete depuis
zero a chaque perturbation,
comme le ferait Dijkstra naif ou A*
naif, mais avec la mecanique
(et le cout de gestion) propre a D*
Lite.
"""
ds = DStarLite(G, source, destination)
ds.compute_shortest_path()
ch = ds.get_path()
cout = ds.g[source] if ds.g[source] <
float('inf') else float('inf')
return ch, cout, [Link]
# Affiche un panneau (une grille) avec le
labyrinthe, l'itineraire initial
# (tirete), la portion deja parcourue
(vert) et le chemin recalcule (fleches)
def dessiner_panneau(ax, grille, n,
chemin_init, chemin_parcouru,
chemin_recalc, source,
destination, deviation,
obstacles, titre,
couleur_chemin):
obs_set = set(obstacles) if
obstacles else set()
recalc_set = set(chemin_recalc)
parcouru_set = set(chemin_parcouru)
init_set = set(chemin_init)
jonction = None
for nd in chemin_recalc:
if nd in init_set and nd !=
deviation:
jonction = nd; break
ax.set_facecolor('#0d1117')
ax.set_title(titre, color='white',
fontsize=8, pad=7,
fontfamily='monospace')
for i in range(n):
for j in range(n):
nd = (i,j)
if grille[i][j] == 0:
c = '#111827' #
mur du labyrinthe
elif nd in obs_set:
c = '#c0392b' #
obstacle ajoute
elif nd == destination:
c = '#ff6b6b'
elif nd == source:
c = '#51cf66'
elif nd == deviation:
c = '#ffd43b'
elif jonction and nd ==
jonction:
c = '#cc66ff'
elif nd in recalc_set:
c = couleur_chemin
elif nd in parcouru_set:
c = '#2d6a4f'
else:
c = '#1e2a3a' #
passage libre
ax.add_patch([Link](
(j-.5, n-1-i-.5), 1, 1,
facecolor=c,
edgecolor='#0d1117',
linewidth=0.4, zorder=1))
# Itineraire initial (tirete)
for k in range(len(chemin_init)-1):
i1,j1=chemin_init[k];
i2,j2=chemin_init[k+1]
[Link]([j1,j2],[n-1-i1,n-1-i2],
color='#445566', lw=1.0,
ls='--', alpha=0.5, zorder=2)
# Portion parcourue (trait plein vert)
for k in range(len(chemin_parcouru)-1):
i1,j1=chemin_parcouru[k];
i2,j2=chemin_parcouru[k+1]
[Link]([j1,j2],[n-1-i1,n-1-i2],
color='#52b788', lw=1.8,
zorder=3)
# Chemin recalcule (fleches)
for k in range(len(chemin_recalc)-1):
i1,j1=chemin_recalc[k];
i2,j2=chemin_recalc[k+1]
[Link]("", xy=(j2,n-1-i2),
xytext=(j1,n-1-i1),
arrowprops=dict(arrowstyle="-|>",
color=couleur_chemin,
lw=1.8,
mutation_scale=10), zorder=5)
# Labels
labels = {source:'S', destination:'D'}
if deviation: labels[deviation]='P'
if jonction: labels[jonction]='J'
for nb in obs_set: labels[nb]='X'
for nd, lbl in [Link]():
i,j=nd
[Link](j, n-1-i, lbl, ha='center',
va='center',
fontsize=7,
fontweight='bold', color='white', zorder=6)
ax.set_xlim(-.5, n-.5);
ax.set_ylim(-.5, n-.5)
ax.set_aspect('equal'); [Link]('off')
# Construit un exemple complet :
labyrinthe, perturbation, detection,
# puis comparaison visuelle des 6
strategies (naif/intelligent x 3)
def afficher_comparaison():
# Generer le labyrinthe et l'itineraire
initial
grille_laby = generer_labyrinthe(N)
G_laby =
construire_graphe(grille_laby, N)
ch_init, cout_init, _ =
dijkstra_naif(G_laby, SOURCE, DESTINATION)
if not ch_init:
print("Pas de chemin dans ce
labyrinthe, essaie un autre seed.")
return
print("Itineraire initial :", ch_init,
"| cout :", cout_init)
# Ajouter des obstacles sur le chemin
grille_pert, obstacles =
ajouter_obstacles(grille_laby, ch_init,
NB_OBSTACLES_SUPP)
if not obstacles:
print("Impossible d'ajouter des
obstacles sans couper le chemin.")
return
print("Obstacles ajoutes :", obstacles)
G_pert = construire_graphe(grille_pert,
N)
# Detection du point de deviation
deviation, parcouru =
detecter_point_deviation(ch_init,
obstacles)
if deviation is None:
print("Aucun obstacle detecte sur
le chemin.")
return
print("Obstacle detecte en :",
deviation)
print("Portion parcourue :",
parcouru)
# Recalculs pour les 6 strategies
arbre_dist, arbre_pred =
dijkstra_precalcul(G_pert, DESTINATION)
ch_naif, cout_naif, exp_naif =
dijkstra_naif(G_pert, deviation,
DESTINATION)
ch_intel, cout_intel, exp_intel =
dijkstra_intelligent(
G_pert, deviation, DESTINATION,
arbre_dist, arbre_pred)
ch_astar_n, cout_astar_n, exp_astar_n =
astar(G_pert, deviation, DESTINATION)
ch_astar_i, cout_astar_i, exp_astar_i =
astar_intelligent(
G_pert, deviation, DESTINATION,
arbre_dist, arbre_pred)
# D* Lite naif : structure neuve, sans
aucune reutilisation
ch_ds_n, cout_ds_n, exp_ds_n =
dstar_lite_naif(
construire_graphe(grille_pert, N),
deviation, DESTINATION)
# D* Lite intelligent : structure
persistante, calculee avant la
# perturbation, puis mise a jour de
facon incrementale (cout marginal)
G_ds = construire_graphe(grille_laby,
N)
ds = DStarLite(G_ds, SOURCE,
DESTINATION)
ds.compute_shortest_path()
ds.appliquer_perturbation(obstacles)
ch_ds_i, cout_ds_i, exp_ds_i =
ds.recalculer_depuis(deviation)
print("Dijkstra naif :",
ch_naif, "| cout:", cout_naif, "|
exp:", exp_naif)
print("Dijkstra intelligent :",
ch_intel, "| cout:", cout_intel, "|
exp:", exp_intel)
print("A* naif :",
ch_astar_n, "| cout:", cout_astar_n, "|
exp:", exp_astar_n)
print("A* intelligent :",
ch_astar_i, "| cout:", cout_astar_i, "|
exp:", exp_astar_i)
print("D* Lite naif :",
ch_ds_n, "| cout:", cout_ds_n, "|
exp:", exp_ds_n)
print("D* Lite intelligent :",
ch_ds_i, "| cout:", cout_ds_i, "|
exp:", exp_ds_i)
# Figure a 8 panneaux : labyrinthe
initial, detection, puis les 6 strategies
fig, axes = [Link](2, 4, figsize=
(22, 11))
axes = [Link]()
[Link].set_facecolor('#0d1117')
[Link](
"Labyrinthe aleatoire — detection
d'obstacle et recalcul (6 strategies : naif
vs intelligent)",
color='white', fontsize=11,
fontfamily='monospace')
configs = [
(grille_laby, [], ch_init, None,
None,
"[0] Labyrinthe + itineraire
initial\n(cout {})".format(cout_init),
'#74c0fc'),
(grille_pert, ch_init, [],
deviation, obstacles,
"[1] Detection de
l'obstacle\nRobot stoppe en P=
{}".format(deviation),
'#74c0fc'),
(grille_pert, ch_init, ch_naif,
deviation, obstacles,
"[2] Dijkstra naif\n(cout {}, {}
explores)".format(cout_naif, exp_naif),
'#ff9f43'),
(grille_pert, ch_init, ch_intel,
deviation, obstacles,
"[3] Dijkstra intelligent\n(cout
{}, {} explores)".format(cout_intel,
exp_intel),
'#54a0ff'),
(grille_pert, ch_init, ch_astar_n,
deviation, obstacles,
"[4] A* naif\n(cout {}, {}
explores)".format(cout_astar_n,
exp_astar_n),
'#8e8ad1'),
(grille_pert, ch_init, ch_astar_i,
deviation, obstacles,
"[5] A* intelligent\n(cout {}, {}
explores)".format(cout_astar_i,
exp_astar_i),
'#a29bfe'),
(grille_pert, ch_init, ch_ds_n,
deviation, obstacles,
"[6] D* Lite naif\n(cout {}, {}
explores)".format(cout_ds_n, exp_ds_n),
'#4a7a78'),
(grille_pert, ch_init, ch_ds_i,
deviation, obstacles,
"[7] D* Lite intelligent\n(cout
{}, {} explores)".format(cout_ds_i,
exp_ds_i),
'#00d2d3'),
]
for ax, (grl, ch_i, ch_r, dev, obs,
titre, col) in zip(axes, configs):
dessiner_panneau(ax, grl, N,
chemin_init=ch_i,
chemin_parcouru=parcouru if dev else [],
chemin_recalc=ch_r,
source=SOURCE,
destination=DESTINATION,
deviation=dev,
obstacles=obs,
titre=titre,
couleur_chemin=col)
legendes = [
[Link](color='#111827',
label='mur labyrinthe'),
[Link](color='#51cf66',
label='S source'),
[Link](color='#ffd43b',
label='P detection'),
[Link](color='#ff6b6b',
label='D destination'),
[Link](color='#cc66ff',
label='J jonction'),
[Link](color='#2d6a4f',
label=' parcouru'),
[Link](color='#c0392b',
label='X obstacle ajoute'),
[Link](color='#445566',
label='-- itineraire initial'),
]
leg = [Link](handles=legendes,
loc='lower center',
bbox_to_anchor=
(0.5,-0.02), ncol=8, fontsize=7.5,
facecolor='#0d1117',
edgecolor='#2a2a4a')
for t in leg.get_texts():
t.set_color('white')
plt.tight_layout()
[Link]("tipe_labyrinthe.png",
dpi=150,
bbox_inches='tight',
facecolor='#0d1117')
[Link]()
print("Figure sauvegardee :
tipe_labyrinthe.png")
# Protocole experimental : moyenne du
nombre de noeuds explores par strategie,
# sur des labyrinthes aleatoires de tailles
croissantes (cout marginal honnete)
def protocole_experimental(tailles=None,
nb_essais=30):
if tailles is None:
tailles = [7, 9, 11, 13, 15]
cles =
['dij_n','dij_i','ast_n','ast_i','ds_n','ds
_i']
res = {c: [] for c in cles}
for n in tailles:
print("Grille {}x{}
...".format(n,n))
src = (0,0); dest = (n-1,n-1)
listes = {c: [] for c in cles}
for trial in range(nb_essais):
# Labyrinthe aleatoire
different a chaque essai
glab = generer_labyrinthe(n,
seed=trial)
G_lab = construire_graphe(glab,
n)
if dest not in G_lab.nodes():
continue
ch_i, _, _ =
dijkstra_naif(G_lab, src, dest)
if not ch_i: continue
# Ajouter 1 ou 2 obstacles sur
le chemin
g_pert, obs =
ajouter_obstacles(glab, ch_i, 2)
if not obs: continue
G_p = construire_graphe(g_pert,
n)
if dest not in G_p.nodes():
continue
dev, _ =
detecter_point_deviation(ch_i, obs)
if dev is None: continue
ad, ap =
dijkstra_precalcul(G_p, dest)
_, _, e_dn = dijkstra_naif(G_p,
dev, dest)
_, _, e_di =
dijkstra_intelligent(G_p, dev, dest, ad,
ap)
_, _, e_an = astar(G_p, dev,
dest)
_, _, e_ai =
astar_intelligent(G_p, dev, dest, ad, ap)
_, _, e_dsn =
dstar_lite_naif(construire_graphe(g_pert,
n), dev, dest)
Gd = construire_graphe(glab, n)
ds = DStarLite(Gd, src, dest)
ds.compute_shortest_path()
ds.appliquer_perturbation(obs)
_, _, e_dsi =
ds.recalculer_depuis(dev)
for c, v in zip(cles,
[e_dn,e_di,e_an,e_ai,e_dsn,e_dsi]):
listes[c].append(v)
if not listes['dij_n']: continue
for c in cles:
res[c].append(sum(listes[c])/len(listes[c])
)
tailles_ok =
tailles[:len(res['dij_n'])]
nb_noeuds = [n*n for n in tailles_ok]
fig, ax = [Link](figsize=(10,6))
[Link].set_facecolor('#0d1117');
ax.set_facecolor('#0d1117')
style = [
('dij_n', 'tomato', 'o-',
'Dijkstra naif', 0),
('dij_i', 'steelblue', 's-',
'Dijkstra intelligent', -0.5),
('ast_n', '#8e8ad1', '^-', 'A*
naif', 0),
('ast_i', '#a29bfe', '^-', 'A*
intelligent', 0.5),
('ds_n', '#4a7a78', 'D-', 'D*
Lite naif', 0),
('ds_i', '#00d2d3', 'D-', 'D*
Lite intelligent', 0),
]
for key, col, mk, lbl, offset in style:
ls = '-' if ('intelligent' in lbl)
else '--'
valeurs = [v + offset for v in
res[key]]
[Link](nb_noeuds, valeurs, mk,
color=col, lw=2, linestyle=ls, label=lbl)
# Annotation clarifiant l'effet
degenere des variantes "intelligentes"
# baties sur un arbre global (Dijkstra
/ A*)
[Link](
"Dijkstra intelligent et A*
intelligent\nconvergent vers ~1 noeud :\n"
"l'arbre precalcule depuis D
couvre\ndeja tout le graphe (cout cache\nde
precalcul, amorti ailleurs)",
xy=(nb_noeuds[2], 1), xytext=
(nb_noeuds[1]+5, 45),
fontsize=9, color='#cccccc',
fontfamily='monospace',
arrowprops=dict(arrowstyle='->',
color='#888888', lw=1.2),
bbox=dict(boxstyle='round,pad=0.4',
fc='#1a2230', ec='#444444')
)
ax.set_xlabel("Nombre de noeuds",
color='white')
ax.set_ylabel("Noeuds explores
(moyenne, cout marginal)", color='white')
ax.set_title("6 strategies — labyrinthe
aleatoire + obstacles\n"
"(trait plein =
intelligent, tirete = naif ; "
"leger decalage vertical
pour lisibilite pres de 0)",
color='white',
fontfamily='monospace', fontsize=10.5)
ax.tick_params(colors='#aaaaaa')
for sp in ['bottom','left']:
[Link][sp].set_color('#444444')
for sp in ['top','right']:
[Link][sp].set_visible(False)
[Link](True, color='#2a2a3a', ls='--',
alpha=0.5)
leg = [Link](facecolor='#1a1a2e',
edgecolor='#444444', fontsize=9, ncol=2)
for t in leg.get_texts():
t.set_color('white')
plt.tight_layout()
[Link]("tipe_protocole_laby.png",
dpi=150,
bbox_inches='tight',
facecolor='#0d1117')
[Link]()
print("\nResultats moyens (cout
marginal, noeuds explores) :")
for i, n in enumerate(tailles_ok):
print(" {}x{} : Dij_n={:.1f}
Dij_i={:.1f} A*_n={:.1f} A*_i={:.1f} D*_n=
{:.1f} D*_i={:.1f}".format(
n,n, res['dij_n'][i],
res['dij_i'][i],
res['ast_n'][i], res['ast_i']
[i],
res['ds_n'][i], res['ds_i']
[i]))
if __name__ == "__main__":
# Aucun seed fixe : labyrinthe et
obstacles differents a chaque lancement
# Partie 1 : exemple visuel complet sur
un labyrinthe
afficher_comparaison()
# Partie 2 : protocole experimental sur
plusieurs tailles de graphe
protocole_experimental(tailles=
[7,9,11,13,15], nb_essais=30)