La heurística de distancia de Manhattan es probablemente la heurística más usada en búsqueda heurística, jamás. Introducida informalmente en los 60 para el 15-puzzle, formalizada en el artículo de A* de 1968, sigue siendo lo primero que enseña cualquier libro de IA. Este artículo trata por qué funciona, qué hace bien y dónde deja de bastar.
La definición
Para un deslizante N×N, por cada ficha (ignorando el hueco) calcula:
distancia = | fila_actual − fila_objetivo | + | col_actual − col_objetivo |
Suma sobre todas las fichas. Esa suma es la distancia de Manhattan del tablero al objetivo.
¿Por qué «Manhattan»? Las calles de Manhattan son una cuadrícula. Para ir de una esquina a otra, andas tantas manzanas este-oeste más tantas norte-sur. No puedes atajar en diagonal. El total caminado es la distancia de Manhattan — también «distancia de taxi» o norma L¹.
Para una ficha, misma lógica: solo se mueve una celda en horizontal o vertical por movimiento, no en diagonal. El número mínimo de movimientos para ir de donde está a donde debe ir es la distancia en filas más la distancia en columnas.
Admisibilidad
A* exige que la heurística sea admisible: no debe sobrestimar nunca el número real de movimientos restantes. Si lo hace, A* puede cortar el camino óptimo y devolver subóptimo.
La distancia de Manhattan es admisible porque:
- Cada ficha debe viajar al menos su distancia en filas + columnas, ya que los movimientos son pasos unitarios.
- La suma sobre todas las fichas no se pasa, porque cada movimiento avanza exactamente una ficha exactamente una celda. (Mueve también el hueco, pero no lo contamos.)
- De hecho, la distancia real es al menos la Manhattan, porque a menudo hay que apartar fichas para que otras pasen — pero nunca menos.
Así Manhattan ≤ real. Admisible.
Consistencia
Propiedad más fuerte: consistencia, a veces llamada monotonía. Una heurística es consistente si para todo estado s y sucesor s' por movimiento m:
h(s) ≤ cost(m) + h(s')
En lenguaje claro: la heurística no puede caer más de uno con un solo movimiento.
La distancia de Manhattan es consistente porque un movimiento cambia su valor exactamente en +1 o −1. (Una ficha se mueve una celda; su contribución cambia ±1; las demás no.)
La consistencia importa porque garantiza que A* no reabre estados ya cerrados. Las implementaciones no necesitan tratar el caso inconsistente, lo que simplifica código y pruebas.
Por qué funciona tan bien en la práctica
Tres propiedades concretas:
Es barata. O(N²) por tablero — suma sobre fichas, cada contribución en tiempo constante. h(s) se calcula en microsegundos en cualquier ordenador moderno.
Lo bastante ajustada para podar profundo. En 15-puzzles, Manhattan promedia el 75–90 % de la distancia real. A* con una heurística así explora una fracción minúscula del espacio.
Compone bien con conflicto lineal. Sumar 2 movimientos por «conflicto lineal» (dos fichas en la misma fila, pertenecientes a esa fila, en orden incorrecto) da una heurística estrictamente más ajustada por coste marginal.
Dónde se queda corta
Manhattan trata las fichas como si pudieran atravesarse libremente. No pueden. El punto ciego más profundo:
Conflictos en columna o fila. Si las fichas 2 y 3 están ambas en la fila 1 pero en orden incorrecto, Manhattan les da sus distancias rectas y no nota nada. En realidad, una tiene que salir de la fila, otra pasar, y la primera volver. Mínimo 2 movimientos extra que Manhattan no ve. Conflicto lineal lo parchea.
Estructura «walking». Manhattan ignora cómo se relacionan las fichas dentro de una fila o columna cuando todas pertenecen a esa fila o columna. Una fila de cuatro fichas en permutación equivocada requiere varios «intercambios de fila» — una estructura que walking distance captura.
Interacciones de subconjuntos disjuntos. Para cualquier partición disjunta de fichas, el coste óptimo de permutar cada partición a su sitio es una cota inferior más ajustada que Manhattan (que es la partición en singletes). Bases aditivas de patrones lo explotan.
La progresión: Manhattan → Manhattan + conflicto lineal → walking distance → bases. Cada una mejora estricta.
Por qué los tableros mayores piden más
Manhattan promedia 75–90 % de la distancia real para el 15-puzzle. Para el 24-puzzle, ~65 %. Para el 35-puzzle, ~55 %.
Razón: con tableros más grandes, los conflictos y la estructura «walking» se vuelven más importantes relativo a las distancias rectas. Manhattan, que ignora ambos, subestima más groseramente.
Por eso las bases de patrones son esencialmente obligatorias para resolver el 24-puzzle y el 35-puzzle. Manhattan está bien para 15-puzzle y 8-puzzle, pero pierde demasiada información en tamaños mayores.
Intuición geométrica
Buena forma de pensar Manhattan: imagina una llanura con una ficha. El conjunto de puntos que la ficha puede alcanzar en k movimientos es un diamante de lado k — puntos a distancia Manhattan ≤ k. (El equivalente euclídeo sería un círculo de radio k.)
Manhattan es la geometría natural de la locomoción en cuadrícula. Cuando el modelo de movimiento está restringido a pasos en cuadrícula, Manhattan es la geometría; euclídea es irrelevante.
Qué implica para desarrolladores
Si escribes un botón de pista para una app y lo quieres en milisegundos:
- 3×3 — Manhattan + conflicto lineal sobra. A* explora decenas de estados; termina en microsegundos.
- 4×4 — Manhattan + conflicto lineal es lo bastante rápido para una pista (un movimiento, no la solución completa). Para la solución óptima completa, walking distance.
- 5×5+ — Bases de patrones. Manhattan no basta para caber en el presupuesto de tiempo de un botón.
Slide Puzzle usa Manhattan + conflicto lineal para el botón en 3×3 y 4×4, walking distance para la calibración de dificultad en 4×4, y una base 5+5+5+9 para calibrar 5×5 y 6×6. Manhattan es la base de todas.
Una intuición final
La heurística de Manhattan es lo que hace buscables los deslizantes. Sin ella, A* e IDA* degeneran en BFS — y BFS no termina un 15-puzzle en la vida del universo.
Esa heurística es la única línea de código que convierte un problema intratable en un cálculo de milisegundos. Vale la pena entenderla bien.