busca de caminhos
BFS, DFS, Dijkstra e A* explorando uma grade que você desenha
Pergunta
Como quatro algoritmos de busca de caminhos se comportam na mesma grade? Desenhe paredes e lama, mova o início e o destino e avance pela busca em largura, pela busca em profundidade, por Dijkstra e por A*, observando a fronteira, as células exploradas e o caminho final. Tudo roda neste navegador; o experimento não está ligado a nenhum projeto.
Bancada
Teclado: as setas movem entre as células, Home e End vão ao início e ao fim da linha, Enter ou Espaço aplica a ferramenta escolhida.
Toque: toque numa célula para aplicar a ferramenta. Arrastar rola a página, então trace linhas com o mouse ou o teclado.
Fila, o mais antigo primeiro. Menor número de passos. Ignora pesos, então pode atravessar a lama.
- I início
- D destino
- # parede, não pode ser atravessada
- ~ lama, entrar nela custa 5
- f fronteira: descoberta, ainda não explorada
- · explorada
- * caminho final
O movimento reduzido está ativo: executar termina de uma vez, sem animação. Avançar continua explorando uma célula.
Desenhe paredes, mova o início e o destino, escolha um algoritmo e depois avance ou execute.
- Situação
- não iniciada
- Exploradas
- 0
- Fronteira
- 0
- Passos do caminho
- 0
- Custo do caminho
- 0
Menos passos: nenhum caminho tem menos passos. Menor peso: nenhum caminho custa menos. Sem lama, é a mesma coisa. Exploradas conta células, não tempo.
O que observar
- fronteira e exploradas
- A fronteira (f) guarda as células descobertas e ainda não exploradas. Explorar uma célula a move para as exploradas (·) e põe os vizinhos novos na fronteira. Os algoritmos só diferem em qual célula da fronteira escolhem em seguida.
- BFS
- Pega a célula mais antiga da fronteira, então cresce em anéis. Quando todo passo custa igual, o primeiro caminho que ele acha tem o menor número de passos. Ele não olha a lama: trace uma faixa de lama sobre a rota mais curta e ele passa direto.
- DFS
- Pega a célula mais nova da fronteira, então segue numa direção até bater num beco sem saída. Acha um caminho sempre que ele existe, mas não o mais curto: numa grade vazia, costuma dar voltas. Compare o tamanho do caminho com o do BFS.
- com e sem pesos
- Algoritmos sem pesos contam passos. Os com pesos somam o custo das células em que entram. Com lama, o menor número de passos e o menor custo podem ser caminhos diferentes, e só Dijkstra e A* otimizam o segundo.
- Dijkstra
- Explora sempre a célula de menor custo total até agora, e por isso a primeira vez que chega ao destino o custo é mínimo. Ele não sabe onde o destino está, então se espalha em todas as direções.
- A*
- Soma um palpite da distância restante (distância de Manhattan, que aqui nunca passa do custo real porque toda célula custa ao menos 1). Isso mantém o resultado ótimo e empurra a busca para o destino. Use comparar para ver que ele explora menos células.
- critério de desempate
- Os vizinhos são tentados na ordem cima, direita, baixo, esquerda. Prioridades iguais vão para a entrada que entrou primeiro; o A* prefere antes a célula mais perto do destino. Por isso a mesma grade sempre dá a mesma busca.
Limites
- O movimento é só para cima, direita, baixo e esquerda. Não há diagonais.
- A lama é o único peso, fixo em 5. Entrar numa célula custa o peso dela; a célula de início nunca é cobrada.
- As grades têm no máximo 30 × 16 células, e uma busca ou uma comparação termina rápido nelas.
- Células exploradas não são tempo de execução. O desempenho real depende das estruturas de dados, que esta página mantém propositalmente simples.
- As grades geradas se repetem pela semente, mas não há garantia de que tenham caminho.
Fidelidade
Uma implementação didática escrita para o Lab, com critérios de desempate fixos para que toda busca se repita igual. O movimento é em quatro direções e a lama é o único peso. Células exploradas não são medidas de tempo.