Às vezes, problemas que parecem muito diferentes acabam sendo similares quando você pensa em como solucioná-los. O que o Pac-Man, a família real britânica e uma viagem de carro até Orlando têm em comum? Todos eles envolvem problemas de localização de rotas ou caminhos de busca:
  • Como o atual Príncipe William está relacionado ao Rei William III, que fundou o College of William and Mary em 1693?
  • Que caminho um fantasma deve seguir para alcançar o Pac-Man o mais rápido possível?
  • Qual é a melhor rota entre Dallas, no Texas, e Orlando, na Flórida?
Precisamos de algumas informações para responder a qualquer uma dessas perguntas.
Por exemplo, uma árvore genealógica da família real britânica deve mostrar as conexões entre pessoas com parentesco direto. O Príncipe William é filho de Charles Philip Arthur Windsor. Charles é filho da Rainha Elizabeth II. O problema é encontrar uma cadeia curta na árvore genealógica que conecte o Príncipe William e William III usando essas conexões diretas. Como você pode ver na árvore abaixo, podemos precisar de algumas conexões.
Para o Pac-Man, precisamos de um mapa do labirinto. This map shows connections between adjacent open squares in the maze—or lack of connections, if there is a wall in between—and the problem is to find a path along black squares that leads the ghost to Pac-Man.
Para encontrar uma rota entre Dallas e Orlando, podemos usar um mapa dos Estados Unidos, mostrando as conexões (estradas) entre cidades próximas. Não existe nenhuma estrada que ligue Dallas diretamente a Orlando, mas várias sequências de estradas o fazem.

Explorando um labirinto

Vamos examinar mais de perto o Pac-Man, um jogo de computador no qual o personagem principal é controlado clicando-se em destinos no labirinto. O jogo está abaixo: tente clicar em algumas posições para mover o personagem, representado pelo círculo amarelo, até o objetivo, representado pelo quadrado vermelho.
Você percebeu como o personagem se moveu até o objetivo? Para fazer isso acontecer, o programa precisa determinar o conjunto exato de movimentos que o personagem deve realizar para chegar ao ponto onde o usuário clicou, e então animar esses movimentos. Podem existir muitos caminhos para o personagem seguir, e o programa precisa escolher o melhor entre eles.
Antes de decidir por um algoritmo, as regras do movimento precisam primeiro ser estabelecidas: as paredes são feitas de quadrados cinzentos, e as posições onde é permitido andar estão vazias. Em cada etapa, o personagem pode se mover de um quadrado para outro quadrado adjacente. O personagem, como a torre do xadrez, não pode se mover na diagonal.
Here's the idea behind the algorithm that this program uses: move 1 square closer to the goal—the place the user clicked on—in each step. Mas o que significa "mais perto do objetivo"? Viajar em linha reta até o objetivo muitas vezes fará com que o personagem dê de cara com um muro. O algoritmo precisa determinar quais dos quadrados circundantes estão de fato "mais perto do objetivo", e podemos fazer isso atribuindo um "custo" a cada quadrado, que representa o número mínimo de movimentos que o personagem teria que fazer para chegar daquele vértice até o objetivo. Aqui está um algoritmo que atribui um custo a cada quadrado:
  1. Comece no objetivo. Qual é a distância entre o objetivo e ele mesmo? Zero, então marque o objetivo com o número 0.
  2. Encontre todos os quadrados no labirinto que estão a exatamente um movimento de distância do objetivo. Marque-os com o número 1. Neste labirinto, se o objetivo for o quadrado da saída, então há apenas um quadrado a exatamente um movimento de distância.
  3. Agora, encontre todos os quadrados no labirinto que estão a exatamente dois movimentos de distância do objetivo. Esses quadrados estão a um movimento dos marcados com 1 e ainda não foram marcados. Marque-os com o número 2.
  4. Agora, encontre todos os quadrados no labirinto que estão a exatamente três movimentos de distância do objetivo. Esses quadrados estão a um movimento dos marcados com 2 e ainda não foram marcados. Marque-os com o número 3.
  5. Continue marcando quadrados no labirinto para aumentar a distância do objetivo. Depois de marcar os quadrados com o número k k , marque com o número k+1 k+1 todos os quadrados que estão a um movimento de distância daqueles marcados com k k e ainda não foram marcados.
Eventualmente, o algoritmo marcará o quadrado onde o personagem está. O programa pode então encontrar um caminho até o objetivo, escolhendo uma sequência de quadrados que começa na posição inicial do personagem, de forma que os números nos quadrados estejam sempre diminuindo no processo. Se você entender o número como a altura do quadrado, seria como descer uma ladeira.
Você pode brincar com o algoritmo de marcação abaixo - clique em "Restart algorithm" para recomeçar.
E se o usuário estivesse tentando ir do quadrado inicial até o objetivo? Usando o algoritmo de marcação de quadrados, o quadrado inicial está a 13 movimentos de distância do objetivo. Aqui está uma figura que mostra as conexões entre as possíveis posições do personagem. O início, o objetivo, e a distância mais curta de cada posição a partir do objetivo:
Há um quadrado imediatamente ao sul do início (linha 4, coluna 3), que está a apenas 12 movimentos do objetivo. Então o primeiro movimento é "sul". Ao sul daquele quadrado há um 11. Sul de novo. Sul de novo para um 10. Então, leste para um 9. Leste mais duas vezes para chegar a um 7, então norte cinco vezes para chegar a um 2. Termine indo para oeste uma vez, para um 1, e finalmente para norte uma vez, chegando ao objetivo.
Não vamos discutir nesse momento exatamente como implementar este algoritmo de busca no labirinto, mas você pode achar divertido pensar em como você poderia representar o labirinto e o personagem usando JavaScript, e como você pode implementar o algoritmo.

Este conteúdo é uma colaboração entre os professores Thomas Cormen e Devin Balkcom da Dartmouth Computer Science e a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.
Carregando