Busca em Profundidade
Para encontrar um caminho de solução Sol, de um
dado nó para algum nó objetivo
Se N é um nó objetivo, então Sol=[N]
Se há um nó N1 sucessor de N, tal que há um caminho
Sol1 de N1 para algum nó-objetivo, então Sol=[N|Sol1]
Em Prolog, a idéia acima pode ser traduzida para:
busca_profundidade(N,[N]) :- objetivo(N).
busca_profundidade(N,[N|Sol1]) :- s(N,N1),
busca_profundidade(N1,Sol1).
Busca em Profundidade
s(a,b).
s(a,c).
s(b,d).
s(b,e).
s(c,f).
s(c,g).
s(d,h).
s(e,i).
s(e,j).
s(f,k).
objetivo(j).
objetivo(f).
a
b
d
h
?-busca_profundidade(a,S).
S=[a,b,e,j];
S=[a,c,f];
No
c
e
i
f
j
k
g
Busca em Profundidade com Limite
Um dos maiores problemas com a busca em profundidade
é que ela pode conduzir a sub-árvores cada vez mais
profundas. Exemplo: jogo de xadrez.
Pode-se minimizar este problema restringindo a busca até
uma profundidade limite:
busca_profundidade2(No,[No],_) :- objetivo(No).
busca_profundidade2(No,[No|Sol],Prof_max):Prof_max > 0,
s(No,No1),
Max1 is Prof_max – 1,
busca_profundidade2(No1,Sol,Max1).
Busca em Largura
O predicado:
busca_largura(Caminhos,Solucao).
é satisfeito se algum caminho de um conjunto de Caminhos
candidatos pode ser estendido até um nó objetivo. Solução é um
destes caminhos estendido.
Na implementação que daremos a seguir, Caminhos será
representado por uma lista e cada caminho candidato será
uma lista de nós na ordem inversa
Em outras palavras, a cabeça de um caminho será o nó
mais recentemente gerado e o último elemento será o nó
inicial da busca
A busca é iniciada com um conjunto de candidatos com
um único elemento: [ [NoInicial] ]
Busca em Largura
Dado um conjunto de caminhos candidatos:
Se o primeiro caminho contém um nó-objetivo como
cabeça, estão este caminho é uma solução para o
problema
Caso contrário, remove-se o primeiro caminho do
conjunto de candidatos e gera-se o conjunto de todas as
possíveis extensões de um passo deste caminho,
acrescentando-se estas extensões ao final do conjunto
de candidatos e executa-se a busca em largura neste
conjunto de caminhos candidatos atualizado
Busca em Largura
1.
2.
3.
4.
5.
6.
a
Conjunto de Candidatos inicial:
b
c
[[a]]
d
e
g
f
Gera extensões de [a]:
i
j k
h
[ [b,a], [c,a] ]
Remove o 1o caminho candidato, [b,a], e gera extensões deste
caminho, colocando-as no final do conjunto:
[ [c,a], [d,b,a], [e,b,a] ]
Remove [c,a] e acrescenta sua extensão ao final do conjunto de
candidatos, produzindo:
[ [d,b,a], [e,b,a], [f,c,a], [g,c,a] ]
Em passos posteriores, [d,b,a] e [e,b,a] são estendidos e o conjunto
de candidatos torna-se: [ [f,c,a], [g,c,a], [h,d,b,a], [i,e,b,a], [j,e,b,a] ]
Agora o processo de busca encontra [f,c,a] que contém o nóobjetivo f. Portanto, este caminho é apresentado como uma solução.
Busca em Largura
Implementação Prolog
resolve_largura(Inicio, Solucao) :busca_largura( [ [Inicio] ], Solucao).
busca_largura( [ [N|Caminho] | _], [N|Caminho]):objetivo(N).
busca_largura([ [N|Caminho]| Caminhos ], Solucao) :bagof([M,N| Caminho],
(s(N,M),not(membro(M,[N|Caminho]))),
NovosCaminhos),
conc(Caminhos, NovosCaminhos, Caminhos1), !,
busca_largura(Caminhos1, Solucao);
busca_largura(Caminhos, Solucao).
Busca Heurística
Assuma que existe uma função custo associada a
cada arco do espaço de estados
Assim, c(n,ns) é o custo associado com o
movimento do nó n para o seu nó sucessor ns
Seja f uma função heurística de estimativa, tal que
para cada nó n do espaço de estados, f(n) estima o
grau de dificuldade de n
O nó candidato corrente mais promissor é aquele
que minimiza f
Busca Heurística
f(n) é definida como a soma de 2 termos:
f(n) = g(n) + h(n)
Onde g(n) é uma estimativa do custo de um caminho ótimo do nó inicial
i até n, e h(n) é uma estimativa do custo de um caminho ótimo de n
até um nó objetivo t
Quando n é encontrado pelo processo de busca, tem-se a
seguinte situação:
Um caminho de i para n já deve ter sido encontrado e seu custo pode ser
calculado como a soma dos custos dos arcos no caminho, e pode servir como
uma estimativa g(n) do custo mínimo de i para n
h(n) é mais problemático porque o espaço entre n e t ainda não foi
explorado, e portanto h(n) é meramente um palpite baseado no
conhecimento geral do algoritmo sobre o problema particular
Não existe um método universal de se construir h, pois depende do domínio
do problema
Busca Heurística
Considere o problema de encontrar a menor rota
entre a cidade inicial i e a cidade objetivo t
e
2
(7)
i
5
2
a (5)
2
(4) c
b (4)
2
f (4)
2
3
g (2)
(3) d
3
t
2
Busca Heurística
Pode-se imaginar a busca do melhor caminho como
consistindo de 2 processos, cada um dos quais explorando
um dos caminhos alternativos:
O processo 1, explora o caminho via a e
O processo 2 explora o caminho via e
processo 1
i
processo 2
f(a)=2+5=7
a
e f(e)=2+7=9
f(b)=4+4=8
b
f f(f)=7+4=11
f(c)=6+4=10
c
g f(g)=9+2=11
f(d)=9+3=12
d
t f(t)=11+0=11
Busca Heurística
Implementação Prolog
% Determina se elemento X é membro de uma lista
membro(X,[X|_]).
membro(X,[_|Y]) :- membro(X,Y).
% Anexa duas listas produzindo uma terceira
conc([],L,L).
conc([C1|L1],L2,[C1|L3]) :- anexa(L1,L2,L3).
% Espaço de estados para teste de busca heurística
s(i,e,2).
s(i,a,2).
s(a,b,2).
s(b,c,2).
s(c,d,3).
s(d,t,3).
s(e,f,5).
s(f,g,2).
s(g,t,2).
% Heuristicas
h(e,7).
h(f,4).
h(g,2).
h(d,3).
h(c,4).
h(a,5).
h(b,4).
h(t,0).
% Nó objetivo
objetivo(t).
Busca Heurística
Implementação Prolog
% Busca do Melhor Caminho usando heurísticas (uma modificação da busca em largura).
resolve_heuristica(Inicio) :melhor([[Inicio/0]],Solucao),
apresenta_solucao(Solucao).
melhor([[No/Custo_total|Caminho]|_],[No/Custo_total|Caminho]) :objetivo(No).
melhor([[N/G|Caminho]|Caminhos],Solucao) :bagof([Ns/Gs,N/G|Caminho],
(s(N,Ns,Custo),not membro(Ns/Gs,[N/G|Caminho]),Gs is G +Custo),
Extensoes),
anexa(Caminhos, Extensoes, Candidatos),
ordena(Candidatos, Candidatos_ordenados),!,
melhor(Candidatos_ordenados, Solucao) ;
melhor(Caminhos, Solucao).
Busca Heurística
Implementação Prolog
%Predicados auxiliares
ordena([],[]).
ordena(L1,L2) :estima(L1, Estimativas),
ordena_estimativas(Estimativas, Estimativas_ordenadas),
estima(L2, Estimativas_ordenadas).
estima([],[]).
ordena_estimativas(E,O) :anexa(L,[f(C1,H1), f(C2, H2)|R],E),
H2 > H1,
anexa(L, [f(C2,
H2),f(C1,H1)|R],L1),
ordena_estimativas(L1,0),!.
ordena_estimativas(E,E).
estima([[N/G|R]|Cs],[f([N/G|R],F)|Estimativas]) :h(N,H),
F is G + H,
estima(Cs, Estimativas).
Busca Heurística
Implementação Prolog
%Predicados auxiliares
apresenta_solucao([N/Custo_total|R]) :write('o caminho de solucao eh: '),
caminho([N/Custo_total|R]), nl,
write('o custo total foi '),
write(Custo_total), nl.
caminho([]) :-!.
caminho([N/_|R]) :- write(N),
write(' <-- '),
caminho(R).
Grafos E/OU
Implementação Prolog
resolve_e_ou(No) :resolve_e_ou(No, Arvore),
apresenta_arvore(Arvore).
resolve_e_ou(No, No) :objetivo(No).
resolve_e_ou(No, No ---> Arvore) :No ---> ou : Nos, %No é um nó OU
membro(No1,Nos), %Selecionar um sucessor No1 de No
resolve_e_ou(No1, Arvore).
resolve_e_ou(No, No ---> e : Arvores) :No ---> e : Nos,
%No é um nó E
resolve_todos(Nos, Arvores). %Resolve todos os nós
sucessores de No
% Operador para definir um link do grafo
:- op(600,xfx,--->).
% Operador para separar o tipo do no (e/ou)
dos nós propriamente ditos
:- op(500,xfx,:).
% Espaço de estados E/OU para teste do
algoritmo de busca
a ---> ou :[b,c].
b ---> e : [d,e].
c ---> e :[f,g].
e ---> ou : [h].
f ---> ou :[h,i].
% Nós objetivo
objetivo(d).
objetivo(g).
objetivo(h).
Grafos E/OU
Implementação Prolog
resolve_todos([],[]).
resolve_todos([No|Nos], [Arvore|Arvores]) :resolve_e_ou(No, Arvore),
resolve_todos(Nos, Arvores).
apresenta_arvore(Arvore) :%Apresenta a arvore de solucao
apresenta_arvore(Arvore,0),!. % com endentação 0
apresenta_arvore(No ---> Arvore, I) :- %Apresenta arvore de solucao
write(No),
%com indentação I
write(' ---> '),
I1 is I + 7,
apresenta_arvore(Arvore, I1),!.
Grafos E/OU
Implementação Prolog
apresenta_arvore(e : [A], I):- %Apresenta lista E de arvores de solucao
apresenta_arvore(A,I).
apresenta_arvore(e : [A|As], I) :- %Apresenta lista E de arvores-solucao
apresenta_arvore(A,I),
tab(I),
apresenta_arvore(e:[As],I),!.
apresenta_arvore([A],_) :write(A),
nl.
apresenta_arvore(No,_) :write(No),
nl.