Conteúdo principal
Encontrando a rota
À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 do mapa do labirinto. O mapa mostra as conexões entre quadrados abertos adjacentes no labirinto (ou falta de conexões, se houver uma parede entre eles), e o problema é encontrar um caminho pelos quadrados pretos que leve o fantasma até o 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
Jogos de labirinto são divertidos, então vamos nos aprofundar em um. No nosso jogo, o personagem principal pode navegar a vários objetivos no labirinto
Como o jogador humano, você controla o personagem principal clicando no seu próximo objetivo no labirinto e o computador descobre como mover o personagem até ali. O objetivo é marcado com um retângulo vermelho com o rótulo "GOAL", e o personagem começa em seu primeiro objetivo, o quadrante inicial. Experimente jogar abaixo:
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.
Aqui está a ideia por trás do algoritmo que esse programa usa: mova 1 quadrado mais perto do objetivo (o local que o usuário clicou) em cada passo. 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:
- Comece no objetivo. Qual é a distância entre o objetivo e ele mesmo? Zero, então marque o objetivo com o número 0.
- 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.
- 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.
- 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.
- Continue marcando quadrados no labirinto para aumentar a distância do objetivo. Depois de marcar os quadrados com o número
Em algum momento, 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 que fica a apenas 12 movimentos de distância do objetivo. Então, o primeiro movimento é para o "sul". Ao sul desse quadrado está um 11. Sul novamente. Sul novamente até um 10. Então leste duas vezes até um 8. Norte até um 7, leste até um 6, então norte cinco vezes até um 2. Termine indo para o oeste uma vez, até um 1 e, finalmente, para o norte uma vez, até o objetivo.
Não vamos discutir nesse momento como implementar, de forma completa, 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.
Quer participar da conversa?
Como meu algoritmo irá definir para o personagem o que é parede e o que é caminho?
E como meu algoritmo saberá traçar a rota mais próxima? Que ferramentas matemáticas devo utilizar para definir esses critérios?(9 votos)
Paredes e caminhos possuem uma "propriedade" como explicado anteriormente, caminhos são brancos (vazios) e paredes são cinzas. Quem define isso é a própria pessoa que está escrevendo o algoritmo, mas nesse exemplo isso não tem importância. No caso de ferramentas o algoritmo pode ser facilmente escrito em qualquer linguagem de programação. E sobre o método como ele encontrará a rota mais próxima neste caso pode-se usar a soma dos pontos para saber qual caminha tem a menor soma, que neste caso deverá ser o caminho mais curto. Se a bola vai para a esquerda o algoritmo irá (por exemplo) somar 50 e se for para a direita irá somar 42, neste caso o caminho da direita é mais curto, entendeu?(42 votos)
onde vou aplicar esse conhecimento ?(4 votos)
voce pode desenvolver um jogo com um algoritmo dificil e bom que as pessoas gostem(7 votos)
- os algoritimos nao so servem para o dia dia mais pra outras coisas tambem quais sao elas?(16 votos)
Penso que o texto quis dizer Dia a dia no sentido de tarefas rotineiras, não englobando trabalho e estudos. Duas áreas que algoritmos podem ser bem úteis. Além claro, de contribuir para organizar nossa própria forma de pensar.(8 votos)
Existem dois parágrafos nesse artigo que, ou não foram traduzidos, ou quando foram, traduziram de maneira incompleta. Por gentileza verifiquem o 5º e o 10º parágrafos.(6 votos)- Por que no canto inferior direito se repetio 7 sendo que ele esta numa diagonal(6 votos)
No exemplo do labirinto, existe duas alternativas de caminhos iguais de valor 7, como o personagem escolhe qual dos dois a seguir, já que eles são iguais?(5 votos)
Nesse caso você precisa pensar em como resolver isso no seu código e precisa dizer explicitamente colocando algum tipo de critério, mas dependendo de como está seu código e que linguagem está usando ele pode escolher um lado "por defeito" (como se fala), quer dizer simplesmente porque a maneira de processar o algoritmo levou em conta um antes do outro e nem levou o outro em conta, mas pode ser que seu código simplesmente trave se você contar com isso.(2 votos)
- O problema foi só o inglês mas, deu pra traduzir...(3 votos)
Podem criar mais exemplos? Mas de qualquer forma gostei destes exemplos.(3 votos)
Legal o exercício, mas porque ele nunca escolhe o outro passo 7? tem alguma regra que diz para ele sempre ir para direção do objetivo?(3 votos)
Serve também para gerar a melhor rota para um técnico , em um sistema de força de venda.(2 votos)