Implementação
Existem várias técnicas para se efetuar uma busca. Como já vimos, uma delas é a estratégia de busca uniforme. No decorrer deste texto veremos como foi implementado o algoritmo de busca uniforme na linguagem prolog. A formalização do problema já foi apresentada na página Formalização do Problema usando Espaço de Estados.
O programa que efetua a busca tem um parâmetro denominado Fila. Este parâmetro contém as trajetórias que estão esperando a expansão e verificação se uma delas é o estado meta. Cada uma destas trajetórias pode ser representada por uma lista de estruturas do tipo "t(A,[r(R, N),r(R1,N1)])", onde o primeiro argumento de "t(_,_)" fornece g(N), g(N) é o custo conhecido de ir-se da raiz até o nódulo N. O segundo parâmetro de "t" fornece a trajetória feita para se chegar até o estado r(R,N), R é o ramo que liga o nódulo N ao pai dele. Quando o nó não tem pai ele é representado pela estrutura r(raiz,_). Durante a execução do algoritmo a fila de espera é colocada em ordem crescente pelo predicado "sort(_,_)", com isso, as estruturas da fila "t(_,_)" com menor g(N) virão para o inicio da fila e, portanto, serão examinadas primeiro. Na apresentação do código abaixo estas características são explicadas com mais detalhes.
/*--------------------------------------------------------------------------
Declaração dos operadores
--------------------------------------------------------------------------*/
:- op(35, xf, [e_uma_meta, atinge_uma_meta]).
:- op(35,xfx,[transforma,nao_produz_circulos_em]).
:- op(30,xfx,[a,em]).
/*--------------------------------------------------------------------------
ap : concatena duas listas.
--------------------------------------------------------------------------*/
ap([],X,X):- !.
ap([X|Y],Z,[X|W]):- ap(Y,Z,W).
/* --------------------------------------------------------------------------
membro : verifica se um elemento está em uma lista
--------------------------------------------------------------------------*/
membro(X,[X|_]):- !.
membro(X,[_|Y]):- membro(X,Y).
/* --------------------------------------------------------------------------
ache_todos: acha todos os estados que podem ser
expandidos a partir do estado Y.
--------------------------------------------------------------------------*/
ache_todos(X,Y,Z):- findall(X,Y,Z), !.
ache_todos(_,_,[]).
/*--------------------------------------------------------------------------
imprima : serve para imprimir uma trajetória.
A trajetória é representada por uma lista de estruturas do tipo
t(G,[r(R,Nodo),....]), onde G é o custo de processamento até
o nó atual, R é o ramo que liga nódulo N ao pai dele.
--------------------------------------------------------------------------*/
imprima(t(GN,T)) :- imprima_trajet(T).
imprima_trajet([r(raiz,Raiz)]):- !,
write('Estado Incial: '), write(Raiz), write('.').
imprima_trajet([r(Ramo,Nodo)|R]):-
imprima_trajet(R), nl,
write(Ramo), write(' e, portanto, temos: '), nl,
write(Nodo), write('.').
/*--------------------------------------------------------------------------
resolva: chama o programa que faz a busca uniforme
Inicialmente, a fila contém a mini-trajetória [t(0,[r(raiz,E)])],
a qual começa e acaba na raiz.
--------------------------------------------------------------------------*/
resolva:- estado_inicial(E),
busca([t(0,[r(raiz,E)])], Solucao),
imprima(Solucao), nl.
/*--------------------------------------------------------------------------
busca: realiza a busca uniforme, procurando o caminho que leva
a uma das metas.
Solução é um caminho que leva da raiz à meta.
T é o primeiro elemento de uma lista de trajetórias candidatas a ser
Solução. Se o predicado "atinge_a_meta" verificar que T chegou à
meta, o problema está resolvido e basta fazer Solução ser igual a T.
--------------------------------------------------------------------------*/
busca([T|_],Solucao):- T atinge_uma_meta, !, Solucao = T.
/*--------------------------------------------------------------------------
Tem-se agora o caso de que T ainda não chegou até a Solução.
Note que T é uma lista de nódulos. Deve-se agora expandir T
de modo a incluir seus filhos na Fila. A lista das extensões possíveis
é colocada em Extensoes, o predicado "ap" concatena Extensoes com
a Fila anterior retornando a FilaEstendida. A FilaEstendida será
ordenada pelo predicado "sort" de acordo com g(N), gerando a nova fila
denominada FilaComMelhorNaFrente.
E a busca continua, agora com FilaComMelhorNaFrente.
--------------------------------------------------------------------------*/
busca([T|Fila],Solucao):-
ache_todos(ExtensaoAteUmFilho, estende_ate_filho(T,ExtensaoAteUmFilho),Extensoes),
ap(Fila,Extensoes,FilaEstendida),
sort(FilaEstendida,FilaComMelhorNaFrente),
busca(FilaComMelhorNaFrente,Solucao).
/*--------------------------------------------------------------------------
Agora a trajetória é estendida de r(Ramo,Nodo) até um Filho do nódulo
Nodo. O filho de Nodo é gerado a partir de uma operação Op. Se este
filho ainda não se encontra na Trajetória, o custo para se obter o mesmo
é somado com o custo de seu nó pai, obtendo-se um novo custo para o
mesmo.
--------------------------------------------------------------------------*/
estende_ate_filho(t(G,[r(Ramo,Nodo)| Trajetoria]),
t(G1,[r(Op,NodoFilho),r(Ramo,Nodo) | Trajetoria])) :-
operacao(Op,Custo) transforma Nodo em NodoFilho,
not( NodoFilho nao_produz_circulos_em Trajetoria),
G1 is G + Custo.
/*--------------------------------------------------------------------------
Verifica se o estado que está sendo gerado já está
na trajetória. Isso elimina os possíveis ciclos.
--------------------------------------------------------------------------*/
Estado nao_produz_circulos_em Trajetoria:-
membro(r(Operacao,Estado),Trajetoria).
/*--------------------------------------------------------------------------
A trajetória que fornece a solução atinge a meta.
O processo de busca termina.
--------------------------------------------------------------------------*/
t(_,[r(Ramo,M)|_]) atinge_uma_meta :- M e_uma_meta.
|
|
Conteúdo |
|
