Hemos visto anteriormente un algoritmo general de búsqueda en prolog. Veremos ahora algunas consideraciones e implementaciones de los algoritmos de búsqueda estudiados.
Un problema de búsqueda en Prolog necesita de la definición de cuatro predicados básicos, dos de ellos optativos, a saber:
Necesarios:
sucesor( estado_anterior, nuevo_estado). En este caso el primer argumento es la entrada y el segundo argumento es la salida. Este predicado puede ser bastante complejo ya que la determinación de un estado a partir de otro depende de las reglas y del problema de búsqueda en particular. El nuevo_estado es sucesor inmediato, es decir no es necesario pasar por un estado intermedio llegar desde estado_anterior.
termina(estado_final).Este predicado establece las condicines de finalización de la búsqueda. Cuando se evalúa verdadero es porque estado_final es el destino de la búsqueda. Es posible que haya variso estados que cumplan las condiciones de ser estado_final.
Optativos:
evaluacion(estado,evaluacion).Este predicado toma como entrada estado e instancia en evaluación la estimación de que tan cerca se encuentra estado del objetivo.
costo(lista_estados, costo). Este predicado toma el primer argumento que es una lista de estados e instancia el segundo a un valor correspondiente al costo del camino formado por los estados de la lista en ese orden.
Los algoritmos de búsqueda vistos son algoritmos generales, independientes del problema. En el caso de nuestra representación en Prolog, los predicados que acabamos de enumerar tendrán una implementación dependiente del problema, pero es posible establecer además los algoritmos de búsqueda en forma independiente. O sea tenemos dos partes, la parte dependiente del problema y el algoritmo independiente del mismo. Veamos por ejemplo el algoritmo general de profundidad primero independiente del problema:
profprimero(Comienzo, Camino):- profprimero2(Comienzo,[Comienzo], Camino).
profprimero2(Estado, ListaEstados, ListaEstados) :- termina(Estado).
profprimero2(Estado, ListaEstados, Camino) :- successor(Estado,NuevoEstado),
not(member(NuevoEstado,ListaEstados)),
profprimero2(NuevoEstado,[NuevoEstado|ListaEstados],Camino).
El predicado profprimero2/3 es el que reliza el trabajo de búsqueda en forma recursiva, tomando un estado posible y avanzando hasta llegar al final. En caso de no llegar al final el mecanismo de backtracking del Prolog vuelve un paso atrás y busca otro camino. La implementación es sencilla porque el propio Prolog utiliza profundidad primero en su algoritmo de evaluación.
Veamos ahora la implementación de ancho primero en Prolog. Cuando explicamos el algoritmo de búsqueda general, dijimos que si la lista de ABIERTOS se implementaba como una cola, entonces teníamos como resultado la búsqueda en ancho primero. Se trata de no explorar estados de nivel n+ 1 hasta no haber cubierto los nodos del nivel n. Una forma de implementar la cola utilizar el hecho de que Prolog realiza su algoritmo intentando unificar de arriba hacia abajo, entonces si agregamos predicados al final y quitamos de arriba, estaríamos simulando una cola. Usaremos la facilidad de Prolog de modificar dinámicamente sus programas. Usaremos un predicado agenda, que ira encolando los estados a visitar, para poder hacerlo usamos el predicado dinámico assertaz que permite agregar un prédicado al final de las clausulas.
breadthsearch(Start,Ans):- cleandatabase, asserta(agenda(Start,[Start])),
agenda(State,Oldstates), find_successors(State,Oldstates,Newstate),
goalreached(Newstate), agenda(Newstate,Ans), retract(agenda(Newstate,Ans)),
asserta(oldagenda(Newstate,Ans)).
find_successors(State,Oldstates,Newstate):- successor(State,Newstate), not(State = Newstate), not(agenda(Newstate,S)), not(oldagenda(Newstate, S)), assertz(agenda(Newstate,[Newstate|Oldstates])).
find_successors(State,Oldstates,Newstate):- retract(agenda(State,Oldstates)), asserta(oldagenda(State,Oldstates)), fail.
cleandatabase :- abolish(oldagenda,2), abolish(agenda,2), !.
cleandatabase :- abolish(agenda,2), !.
cleandatabase.