Este algoritmo implementa o algoritmo A* no mapa da Romênia para encontrar o caminho mais curto entre duas cidades.
- Felipe Pinto da Silva
Representa um nó no grafo.
name
(str): Nome do nó.parent
(Node, opcional): Nó pai. Padrão: None.distance
(int, opcional): Custo do nó inicial até o nó atual. Padrão: 0.heuristic
(int): Custo estimado do nó atual até o nó de destino.f
(int): Soma do custo e da heurística.
Define o mapa da Romênia com conexões entre cidades e distâncias.
Define uma heurística simples de distância em linha reta (aproximada).
node_name
(str): Nome do nó atual.
int
: Heurística estimada do nó atual até o nó de destino.
Executa o algoritmo A* para encontrar o caminho mais curto de um nó inicial para um nó de destino em um grafo.
graph
(dict): Grafo representando o mapa.start
(str): Nó inicial.goal
(str): Nó de destino.
list
: Caminho mais curto do nó inicial até o nó de destino.
# Define o mapa da Romênia
graph = romania_map()
# Define o ponto de partida e o ponto de chegada
start_point = 'Arad'
end_point = 'Bucharest'
# Executa o algoritmo A* para encontrar o caminho
path = a_star(graph, start_point, end_point)
-| Algoritmo A* |-
Origem: Arad
Destino: Bucharest
Caminho encontrado: ['Arad', 'Sibiu', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest']
- Python 3.x
- Módulo heapq
- Módulo os