ALGORITMO DE BUSQUEDA EN PROLOG

% busqueda-prolog-2.pl
% Metodos de busqueda en anchura en espacios de estados con PROLOG.
%==============================================================================

%******************************************************************************
% ENUNCIADO:
%******************************************************************************

% En lo que sigue vamos a implementar en Prolog la busqueda en anchura para
%   problemas representados como espacios de estados. Recuerdese, de la
%   practica anterior, que separabamos la representacion del problema del
%   algoritmo concreto de busqueda. Un problema viene representado por los
%   predicados estado_inicial/1, estado_final/2 y sucesor/2. 

% Por ejemplo, el problema de busqueda correspondiente al siguiente grafo:
%
%                          a
%                              /   \
%                            b       c
%                           / \      | \
%                          d   e     f  g
%                        //   / \    |
%                       h    i   j   k
%
%   donde el estado inicial es "a", los estados finales son "f" y "j" y el
%   arco entre "d" y "h" es bidireccional, viene representado por el siguiente
%   programa Prolog: 

estado_inicial(a).
estado_final(E) :-
 member(E,[f,j]).
sucesor(a,b).
sucesor(a,c).
sucesor(b,d).
sucesor(b,e).
sucesor(c,f).
sucesor(c,g).
sucesor(d,h).
sucesor(e,i).
sucesor(e,j).
sucesor(f,k).
sucesor(h,d).

%******************************************************************************
% APARTADOS:
%******************************************************************************

% (1) Un NODO es una lista de estados [E_n,...,E_1] de forma que E_1 es el
%     estado inicial y E_(i+1) es un sucesor de E_i. En nuestro caso, un nodo
%     representa un camino pendiente de explorar. Un nodo representara una
%     solucion si su ultimo estado (el primero del camino) es el estado inicial
%     y su primer estado (el ultimo del camino) es un estado final. La busqueda
%     en anchura la implementamos con una cola de espera de nodos pendientes de
%     ampliar, en cada momento se escoge para su expansion el nodo que mas
%     tiempo lleva en la cola.

%     Realizar A MANO una busqueda en anchura correspondiente al problema del
%     ejemplo anterior, explicitando la evolucion de la cola de espera. 

% Cola inicial [[a]]
% Expansion 1 [[b,a], [c,a]]  
% Expansion 2 [[c,a], [d,b,a], [e,b,a]] 
% Expansion 3 [[d,b,a], [e,b,a], [f, c, a], [g, c, a]] 
% Expansion 4 [[e,b,a], [f, c, a], [g, c, a], [h, d, b, a]] 
% Expansion 5 [[f, c, a], [g, c, a], [h, d, b, a], [i, e, b, a], [j, e, b, a]] 
% Encontrada solucion: [f, c, a] (que corresponde a [a, c, f]).

% (2) Como se ha visto en el apartado (1), es necesario construir la lista de
%     nodos obtenidos mediante expansion de un nodo dado. La relacion expande/2
%     va a realizar dicha tarea, teniendo en cuenta que no hay que considerar
%     caminos ciclicos ni repetidos. Por tanto, debemos definir: 

% expande(+Abiertos,?Sucesores) :-
% "Sucesores es la lista de los sucesores del primer elemento de Abiertos
%  que no pertenecen ni al camino que lleva a dicho elemento ni a
%  Abiertos" 

% INDICACION: El siguiente predicado predefinido en Prolog puede ser de
%   utilidad:
% findall(+Var, +Objetivo, -Lista) :-
%       "Lista es la lista de TODAS las respuestas que se obtendrian sobre Var,
%        al intentar satisfacer Objetivo. Si no existen respuestas no falla:
%        simplemente crea la lista vacia." 

% expande(Abiertos,Sucesores) :-
%   Abiertos = [[E|C]|_],
%   findall([E1,E|C], 
%          (sucesor(E,E1),
%   not(member(E1,C)),
%   not(member([E1|_],Abiertos))),
%  Sucesores).

expande([[E|C]|R],Sucesores) :-
   findall([E1,E|C], 
          (sucesor(E,E1),
   not(member(E1,C)),
   not(member([E1|_],[[E|C]|R]))),
  Sucesores).

% (3) Definir el predicado anchura/2, tal que:

% anchura(+Abiertos, ?Solucion) :-
%       "Solucion es solucion al problema de busqueda en el espacio de
%        estados actualmente representado, con cola de espera Abiertos"

% INDICACION: Distinguir dos casos:
% - El primero de Abiertos es un nodo cuyo primer estado (ultimo del camino) es
%   un estado final. 
% - El primero de Abiertos es un nodo que hay que expandir usando expande/2. 

% anchura(Abiertos,S) :-
%  Abiertos = [[E|C]|_],   
%  estado_final(E),   
%  reverse([E|C],S).   

anchura([[E|C]|_],S) :-
 estado_final(E),   
 reverse([E|C],S).   

% anchura(Abiertos,S) :-
%  Abiertos = [_|R],   
%  expande(Abiertos,Sucesores),  
%  append(R,Sucesores,NAbiertos),  
%  anchura(NAbiertos,S).  

anchura([E|R],S) :-
 expande([E|R],Sucesores),  
 append(R,Sucesores,NAbiertos),  
 anchura(NAbiertos,S).  

