Piles, files
et graphes.

• Choisir entre pile, file et file de priorité.
• Représenter une carte, un réseau, un labyrinthe comme un graphe.
• Trouver le plus court chemin dans une grille avec obstacles (BFS) puis avec coûts (Dijkstra).
• Expliquer pourquoi BFS trouve toujours le plus court et pas DFS.

Les mesures d’un capteur arrivent plus vite qu’on ne les traite : on les met dans une file, et on les consomme dans l’ordre. Un deque(maxlen=100) oublie automatiquement les plus anciennes : un tampon circulaire. Les commandes envoyées à un moteur, les messages réseau, les événements clavier : tout passe par des files.

Une parenthèse fermante doit correspondre à la dernière ouvrante non encore fermée : exactement LIFO. La notation polonaise inverse n’a pas besoin de parenthèses ni de priorités : les calculatrices HP et la machine virtuelle Python (le bytecode de la séance 01 : LOAD, LOAD, BINARY_OP) fonctionnent ainsi. Écrire un convertisseur d’expression classique vers RPN (algorithme de la gare de triage, Dijkstra) est un bel exercice.

Une carte routière, Internet, un réseau social, les états d’un Rubik’s cube, les dépendances d’un projet, les coups possibles d’une partie d’échecs, une grille de labyrinthe (chaque case est un sommet, relié à ses 4 voisines libres). Une fois le problème traduit en graphe, les mêmes trois algorithmes le résolvent : DFS, BFS, Dijkstra.

Sans lui, un graphe avec un cycle (couloir → labo → couloir…) ferait boucler le parcours. On marque un sommet au moment où on l’empile, pas quand on le dépile : sinon il pourrait être empilé plusieurs fois. DFS répond à « est-ce atteignable ? », « y a-t-il un cycle ? », « quelles sont les composantes ? », mais ne trouve pas le plus court chemin : il s’enfonce dans une direction avant d’en essayer une autre.

La file traite les sommets dans l’ordre où ils ont été découverts : d’abord tous ceux à distance 1, puis tous ceux à distance 2, etc. (par couches). Quand on atteint l’arrivée, on l’a forcément atteinte par la première couche qui la contient, c’est-à-dire à distance minimale. L’invariant : la file contient des sommets à distance d puis d+1, jamais plus. Le dictionnaire precedent forme un arbre des plus courts chemins ; le remonter donne le chemin. Complexité : O(sommets + arêtes).

On ne construit jamais le dictionnaire des 70 cases et de leurs voisins : la fonction voisins() le calcule à la demande. C’est un graphe implicite, indispensable quand les sommets sont trop nombreux pour être listés (les 4,3 × 10¹⁹ états d’un Rubik’s cube). Comparez avec le backtracking de la séance 12 : celui-ci trouvait un chemin ; BFS trouve le plus court. Le while s: fonctionne car (0, 0) est un tuple non vide, donc vrai — mais None est faux.

BFS suppose que chaque arête coûte 1. Avec des coûts variés, il faut toujours traiter le sommet le moins cher en attente : c’est une file de priorité, implémentée par un tas (heapq) où insertion et extraction du minimum coûtent O(log n). Dijkstra (1956, conçu en 20 minutes à une terrasse de café) est BFS avec un tas à la place de la file. Le robot contourne le sable par le bas : 2 pas de plus (14 au lieu de 12), mais un coût de 14 au lieu de 24. Changez le coût du sable à 2 : que choisit-il ? Complexité O((S + A) log S). Il ne fonctionne pas avec des coûts négatifs (Bellman-Ford pour cela).

A* ajoute à la distance parcourue une estimation de ce qui reste (ici la distance de Manhattan). Si l’estimation ne surestime jamais (elle est admissible), A* trouve le chemin optimal en explorant beaucoup moins : ici ~80 sommets au lieu de 1600. C’est l’algorithme de navigation de tous les jeux vidéo et de la plupart des robots mobiles. Une heuristique trop optimiste (zéro) redonne Dijkstra ; trop pessimiste, on perd l’optimalité mais on va plus vite (A* pondéré).

def contient_cycle(graphe):
    etat = {}                                  # absent = jamais vu, 1 = en cours, 2 = terminé
    def visite(s):
        etat[s] = 1
        for v in graphe.get(s, []):
            if etat.get(v) == 1:
                return True                    # arc arrière : cycle
            if v not in etat and visite(v):
                return True
        etat[s] = 2
        return False
    return any(s not in etat and visite(s) for s in graphe)

Détecter un cycle dans un graphe orienté est ce que fait pip pour les dépendances, un tableur pour les formules circulaires, et un ordonnanceur de tâches. L’absence de cycle permet un tri topologique (ordre dans lequel faire les tâches).

def plus_court_avec_cle():
    trouver = lambda c: next((x, y) for y in range(H) for x in range(L) if grille[y][x] == c)
    depart = (*trouver("S"), False)
    arrivee_xy = trouver("E")
    file = deque([depart]); precedent = {depart: None}
    while file:
        x, y, cle = file.popleft()
        if (x, y) == arrivee_xy:
            n = 0; s = (x, y, cle)
            while precedent[s] is not None: n += 1; s = precedent[s]
            return n
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < L and 0 <= ny < H): continue
            c = grille[ny][nx]
            if c == "#" or (c == "D" and not cle): continue
            etat = (nx, ny, cle or c == "K")
            if etat not in precedent:
                precedent[etat] = (x, y, cle); file.append(etat)
    return None

L’astuce générale : quand la solution dépend de « ce qu’on a fait avant », on l’ajoute à l’état. Le graphe devient (positions × possessions). Avec 3 clés, 8 combinaisons ; avec n objets, 2ⁿ : c’est là que l’explosion combinatoire commence, et qu’A* avec une bonne heuristique devient indispensable.

def voisins(etat):
    i = etat.index("0")
    x, y = i % 3, i // 3
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < 3 and 0 <= ny < 3:
            j = ny * 3 + nx
            l = list(etat); l[i], l[j] = l[j], l[i]
            yield "".join(l)

def resoudre(depart, but="123456780"):
    file = deque([depart]); precedent = {depart: None}
    while file:
        s = file.popleft()
        if s == but:
            n = 0
            while precedent[s]: n += 1; s = precedent[s]
            return n
        for v in voisins(s):
            if v not in precedent:
                precedent[v] = s; file.append(v)

print(resoudre("412703685"), "coups")

# Exhaustif depuis la solution : distances de tous les états
dist = {"123456780": 0}; file = deque(["123456780"])
while file:
    s = file.popleft()
    for v in voisins(s):
        if v not in dist:
            dist[v] = dist[s] + 1; file.append(v)
print(len(dist), "états atteignables, le plus loin à", max(dist.values()), "coups")
print([s for s, d in dist.items() if d == 31])

Le taquin a 9! = 362 880 configurations, mais seule la moitié est atteignable : chaque glissement change la parité d’une certaine permutation, et la parité de la solution est fixée (Johnson & Story, 1879 : c’est pourquoi le célèbre « défi à 1000 $ » de Sam Loyd était impossible). BFS explore les 181 440 états en une seconde ; le taquin 4×4 en a 10¹³ : il faut A* avec l’heuristique de Manhattan, et c’est un banc d’essai classique de l’IA. Le Rubik’s cube (4,3 × 10¹⁹) a été résolu par des méthodes similaires : 20 coups suffisent toujours (« God’s number », 2010, 35 années-CPU).