Um passo de Dijkstra o algoritmo A* (leia: “uma estrela”). Em termos de pathfinding, Dijkstra o algoritmo vai querer experimentar cada caminho e cada vértice para encontrar o caminho mais curto entre o seu ponto de partida e de destino, enquanto A* tem um atributo extra, uma heurística, que deve permitir que ele encontre o caminho mais curto, sem necessidade de verificar cada caminho e o vértice. Cada algoritmo tem seus casos de uso, mas geralmente falando, tanto Dijkstra e a * podem encontrar o caminho mais curto, mas a* vai fazê-lo mais rápido.
eu recomendaria saber um pouco sobre o algoritmo de Dijkstra antes de entrar neste artigo, pois há muitos pontos de comparação. Ou melhor ainda, leia o meu último artigo sobre o assunto! https://medium.com/swlh/pathfinding-dijkstras-algorithm-65e71c346629
i’m going to need to set-up a few things for my examples, plus give a definition of what a heuristic is. Para começar, deixe-me mostrar-lhe o tipo de gráfico que eu quero usar para meus exemplos.
isto é um pouco abstracto, mas eu quero usar uma placa axadrezada como o meu gráfico, e quero permitir o movimento entre os seus quadrados. Se eu sobrepor o grafo equivalente com vértices e arestas, ele deve parecer algo assim.
vamos tomar o quadrado central/vértice, E, por exemplo. Tem oito vértices vizinhos, então podemos mover para cima, para baixo, para a esquerda, para a direita, e em todas as combinações diagonais de cada um. E isso é realmente tudo o que eu estava tentando configurar aqui: eu vou usar um tabuleiro de xadrez, e eu vou permitir o movimento em oito direções. Um pouco demorado, mas agora vamos começar a olhar para o movimento e o custo do movimento.começando de forma simples, vou dizer que subir, descer, esquerda e direita tem um custo de movimento de 1. O tabuleiro está a ficar ocupado, então vou extrair o gráfico, e adicionar esse custo de movimento como pesos de borda.
se estes pesos são distâncias, e se as relações e vizinhos são dispostos assim, então a geometria pode nos dizer sobre o custo dos movimentos diagonais. Usando o Pythagorean Theorum, devemos começar √(12 + 12) = √2, que é cerca de 1.41421356237… que não é um número muito bom para trabalhar. Então, vou roubar uma ideia (e citar minhas fontes!), e multiplicar e arredondar os custos para baixo. Para ambos os tipos de movimento, vou multiplicá-los por dez, e depois truncar as casas decimais. Isto nos dará os custos finais de 10 para os movimentos acima, abaixo, esquerda e direita, e 14 para os movimentos diagonais.
heurísticas
sinto que estes são difíceis de definir, por isso vou começar com a linha de abertura da Wikipédia sobre o assunto:
Em ciência da computação, inteligência artificial e matemática de otimização, uma heurística (do grego εὑρίσκω “eu encontrar, descobrir”) é uma técnica projetada para a solução de um problema mais rapidamente quando os métodos clássicos são muito lentas, ou para encontrar uma solução aproximada quando clássico métodos não conseguem encontrar qualquer solução exata. Isso é conseguido através do comércio otimalidade, Completude, precisão ou precisão para a velocidade. De certa forma, pode ser considerado um atalho.
isso é útil? Percebeste? Porque não percebo. Quer dizer, eu meio que entendo, e é uma descrição precisa, mas se esta foi a primeira vez que você ouviu falar sobre um heurístico, eu não tenho certeza de que você obteria a imagem completa do que heurística são a partir disto. Talvez se eu te falar sobre o heurístico da descoberta do caminho, tu tenhas uma melhor compreensão.
com o algoritmo de Dijkstra, o foco foi em um valor: a menor distância do índice inicial. O que, Pensando bem, é um pouco estranho. Você tem este algoritmo tentando encontrar novos, caminhos mais curtos para algum destino, mas seu foco é sempre em onde ele começou. Imagina alguém a ir às compras, mas a andar para trás o caminho todo, a tentar vigiar a casa deles até chegarem à loja. Na vida real, isto provavelmente não funcionaria, mas talvez se lhes desse tempo para irem por toda a cidade, talvez resultasse.
saindo desta analogia Pateta, A* é diferente da de Dijkstra porque sugere virar – se e andar para a frente. A*, como Dijkstra’s, também mantém o controle de quão longe de casa está, mas sua característica única é que ele mantém o controle de quão longe está de seu destino, também. Ao dar seu próximo passo, Dijkstra vai olhar para qual caminho é atualmente o mais curto, mas A* VAI um passo mais longe e também considera se esse passo está movendo-o mais perto de seu objetivo. Mais simplesmente, A* tem uma estimativa aproximada de sua distância restante para seu objetivo, e quando essa estimativa se aproxima de zero, ela sabe que está se movendo na direção certa. Este é o heurístico que vamos usar em nossos exemplos.
passar através do algoritmo
Este vai ser um exemplo bastante simples, mas deve mostrar-lhe o fluxo básico e repetição do algoritmo. Vou certificar-me de fornecer links em minhas referências a outros exemplos mais complicados, mas este deve ser um bom primer para aqueles. Vou usar um set-up semelhante a como eu demonstrado Dijkstra.
Mais uma diferença entre Dijkstra e a* é que Dijkstra começa a looping imediatamente, mas A* tem que fazer um pequeno set-up para o seu vértice inicial. Então vamos fazer isso agora, e ter uma idéia de como a mesa vai funcionar.
Primeiro, nós vamos adicionar Um conjunto Aberto. Segundo, vamos descobrir A distância de A desde o início. Naturalmente, a distância de A A A é zero, então isso será adicionado à mesa, e eu terei que ser o número no canto superior esquerdo do quadrado de A. Terceiro, vamos determinar a distância heurística. Podemos fazer isso de várias maneiras, tudo o que é importante é que medamos essa distância da mesma maneira para cada quadrado. Vou usar uma distância” como o corvo voa ” para todas as distâncias heurísticas, o que significa que posso usar o teorema de Pitágoras novamente. Neste caso, vamos calcular √(202 + 302), e descobrir que A é uma distância de 36.0555127546… de L (EU arredondarei as casas decimais para o décimo mais próximo para economizar espaço). Vou adicionar isto à mesa e colocá-lo no canto superior direito do quadrado A. Finalmente, a soma. Vou adicionar a distância mais curta do início à distância heurística, adicioná-la à mesa, e colocá-la no centro da Praça A.
Este é o nosso ponto de partida, e agora podemos olhar para os vizinhos de A, e adicionar os seus valores à tabela.
Primeiro, vamos adicionar B, E, e F para o conjunto Aberto. Em seguida, podemos encontrar as distâncias mais curtas desde o início, e como tudo é um passo desde o início, serão apenas 10 para B E E, e 14 para a diagonal mover-se para F. para a distância heurística, vamos usar o teorema de Pitágoras de cada quadrado para o vértice final. Finalmente, vamos obter suas somas, e adicionar “A” a cada uma de suas colunas de vértices anteriores.
neste ponto, fizemos tudo o que precisávamos com A, então ela será movida para o conjunto fechado, e precisaremos de um novo vértice atual. Para determinar qual vértice deve ser examinado em seguida, vamos olhar para o conjunto aberto, e encontrar o vértice que tem a menor soma. Neste momento, isso é F com uma soma de 36.1. Então, vamos torná-lo o vértice atual, e começar a trabalhar os valores para seus vizinhos.
F possui oito vizinhos, mas apenas cinco estão indo para ser alterado aqui. Em primeiro lugar, A está no cenário fechado agora, então não pode ser mudado agora. Para os restantes sete, vamos adicioná-los ao conjunto aberto (a menos que eles já são parte dele), e então vamos trabalhar em suas distâncias desde o início. Isto vai funcionar muito como o algoritmo de Dijikstra, e vamos adicionar a distância de F desde o início até a distância de cada um de seus vizinhos de F. em nossa mesa, a distância de F desde o início é de 14, Então vamos preencher 14 + 10=24 ou 14 + 14 = 28 para estes. No entanto, B E e já têm distâncias mais curtas para o início, de modo que seus registros de tabela não são atualizados. Isso deixa cinco vértices que serão atualizados, com C, I, E K recebendo 28, E G E J recebendo 24 por sua distância desde o início. Em seguida, use o teorema de Pitágoras para cada uma dessas distâncias heurísticas dos vértices, em seguida, calcular suas somas, e finalmente adicionar “F” à coluna de vértices anterior para os vértices que foram atualizados.
F está completo e será movido para o conjunto fechado, e um novo vértice atual será escolhido com base no qual o vértice no conjunto aberto tem a menor soma. É muito perto ,mas K é um décimo menor (e sim, isso é por causa de uma diferença de arredondamento, mas neste caso, acaba por ser um bom desempate). K será o novo vértice a examinar, então vamos começar por olhar para seus vizinhos.
K tem seis vizinhos, três dos quais já estão no conjunto Aberto, portanto, os dois últimos H e L serão adicionados para o Aberto, bem como definir. Vamos calcular as distâncias desde o início. A distância do início de K é de 28, Então vamos trabalhar com 28 + 10 = 38 Para G, J, E L, e 28+14=42 para H. No entanto, G E J já têm distâncias menores para começar, de modo que eles não serão atualizados. Vamos encontrar as distâncias heurísticas para cada um, calcular suas somas, e adicionar “K” a cada vértice anterior que foi atualizado.
K está completo e movido para o conjunto fechado, e o vértice seguinte no aberto com a menor soma é L, o nosso destino!
Agora, o que L é o atual vértice, o algoritmo termina, e nós podemos usar a nossa tabela para rastrear o caminho de volta para o início:
- L anteriores vértice é K
- K anterior vértice é F
- F’ anterior vértice é Um, o vértice de partida.
Então, isso significa que o caminho mais curto é Uma > F > K > L.
analisando os resultados
em comparação com o algoritmo de Dijkstra, A * deixou uma grande confusão atrás dele. Vejamos alguns pontos. Começando, olhe para o vértice C e sua distância para o início: 28. Isso parece estranho porque A E C são apenas dois movimentos horizontais de distância um do outro, então a distância mais Curta deve ser 20. Neste momento, c parece pensar que seu caminho mais curto para A é dois movimentos diagonais através de F.
Quando o algoritmo de Dijkstra termina, ele deve fornecer uma tabela muito completa de distâncias do ponto de partida. Inversamente, a tabela de A*tem valores errados, e está completamente faltando vértice D. Mas obteve a mesma resposta que Dijkstra teria, e fez muito mais rápido. Dijkstra teria querido olhar para todos os 12 vértices antes de declarar que encontrou o caminho mais curto; a * só precisava olhar para 4 antes de encontrar o caminho certo. Esta mudança de velocidade deve-se à heurística que estávamos a usar: sempre que podíamos, queríamos estar a fechar a distância com o nosso destino. Se voltarmos à definição da Wikipédia para heurística, A* trocou Completude por velocidade.vamos tentar outro pequeno exemplo, mas com uma obstrução no caminho para o destino.
o ponto de Partida é o vértice superior esquerdo, e Um* está a tentar encontrar o caminho mais curto para o vértice inferior direito. Os quadrados negros representam uma lacuna no grafo e não podem ser atravessados. Se a* está seguindo sua heurística de “sempre chegar mais perto do Destino”, esses quadrados negros vão levá-lo a um beco sem saída.
neste ponto, A* vontade de olhar para os mais pequenos montantes, quais serão os quadrados um pouco abaixo e à direita do vértice de partida. A * irá explorar ambos os caminhos, mas o caminho para baixo irá correr para outro beco sem saída, e o caminho para a direita irá encontrar um caminho em torno dos quadrados Negros. Pode ser um pouco diferente, mas vamos assumir que foi assim que A* lidou com este cenário. Mesmo quando ele foi puxado para becos sem saída, ele foi capaz de voltar e encontrar outro caminho, e ele não precisava olhar para cada vértice (o vértice muito superior direito foi ignorado novamente). Isso significa que quando uma estrela* está correndo no seu pior absoluto, é basicamente tão rápido quanto o desempenho normal de Dijkstra. Cada algoritmo tem casos de uso perfeitamente válidos, mas em termos de pathfinding e encontrar os caminhos mais curtos, a* é a melhor escolha.