A heurística da distância de Manhattan é a heurística mais usada em busca heurística, talvez de sempre. Introduzida informalmente nos anos 1960 para o 15-puzzle, formalizada no artigo do A* de 1968, continua a ser a primeira coisa que qualquer manual de IA ensina. Este artigo é sobre por que funciona, no que se sai bem e onde deixa de chegar.
A definição
Para um quebra-cabeça deslizante N×N, para cada peça (ignore o vazio), calcule:
distância = | linha_atual − linha_alvo | + | col_atual − col_alvo |
Some sobre todas as peças. Essa soma é a distância de Manhattan do tabuleiro atual em relação ao alvo.
Por que "Manhattan"? As ruas de Manhattan formam uma grelha regular. Para ir de um quarteirão a outro, andam-se tantos quarteirões este-oeste mais tantos norte-sul. Não se pode cortar em diagonal. O número total de quarteirões andados é a distância de Manhattan — também chamada distância do táxi ou norma L¹.
Para uma peça, a mesma lógica: pode mover-se na horizontal ou na vertical uma célula por movimento, mas não em diagonal. O número mínimo de movimentos para ir de onde está para onde precisa de estar é a distância em linha mais a distância em coluna.
Admissibilidade
O A* exige que a heurística seja admissível: nunca deve superestimar o número real de movimentos restantes. Se a heurística superestimar, o A* pode cortar o caminho ótimo antecipadamente e devolver uma solução subótima.
A distância de Manhattan é admissível porque:
- Cada peça individual tem de percorrer pelo menos a sua distância em linha + em coluna, porque os movimentos são passos unitários em linha ou coluna.
- Somar sobre todas as peças não ultrapassa, porque cada movimento avança exatamente uma peça em exatamente uma célula. (Também move o vazio, mas o vazio não conta.)
- De facto, a distância real é pelo menos a distância de Manhattan, porque as peças muitas vezes têm de ser afastadas para outras passarem — mas nunca menos.
Logo, Manhattan ≤ real. Admissível.
Consistência
Uma propriedade mais forte: consistência, por vezes chamada monotonicidade da heurística. Uma heurística é consistente se, para cada estado s e cada sucessor s' por um movimento m:
h(s) ≤ custo(m) + h(s')
Em português corrente: o valor da heurística não pode cair mais de um por cada movimento feito.
A distância de Manhattan é consistente porque um único movimento altera a distância de Manhattan exatamente em +1 ou −1. (Uma peça move-se uma célula, pelo que a sua contribuição para a heurística muda em ±1; as contribuições das restantes não mudam.)
A consistência importa porque garante que o A* nunca reabre um estado que já tenha fechado. As implementações não precisam de tratar o caso inconsistente, o que simplifica o código e as demonstrações.
Por que funciona tão bem na prática
Três propriedades concretas:
É barata de calcular. O(N²) por tabuleiro — soma sobre todas as peças, cada contribuição em tempo constante. Calcular h(s) leva microssegundos em qualquer computador moderno.
É apertada o suficiente para podar em profundidade. Para 15-puzzles, o valor da heurística de Manhattan ronda em média 75–90% da distância real. O A* com uma heurística tão apertada explora uma fração mínima do espaço de estados.
Compõe-se bem com o conflito linear. Adicionar 2 movimentos por "conflito linear" (duas peças na mesma linha, ambas pertencentes a essa linha, mas na ordem errada) dá uma heurística estritamente mais apertada a um custo computacional marginal.
Onde fica curta
A distância de Manhattan trata as peças como se pudessem atravessar-se livremente. Não podem. O maior ponto cego:
Conflitos numa coluna ou linha. Se as peças 2 e 3 estão ambas na linha 1 mas na ordem errada, Manhattan dá-lhes as suas distâncias em linha reta e não nota nada. Na verdade, uma delas tem de ser levantada para fora da linha, deixar a outra passar e voltar a entrar. São pelo menos 2 movimentos extra que Manhattan não vê. O conflito linear corrige isto.
Estrutura "de marcha". Manhattan ignora como as peças se relacionam dentro de uma linha ou coluna quando todas pertencem a essa linha ou coluna. Uma linha com quatro peças na permutação errada exige várias "trocas de linha" — uma estrutura que a walking distance captura.
Interações entre subconjuntos disjuntos. Para qualquer partição disjunta das peças, o custo ótimo de permutar cada partição para o sítio é um limite inferior mais apertado do que Manhattan (que é a partição em singletons). As bases de padrões aditivas exploram isto.
A progressão é: Manhattan → Manhattan + conflito linear → walking distance → bases de padrões. Cada uma é uma melhoria estrita.
Por que tabuleiros maiores precisam de mais
A distância de Manhattan ronda em média 75–90% da distância real para o 15-puzzle. Para o 24-puzzle, ronda os 65%. Para o 35-puzzle, cerca de 55%.
A razão: à medida que os tabuleiros crescem, os conflitos de peças e a "estrutura de marcha" tornam-se mais importantes relativamente às distâncias em linha reta. A distância de Manhattan, que ignora ambas, subestima de forma mais grave em tabuleiros maiores.
É por isso que as bases de padrões são essencialmente obrigatórias para a resolução do 24-puzzle e do 35-puzzle. A heurística de Manhattan está bem para o 15-puzzle e para o 8-puzzle, mas perde demasiada informação em tamanhos maiores.
Intuição geométrica
Uma boa forma de pensar na distância de Manhattan: imagine um plano com uma peça em cima. O conjunto de pontos que a peça alcança em k movimentos é um losango de lado k — pontos a distância de Manhattan ≤ k. (O equivalente euclidiano seria um círculo de raio k.)
A distância de Manhattan é a geometria natural de locomoção em grelha. Quando se tem um modelo de movimento restrito a passos de grelha, a distância de Manhattan é a geometria; a distância euclidiana é irrelevante.
O que isto significa para quem desenvolve apps
Se está a escrever um botão de dica para uma app de quebra-cabeças deslizantes e quer que funcione em milissegundos:
- 3×3 — Manhattan + conflito linear chega de sobra. O A* explora dezenas de estados; termina em microssegundos.
- 4×4 — Manhattan + conflito linear é rápido o suficiente para uma dica (um movimento, não a solução ótima completa). Para a solução ótima completa, walking distance é a escolha certa.
- 5×5+ — Bases de padrões. Manhattan não chega para caber no orçamento de tempo de um botão de dica.
O Slide Puzzle usa Manhattan + conflito linear para o botão de dica de 3×3 e 4×4, walking distance para a calibração de dificuldade do 4×4, e uma base de padrões 5+5+5+9 para a calibração de 5×5 e 6×6. A heurística de Manhattan é a fundação de todas elas.
Uma intuição final
A heurística da distância de Manhattan é o que torna os quebra-cabeças deslizantes pesquisáveis. Sem ela, o A* e o IDA* degenerariam em BFS — e o BFS não termina no 15-puzzle dentro do tempo de vida do universo.
Essa heurística é a única linha de código que transforma um problema intratável num cálculo de milissegundos. Vale a pena compreendê-la bem.