a star algorithm

Algoritmo A*

Sobre

• Algoritmo guloso
• encontra o menor caminho de maneira super eficiente.
• Requer definição de uma função heurística h(x), que subestima a distância entre o vértice xeo vértice destino.
• A ideia por trás do A* é transformar o grafo em uma árvore
• A raiz da árvore é o nó origem
• Essa árvore será estendida a partir de suas folhas (que no começo é só o nó origem), usando o grafo como referência
• Não vai expandir todas as possibilidades, apenas as que parecerem mais promissoras

---

? Como saber se uma possibilidade é promissora?

• Através da função F(x) = g(x) + h(x)
  • Que é uma função heurística
    • g(x) é o custo para, a partir da origem, chegar até o nó x
    • h(x) é uma função heurística para a estimativa do custo do próximo nó
  • Sempre olhamos as possibilidades de expansão da árvore e calculamos o valor de F(x)
    • Adicionamos o nó que possui o menor F(x) dentre os que encontramos

---

• OA* é o algoritmo mais eficiente para caminhos mínimos em grafos
• Entretanto, ele limitações severas
  • É preciso definir uma h(x) que seja admissível: ela nunca irá retornar um valor maior do que a distância real de x até y
  • Se h(x) for admissível, mas subestimar demais a distância real, o algoritmo fica super ineficiente. Se h(x) não for admissível, o algoritmo poderá não encontrar o caminho mínimo

---

? Complexidade

• A complexidade depende diretamente da função h(x) usada.
• No pior caso, a quantidade de nós explorados é exponencial no tamanho do menor caminho, mas tem complexidade polinomial se h∗(x)−h(x)≤O(logh∗(x)).

---

? Quando é bom usar?

• Grafos onde se pode subestimar a distância entre dois vértices, como em mapas
• A menor distância entre dois pontos é uma reta, mas provavelmente a distância real será maior que isso

---

? Qual é o caminho mínimo nesse caso?

---

Executar o projeto

Resultado

---

??‍ Autores

Bia Chacon

---

Licença

Este projeto está sob o MIT. Veja aqui LICENSE para mais informações.

---