/* Algoritmo A*  */

rota :- a_estrela([[joinville]],lages, Rota), nl,
        write('Caminho:'),
        imprima(Rota), nl,
        write('Distância de: '),
        g(Rota, Custo),
        write(Custo), nl.
rota.

todas_rotas :- rota, fail.

imprima([]):- !.
imprima([lages|_]):-cidade(lages),!.
imprima([Cabeca|Cauda]):- !,cidade(Cabeca), write(','), imprima(Cauda).
imprima(Arg):- cidade(Arg).

cidade(bal_camboriu) :- write(' Balneário Camboriú').
cidade(blumenau)     :- write(' Blumenau').
cidade(brusque)      :- write(' Brusque').
cidade(caçador)      :- write(' Caçador').
cidade(garuva)       :- write(' Garuva').
cidade(itajai)       :- write(' Itajaí').
cidade(jaragua)      :- write(' Jaraguá do Sul').
cidade(joinville)    :- write(' Joinville').
cidade(mafra)        :- write(' Mafra').
cidade(rio_do_sul)   :- write(' Rio do Sul').
cidade(sao_bento)    :- write(' São Bento do Sul').
cidade(lages)        :- write(' Lages').

g([Nodo1,Nodo2],Custo):-
        conexao(Nodo1,Nodo2,Custo).

g([Nodo1, Nodo2|Caminho],Custo):-
        conexao(Nodo1,Nodo2,Custo1),
        g([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]):-
        caminho_minimo(Lista,Objetivo,Menor_caminho,Novo_caminho),
        classifica(Novo_caminho,Objetivo, Lista_classificada).

caminho_minimo([Caminho1|Lista],Objetivo,Caminho2,[Caminho1|Novo_caminho]):-
        caminho_minimo(Lista,Objetivo,Caminho2,Novo_caminho),
        f(Caminho1,Objetivo,F1),
        f(Caminho2,Objetivo,F2),
        F2<F1,!.

caminho_minimo([Rota|Lista],_,Rota,Lista).

expandir([Nodo|Rota],Expansao_caminho) :-
        findall([Novo_nodo,Nodo|Rota], 
                (conexao(Nodo,Novo_nodo,_), \+ member(Novo_nodo,[Nodo|Rota])), 
                Expansao_caminho).

/* Funções heurísticas */

h([Nodo|_],Objetivo,H) :- distancia(Nodo,Objetivo,H). 

f(Rota,Objetivo,F) :-                   
        g(Rota,G),             /* calcula o custo g(n) */
        h(Rota,Objetivo,H),    /* calcula a função heurística h(n) */
        F is G+H.              /* F = G + H */

/* Um mapa com as distâncias das cidades */

conexao(A,B,D) :- estrada(A,B,D).
conexao(A,B,D) :- estrada(B,A,D).

estrada(bal_camboriu, brusque,    43).
estrada(bal_camboriu, itajai,      9).
estrada(blumenau,     brusque,    40).
estrada(blumenau,     itajai,     47).
estrada(blumenau,     jaragua,    67).
estrada(blumenau,     rio_do_sul, 89).
estrada(caçador,      jaragua,   301).
estrada(caçador,      mafra,     204).
estrada(garuva,       joinville,  36).
estrada(garuva,       sao_bento,  74).
estrada(itajai,       joinville,  94).
estrada(jaragua,      joinville,  53).
estrada(jaragua,      sao_bento,  45).
estrada(joinville,    sao_bento,  68).
estrada(mafra,        sao_bento,  65).
estrada(rio_do_sul,   lages,     134).

/* Função heurística: distância em linha reta até Lages */

distancia( Cidade,lages,H):-
        distancia( Cidade,H).

distancia(bal_camboriu      ,275).    distancia(blumenau          ,219).
distancia(brusque           ,203).    distancia(caçador           ,162).
distancia(garuva            ,353).    distancia(itajai            ,266).
distancia(jaragua           ,275).    distancia(joinville         ,310).
distancia(mafra             ,265).    distancia(rio_do_sul        ,134).
distancia(sao_bento         ,320).    distancia(lages              ,0).
Hosted by www.Geocities.ws

1