% ILP-503 (Prof. Dr. Silvio do Lago Pereira)

:- discontiguous estende/4.

% ---------------------------------------------------------------------
% EXEMPLO 7
% ---------------------------------------------------------------------

raiz(folha(Estado,[])) :-
    inicial(Estado).

expande(Folha, Sucessores) :-
    findall(Sucessor, sucessor(Folha, Sucessor), Sucessores).

sucessor(folha(Estado,Ações), folha(Sucessor,[Ação|Ações])) :-
    ação(Ação, Estado, Sucessor).

% ---------------------------------------------------------------------
% EXEMPLO 9
% ---------------------------------------------------------------------

bac :-
   raiz(Folha),
   bac([Folha], Plano),
   format('Plano: ~w\n', [Plano]).

bac([folha(Estado,Ações)|Folhas], Plano) :-
    (   meta(Estado)
    ->  reverse(Ações, Plano)
    ;   expande(folha(Estado,Ações), Sucessores),
        estende(0, Folhas, Sucessores, Fronteira),
        bac(Fronteira, Plano) ).

estende(0, Folhas, Sucessores, [Folha|Fronteira]) :-
   append(Folhas, Sucessores, Lista),
   random_select(Folha, Lista, Fronteira).

% ---------------------------------------------------------------------
% EXEMPLO 10
% ---------------------------------------------------------------------

expande(Folha, Expandidos, Sucessores) :-
   findall(Sucessor,
           sucessor(Folha, Expandidos, Sucessor),
           Sucessores).

sucessor(folha(Estado,Ações),
         Expandidos,
         folha(Sucessor,[Ação|Ações])) :-
    ação(Ação, Estado, Sucessor),
    not(member(Sucessor, Expandidos)).

% ---------------------------------------------------------------------
% EXEMPLO 11
% ---------------------------------------------------------------------

ba :-
   raiz(Folha),
   ba([Folha], [], Plano),
   format('Plano: ~w\n', [Plano]).

ba([Folha|Folhas], Expandidos, Plano) :-
   arg(1, Folha, Estado),
   (   meta(Estado)
   ->  arg(2, Folha, Ações),
       reverse(Ações, Plano)
   ;   expande(Folha, Expandidos, Sucessores),
       estende(0, Folhas, Sucessores, Fronteira),
       ba(Fronteira, [Estado|Expandidos], Plano) ).

% ---------------------------------------------------------------------
% EXEMPLO 13
% ---------------------------------------------------------------------

bl :-
   raiz(Folha),
   bl([Folha], [], Plano),
   format('Plano: ~w\n', [Plano]).

bl([Folha|Folhas], Expandidos, Plano) :-
   arg(1, Folha, Estado),
   (   meta(Estado)
   ->  arg(2, Folha, Ações),
       reverse(Ações, Plano)
   ;   expande(Folha, Expandidos, Sucessores),
       estende(1, Folhas, Sucessores, Fronteira),
       bl(Fronteira, [Estado|Expandidos], Plano) ).

estende(1, Folhas, Sucessores, Fronteira) :-
   append(Folhas, Sucessores, Fronteira).

% ---------------------------------------------------------------------
% EXEMPLO 15
% ---------------------------------------------------------------------

bp :-
   raiz(Folha),
   bp([Folha], [], Plano),
   format('Plano: ~w\n', [Plano]).

bp([Folha|Folhas], Expandidos, Plano) :-
   arg(1, Folha, Estado),
   (   meta(Estado)
   ->  arg(2, Folha, Ações),
       reverse(Ações, Plano)
   ;   expande(Folha, Expandidos, Sucessores),
       estende(2, Folhas, Sucessores, Fronteira),
       bp(Fronteira, [Estado|Expandidos], Plano) ).

estende(2, Folhas, Sucessores, Fronteira) :-
   append(Sucessores, Folhas, Fronteira).