L’heuristique de distance de Manhattan est probablement la plus utilisée en recherche heuristique, toutes époques confondues. Introduite informellement dans les années 60 pour le 15-puzzle, formalisée dans l’article A* de 1968, encore aujourd’hui ce que tout manuel d’IA enseigne en premier. Voici pourquoi elle marche, ce qu’elle fait bien et où elle cesse de suffire.
La définition
Pour un taquin N×N, par tuile (en ignorant le vide), calculez :
distance = | rangée_actuelle − rangée_cible | + | col_actuelle − col_cible |
Somme sur les tuiles. C’est la distance de Manhattan du plateau au but.
Pourquoi « Manhattan » ? Les rues de Manhattan sont en damier. On marche tant de blocs est-ouest plus tant de blocs nord-sud. Pas de diagonale possible. Le total est la distance de Manhattan — aussi taxicab distance ou norme L¹.
Pour une tuile, même logique : un coup = un pas horizontal ou vertical, pas de diagonale. Le minimum de coups pour aller de sa position courante à sa cible est la distance en rangées + distance en colonnes.
Admissibilité
A* exige une heuristique admissible : ne jamais surestimer le nombre réel de coups restants. Si elle surestime, A* peut couper le chemin optimal et renvoyer du sous-optimal.
Manhattan est admissible parce que :
- Chaque tuile doit voyager au moins sa distance en rangées + colonnes, les coups étant des pas unitaires.
- La somme sur toutes les tuiles ne dépasse pas la réalité, chaque coup avançant exactement une tuile d’une case.
- En réalité la vraie distance est au moins Manhattan, parce qu’on doit souvent écarter pour laisser passer — mais jamais moins.
Donc Manhattan ≤ réelle. Admissible.
Consistance
Propriété plus forte : consistance, parfois monotonie. Une heuristique est consistante si pour tout état s et tout successeur s’ par coup m :
h(s) ≤ cost(m) + h(s’)
En français : l’heuristique ne peut pas chuter de plus de un en un coup.
Manhattan est consistante : un coup change sa valeur exactement de +1 ou −1. (Une tuile bouge d’une case ; sa contribution change de ±1 ; les autres restent.)
La consistance garantit qu’A* ne réouvre pas d’état déjà fermé. Les implémentations n’ont pas à gérer le cas inconsistant — code et preuves simplifiés.
Pourquoi ça marche si bien en pratique
Trois propriétés :
Bon marché. O(N²) par plateau — somme sur les tuiles, contribution constante. h(s) en microsecondes sur tout ordinateur moderne.
Assez serrée pour bien élaguer. Sur 15-puzzles, Manhattan vaut en moyenne 75–90 % de la vraie distance. A* avec une heuristique aussi serrée explore une fraction infime de l’espace.
Combine bien avec le conflit linéaire. Ajouter 2 coups par « conflit linéaire » (deux tuiles d’une même rangée appartenant à cette rangée mais mal ordonnées) donne une heuristique strictement plus serrée pour un coût marginal.
Où elle est trop lâche
Manhattan traite les tuiles comme si elles pouvaient se traverser. Elles ne peuvent pas. Le point aveugle le plus profond :
Conflits dans rangée ou colonne. Si 2 et 3 sont dans la rangée 1 mais mal ordonnées, Manhattan leur donne leurs distances droites et ne note rien. En réalité, l’une doit sortir, l’autre passer, et la première rentrer — au moins 2 coups en plus que Manhattan ne voit pas. Conflit linéaire corrige.
Structure « walking ». Manhattan ignore les relations entre tuiles d’une même rangée/colonne qui appartiennent toutes à celle-ci. Une rangée de quatre tuiles mal permutées exige plusieurs « échanges de rangée » — structure que capture walking distance.
Interactions de sous-ensembles disjoints. Pour toute partition disjointe, le coût optimal de permuter chaque partition est une borne plus serrée que Manhattan (partition en singletons). Bases additives l’exploitent.
Progression : Manhattan → Manhattan + conflit linéaire → walking distance → bases. Chaque étape strictement meilleure.
Pourquoi les grands plateaux en demandent plus
Manhattan vaut 75–90 % de la vraie distance sur 15-puzzle. ~65 % sur 24-puzzle. ~55 % sur 35-puzzle.
Plus le plateau grandit, plus conflits et structure « walking » comptent par rapport aux distances droites. Manhattan, qui ignore les deux, sous-estime plus grossièrement aux grandes tailles.
D’où la quasi-obligation des bases de motifs pour 24-puzzle et 35-puzzle. Manhattan reste très bien pour 15-puzzle et 8-puzzle mais perd trop d’information aux grandes tailles.
Intuition géométrique
Belle façon d’y penser : sur un plan, une seule tuile. L’ensemble des points qu’elle peut atteindre en k coups est un losange de côté k — points à distance Manhattan ≤ k. (En euclidien : un cercle de rayon k.)
Manhattan est la géométrie naturelle du déplacement en grille. Quand le mouvement est restreint aux pas de grille, Manhattan est la géométrie ; euclidien est sans rapport.
Ce que ça implique pour les développeurs
Pour un bouton d’indice en millisecondes :
- 3×3 — Manhattan + conflit linéaire suffit. A* explore des dizaines d’états ; finit en microsecondes.
- 4×4 — Manhattan + conflit linéaire est assez rapide pour un indice (un coup, pas la solution entière). Pour la solution complète optimale, walking distance.
- 5×5+ — Bases de motifs. Manhattan n’entre pas dans le budget temps d’un bouton.
Slide Puzzle utilise Manhattan + conflit linéaire pour le bouton d’indice 3×3 et 4×4, walking distance pour la calibration de difficulté 4×4, et une base 5+5+5+9 pour 5×5 et 6×6. Manhattan est la fondation de tout.
Intuition finale
L’heuristique de Manhattan est ce qui rend les taquins recherchables. Sans elle, A* et IDA* dégénèrent en BFS — qui ne termine pas un 15-puzzle dans la durée de vie de l’univers.
Une ligne de code qui transforme un problème intraitable en calcul en millisecondes. Ça vaut le coup de bien la comprendre.