rota :- a_estrela([['Arad']],'Bucharest', Rota),
write('Caminho: '),
write(Rota),
write(', com custo de: '),
calcula_custo(Rota, Custo),
write(Custo),
write('\n').
calcula_custo([Nodo1,Nodo2],Custo):-
estrada(Nodo1,Nodo2,Custo).
calcula_custo([Nodo1, Nodo2|Caminho],Custo):-
estrada(Nodo1,Nodo2,Custo1),
calcula_custo([Nodo2|Caminho],Custo2),
Custo is Custo1 + Custo2.
a_estrela([[Objetivo|Rota]|_],Objetivo,Rota_final):-
reverse([Objetivo|Rota], Rota_final).
a_estrela([Rota|Lista],Objetivo,Rota_final) :-
expandir(Rota,Expansao_caminho),
append(Lista,Expansao_caminho,Novo_caminho),
classifica(Novo_caminho,Objetivo,Lista_classificada),
a_estrela(Lista_classificada,Objetivo,Rota_final).
classifica([],_,[]).
classifica(Lista,Objetivo,[Menor_caminho|Lista_classificada]):-
min(Lista,Objetivo,Menor_caminho,Novo_caminho),
classifica(Novo_caminho,Objetivo, Lista_classificada).
min([Caminho1|Lista],Objetivo,Caminho2,[Caminho1|Novo_caminho]):-
min(Lista,Objetivo,Caminho2,Novo_caminho),
f(Caminho1,Objetivo,F1),
f(Caminho2,Objetivo,F2),
F2<F1,!.
min([Rota|Lista],_,Rota,Lista).
expandir([Nodo|Rota],Expansao_caminho) :-
findall([Novo_nodo,Nodo|Rota],
(estrada(Nodo,Novo_nodo,_), \+ member(Novo_nodo,[Nodo|Rota])),
Expansao_caminho).
h([Nodo|_],Objetivo,H) :- distancia(Nodo,Objetivo,H).
f(Rota,Objetivo,F) :-
inverte_custo(Rota,G),
h(Rota,Objetivo,H),
F is G+H.
inverte_custo([A,B],Custo) :-
estrada(B,A,Custo).
inverte_custo([A,B|T],Custo) :-
estrada(B,A,Custo1),
inverte_custo([B|T],Custo2),
Custo is Custo1+Custo2.
estrada('Arad','Zerind',75).
estrada('Arad','Sibiu',140).
estrada('Arad','Timisoara',118).
estrada('Bucharest','Fagaras',211).
estrada('Bucharest','Pitesti',101).
estrada('Bucharest','Giurgiu',90).
estrada('Bucharest','Urziceni',85).
estrada('Craiova','Dobreta',120).
estrada('Craiova','Rimnicu',146).
estrada('Craiova','Pitesti',138).
estrada('Dobreta','Mehadia',75).
estrada('Dobreta','Craiova',120).
estrada('Eforie','Hirsova',86).
estrada('Fagaras','Sibiu',99).
estrada('Fagaras','Bucharest',211).
estrada('Giurgiu','Bucharest',90).
estrada('Hirsova','Urziceni',98).
estrada('Hirsova','Eforie',86).
estrada('Iasi','Neamt',87).
estrada('Iasi','Vaslui',92).
estrada('Lugoj','Timisoara',111).
estrada('Lugoj','Mehadia',70).
estrada('Mehadia','Lugoj',70).
estrada('Mehadia','Dobreta',75).
estrada('Neamt','Iasi',87).
estrada('Oradea','Zerind',71).
estrada('Oradea','Sibiu',151).
estrada('Pitesti','Rimnicu',97).
estrada('Pitesti','Craiova',138).
estrada('Pitesti','Bucharest',101).
estrada('Rimnicu','Sibiu',80).
estrada('Rimnicu','Pitesti',97).
estrada('Rimnicu','Craiova',146).
estrada('Sibiu','Arad',140).
estrada('Sibiu','Oradea',151).
estrada('Sibiu','Fagaras',99).
estrada('Sibiu','Rimnicu',80).
estrada('Timisoara','Arad',118).
estrada('Timisoara','Lugoj',111).
estrada('Urziceni','Bucharest',85).
estrada('Urziceni','Hirsova',98).
estrada('Urziceni','Vaslui',142).
estrada('Vaslui','Iasi',92).
estrada('Vaslui','Urziceni',142).
estrada('Zerind','Arad',75).
estrada('Zerind','Oradea',71).
distancia( Cidade,'Bucharest',H):-
distancia( Cidade,H).
distancia('Arad' ,366).
distancia('Bucharest', 0).
distancia('Craiova' ,160).
distancia('Dobreta' ,242).
distancia('Eforie' ,161).
distancia('Fagaras' ,178).
distancia('Giurgiu' , 77).
distancia('Hirsova' ,151).
distancia('Iasi' ,266).
distancia('Lugoj' ,244).
distancia('Mehadia' ,241).
distancia('Neamt' ,234).
distancia('Oradea' ,380).
distancia('Pitesti' , 98).
distancia('Rimnicu' ,193).
distancia('Sibiu' ,253).
distancia('Timisoara',329).
distancia('Urziceni' , 80).
distancia('Vaslui' ,199).
distancia('Zerind' ,374).