% (4) Definir el predicado anchura/1, tal que:

% anchura(?Solucion) :-
%       "Solucion es solucion al problema de busqueda en el espacio de estados
%        actualmente representado" 

anchura(S) :-
 estado_inicial(E),  
 anchura([[E]],S).  

% (5) Usar el predicado anterior para resolver los siguientes problemas:
%     - El grafo correspondiente al ejemplo del comienzo.
%     - El problema de las jarras.
%     - El problema de las 4 reinas.

%     Obtener, mediante el mecanismo de traza, la sucesion de nodos analizados
%     en cada uno de los problemas. 

% Con el problema del grafo:

%  18 ?- trace(anchura/2, +call).
%          anchura/2: call

%  Yes
%  19 ?- anchura(S).
%  T Call:  (  8) anchura([[a]], _G148)
%  T Call:  (  9) anchura([[b, a], [c, a]], _G148)
%  T Call:  ( 10) anchura([[c, a], [d, b, a], [e, b, a]], _G148)
%  T Call:  ( 11) anchura([[d, b, a], [e, b, a], [f, c, a], [g, c, a]], _G148)
%  T Call:  ( 12) anchura([[e, b, a], [f, c, a], [g, c, a], [h, d, b, a]], _G148)
%  T Call:  ( 13) anchura([[f, c, a], [g, c, a], [h, d, b, a], [i, e, b, a], [j, e, b, a]], _G148)

%  S = [a, c, f] ;
%  T Call:  ( 14) anchura([[g, c, a], [h, d, b, a], [i, e, b, a], [j, e, b, a], [k, f, c, a]], _G148)
%  T Call:  ( 15) anchura([[h, d, b, a], [i, e, b, a], [j, e, b, a], [k, f, c, a]], _G148)
%  T Call:  ( 16) anchura([[i, e, b, a], [j, e, b, a], [k, f, c, a]], _G148)
%  T Call:  ( 17) anchura([[j, e, b, a], [k, f, c, a]], _G148)

%  S = [a, b, e, j] ;
%  T Call:  ( 18) anchura([[k, f, c, a]], _G148)
%  T Call:  ( 19) anchura([], _G148)

%  No
%  20 ?- trace(anchura/2, -call).
%          anchura/2:

%  Yes

% (6) Vamos a mejorar el predicado anchura/2, haciendolo mas eficiente. Para
%     ello vamos a evitar generar caminos que pasen por estados que pertenecen
%     a algun nodo expandido o pendiente de expandir. Esto se consigue
%     manteniendo una lista (cerrados) que va a contener los estados ya
%     generados.

% (6.1) Definir:

% expande(+Abiertos,+Cerrados,?Sucesores) :-
%       "Sucesores es la lista de los sucesores del primer elemento de Abiertos
%        que no pertenecen ni a Abiertos ni a Cerrados."

% expande(Abiertos,Cerrados,Sucesores) :-
%  Abiertos = [[E|C]|_],
%  findall([E1,E|C], 
%   (sucesor(E,E1),
%    not(member([E1|_],Abiertos)),
%    not(member(E1,Cerrados))), 
%   Sucesores).

expande([[E|C]|R],Cerrados,Sucesores) :-
 findall([E1,E|C], 
  (sucesor(E,E1),
   not(member([E1|_],[[E|C]|R])),
   not(member(E1,Cerrados))), 
  Sucesores).

% (6.2) Definir :

% anchura_con_cerrados(+Abiertos,+Cerrados,?Solucion) :-
%       "Solucion es la solucion encontrada por busqueda en anchura a partir de
%        las listas Abiertos y Cerrados, donde Abiertos es la lista de nodos
%        pendientes de analizar y cerrados los estados ya generados"

% INDICACION: analoga a la dada en (3).

% anchura_con_cerrados(Abiertos,_,S) :-  
%  Abiertos = [[E|C]|_],    
%  estado_final(E),    
%  reverse([E|C],S).    

anchura_con_cerrados([[E|C]|_],_,S) :-  
 estado_final(E),    
 reverse([E|C],S).    

% anchura_con_cerrados(Abiertos,Cerrados,S) :-
%  Abiertos = [[E|_]|R],    
%  expande(Abiertos,Cerrados,Sucesores),  
%  append(R,Sucesores,NAbiertos),   
%  NCerrados = [E|Cerrados],   
%  anchura_con_cerrados(NAbiertos,NCerrados,S).  

anchura_con_cerrados([[E|C]|R],Cerrados,S) :-
 expande([[E|C]|R],Cerrados,Sucesores),  
 append(R,Sucesores,NAbiertos),   
 NCerrados = [E|Cerrados],   
 anchura_con_cerrados(NAbiertos,NCerrados,S).  

% (6.3) Definir:

% anchura_con_cerrados(?S) :-
%       "S es una solucion del problema mediante busqueda en anchura, sin
%       generar nodos mas de una vez" 

anchura_con_cerrados(S) :-
 estado_inicial(E),   
 anchura_con_cerrados([[E]],[ ],S).

% (7) Repetir el apartado (5) para el procedimiento de busqueda del apartado
%     (6).