buscaMenor(EstadoInicial, EstadoMeta):-
    assert(inicial(a)), 
    assert(meta(b)), 
    retractall(inicial(_)), 
    retractall(meta(_)),
    assert(inicial(EstadoInicial)),
    assert(meta(EstadoMeta)),
    buscaMenor([0:EstadoInicial:[]], [], CaminhoMenorCustoAteMeta:Custo),
    format('Plano: ~w', [CaminhoMenorCustoAteMeta]),
    format('\nCusto: ~w \n\n', [Custo]).

buscaMenor([Custo:EstadoFinal:CaminhoFimInicio|_], _, CaminhoInicioFim:Custo) :-
    meta(EstadoFinal), !,
    reverse(CaminhoFimInicio, CaminhoInicioFim).

buscaMenor([CustoAtual:EstadoAtual:Caminho|Folhas], Visitados, Solucao):-
    sucessoresCusto(CustoAtual:EstadoAtual:Caminho, Visitados, Sucessores),
    insereOrdenado(Sucessores, Folhas, NovoFolhas),
    union([EstadoAtual], Visitados, UniaoVisitados),
    buscaMenor(NovoFolhas, UniaoVisitados, Solucao).

sucessoresCusto(CustoAtual:EstadoAtual:Caminho, Visitados, ListaDeSucessores):-
    findall(CustoNovo:EstadoNovo:[Acao|Caminho],
    (acao(Acao, EstadoAtual, EstadoNovo, CustoAcao),
        not(member(EstadoNovo, Visitados)),
        CustoNovo is CustoAtual+CustoAcao), 
        ListaDeSucessores).

insereOrdenado(NovasOpcoes, Caminhos, NovosCaminhos) :-
        append(NovasOpcoes, Caminhos, OpcoesCaminhos),
        sort(OpcoesCaminhos, NovosCaminhos), !.

acao(n100, S1, S2, 1) :- S2 is S1-100, S2>=0.
acao(n50, S1, S2, 1) :- S2 is S1-50, S2>=0.
acao(n25, S1, S2, 1) :- S2 is S1-25, S2>=0.
acao(n10, S1, S2, 1) :- S2 is S1-10, S2>=0.
acao(n5, S1, S2, 1) :- S2 is S1-5, S2>=0.
acao(n1, S1, S2, 1) :- S2 is S1-1, S2>=0.


