Busca Heurística

Prévia do material em texto

Inteligência Artificial
Inteligência Artificial:
Busca Heurística
Profa. Andréia Gentil Bonfante
Inteligência Artificial
Exemplo: dificuldades do 8-puzzle
8 1 
2 4 3 
7 6 5 
1 2 3
8 4
7 6 5 
25/11/2014 2
Solução típica: 20 passos
Expansão de filhos: ~3 (meio=4, canto=2, lados=3)
Complexidade de espaço (BL): 320 =
3.5 x 109 
Eliminando estados repetidos:
3.6 X 105 pois existem 9! = 362.880 arranjos 
diferentes de 9 posições
Porém, ainda é um nro grande de 
estados ... Precisamos de uma 
função heurística para o 8-puzzle
Inteligência Artificial
Heurística X Função de avaliação
• Heurística - conselhos não numéricos para 
determinar em que ordem devem ser 
considerados os sucessores de um dado nó 
para se continuar a busca. Exemplos: 
• não vire sucessivamente à esq (ou dir) nos 
quarteirões se está a procura de um caminho de 
um lugar A para B.
• tire as peças pequenas primeiro quando 
desmontando uma máquina.
25/11/2014 3
Inteligência Artificial
Heurística X Função de avaliação
• Função de avaliação - função que retorna um 
valor que dá suporte para a escolha do 
próximo nó a ser expandido na lista de nós 
dos algoritmos de busca básicos. Quando os 
nós são ordenados para que o nó com 
melhor avaliação seja expandido primeiro 
temos a busca BEST-FIRST (na verdade uma 
família de algoritmos de busca com 
diferentes funções de avaliação).
25/11/2014 4
Inteligência Artificial
Função de custo do caminho g(n) X Função heurística h(n)
25/11/2014 5
g(n)
Start
N
Goal
h(n)
Podemos usar o custo do caminho 
g(n) para decidir que nó estender. Já 
fizemos isto na Busca Uniforme (ou 
chamada de Branch-and-Bound). 
Porém, esta medida não dirige a 
busca para o nó objetivo. Ela cuida 
do passado.
A função heurística calcula o custo 
estimado para se alcançar o nó 
objetivo. É denotada por h(n), e 
estima o custo do caminho mais 
barato do nó n para o nó objetivo. 
Ela cuida do futuro.
Inteligência Artificial
Algoritmo Best-First
Nó = Raiz
Acrescentar ( Nó, aberto )
Enquanto aberto <> 0
Faça
Nó = prim ( aberto )
Se Nó = objetivo então saida com sucesso
Retirar ( Nó, aberto )
Acrescentar ( Nó, fechado )
Expandir ( Nó )
Para todo Ni filho de Nó
Faça
Calcular Função-Avaliação
Se Ni  aberto e Ni  fechado então
acrescentar ( Ni , aberto )
Ordenar ( aberto ) em ordem crescente de Função-Avaliação
25/11/2014 6
Aberto: Lista de nós gerados mas não 
visitados, permitindo retornar ao 
caminho que foi abandonado se o 
novo caminho falhou nas 
expectativas
Fechado: Lista de nós 
que já foram 
examinados. Para 
evitar andar em ciclos.
Inteligência Artificial
Algoritmo Greedy Best First
Nó = Raiz
Acrescentar ( Nó, aberto )
Enquanto aberto <> 0
Faça
Nó = prim ( aberto )
Se Nó = objetivo então saida com sucesso
Retirar ( Nó, aberto )
Acrescentar ( Nó, fechado )
Expandir ( Nó )
Para todo Ni filho de Nó
Faça
Calcular H(Ni)
Se Ni  aberto e Ni  fechado então
acrescentar ( Ni , aberto )
Ordenar ( aberto ) em ordem crescente de H(N)
25/11/2014 7
Inteligência Artificial
Propriedades do Greedy Best First
• Usa a função h(n) para selecionar o novo nó a 
expandir.
• Como a idéia é minimizar o custo estimado para 
alcançar o nó objetivo, h(nó-objetivo) = 0.
• Lembra o B. Profundidade, pois prefere seguir um 
único caminho até que ou encontre a meta ou tenha 
que voltar atrás.
25/11/2014 8
Inteligência Artificial
Propriedades do Greedy Best First
Não é admissível, nem completo, pois pode se 
enveredar para um caminho infinito e nunca 
retornar para tentar outras alternativas.
Complexidade de Tempo: O(bm).
Complexidade de Espaço: O(bm) - mantém todos os 
nós.
Pode reduzir espaço e tempo com o uso de uma boa 
função heurística.
25/11/2014 9
Inteligência Artificial
Exemplo de uma função heurística
• Para problemas de Cálculo de Rotas uma boa 
função heurística é a distância em linha direta
25/11/2014 10
SC
A
D
B
SP
C
140
99 211
80
97 101
Tabela de Distância 
em Linha Reta para São Paulo
SC --- 366
A --- 253
B --- 178
C --- 193
D --- 98 
SP --- 0
...
Dada as coordenadas de cada cidade a distância D 
= sqrt(sqr(X2 - X1) + sqr(Y2 - Y1)).
A solução é o caminho SC-A-B-SP que não é o 
melhor!!!! O caminho por C, D, SP é menor. 
Greedy nem sempre encontra soluções ótimas.
Inteligência Artificial
Exemplos de árvores de busca usando Greedy
Passo 1 Passo 2 Passo 3
A A A
B(3) C(5) D(1) B(3) C(5) D
E(4) F(6)
25/11/2014 11
Inteligência Artificial
Exemplos de árvores de busca usando Greedy
Passo 4 
A Observem como
B C(5) D Greedy volta atrás
G(6) H(5) E(4) F(6) para escolher B (3)
25/11/2014 12
Inteligência Artificial
Busca A*
Esta estratégia é completa e admissível se h nunca super-estima o 
custo de se alcançar o objetivo. Tal h é chamada de heurística 
admissível.
Best First usando f como função de avaliação e uma função h 
admissível é conhecido como Busca A*
25/11/2014 13
Greedy minimiza
h(n), mas não é 
completo nem 
admissível
Busca Uniforme
minimiza g(n). É
admissível e 
completo,mas pode
ser ineficiente
f(n) = g(n) + h(n)
Inteligência Artificial
Algoritmo A*
Nó = Raiz
Acrescentar ( Nó, aberto )
F ( Nó ) = H ( Nó )
G ( Nó ) = 0
Enquanto aberto <> 0
Faça
Nó = Prim ( aberto )
Se Nó = objetivo então saida com sucesso
Retirar ( Nó, aberto )
Acresentar ( Nó, fechado )
Expandir ( Nó )
Para todo Ni filho de Nó
Faça
Calcular H( Ni )
Se Ni  aberto e Ni  fechado então
G( Ni ) = G ( Nó ) + c ( Nó, Ni )
F( Ni ) = G( Ni ) + H( Ni )
acrescentar ( Ni , aberto )
Ordenar ( aberto ) em ordem crescente de F( N )
25/11/2014 14
Inteligência Artificial
Algoritmos de Melhorias Iterativas
• Existem problemas para os quais a descrição do 
estado já contem toda a informação necessária 
para a solução: o caminho até a solução é 
irrelevante. Ex: 8 rainhas.
• Nestes casos usa-se algoritmos que começam com 
uma configuração completa e tentam melhorias 
para conseguir uma melhor qualidade da solução.
25/11/2014 15
Inteligência Artificial
• Duas classes:
Hill-climbing: sempre tenta fazer mudanças 
que melhoram o estado atual
Simulated Annealing: pode algumas vezes 
fazer mudanças que tornam as coisas 
piores, pelo menos temporariamente.
25/11/2014 16
Inteligência Artificial
Algoritmo Hill-Climbing
Nó = Raiz
Saida = V
Enquanto Nó <> Objetivo
Faça
Expandir ( Nó )
Para todo Ni filho de Nó 
faça
Calcular H( Ni )
Próx_Nó = N tal que H( N ) = min H( Ni )
Se H( Nó ) < H( Próx_Nó ) então
Saida = F
Nó = objetivo
senão Nó = Próx_Nó
Se Saida então suceso
senão falha
25/11/2014 17
Inteligência Artificial
Propriedades do Hill-Climbing
• A busca pode não conduzir à solução ótima (beco 
sem saída, ou seja, máximo local), já que após a 
decisão referente ao nó mais promissor os outros 
caminhos opcionais são esquecidos (não usa lista 
Aberto).
• Hill Climbing pode também ser usado em problemas 
cujas soluções sejam o caminho. Basta mantê-lo “em 
cima” de cada nó como fazíamos nas buscas cegas.
25/11/2014 18
Inteligência Artificial
•Objetivo é atingir o topo da montanha:
• Se existe um só cume então o método é 
admissível
• Se existem vários cumes menores que o 
objetivo, o algoritmo pode conduzir ao cume 
de uma dasmontanhas e não ao topo 
desejado. O algoritmo pára mesmo embora a 
solução esteja longe de ser satisfatória.
25/11/2014 19
Inteligência Artificial
Simulated Annealing
• Similar ao Hill-Climbing, mas em vez de pegar o 
melhor movimento, pega um movimento escolhido 
randomicamente.
• Usa uma analogia com o processo de resfriar um 
líquido gradualmente até ele congelar. Usa um 
parâmetro para determinar quão longo será este 
processo.
• Fornece um meio de escapar do máximo local e é 
completo e admissível, se o parâmetro de entrada
permite que o processo seja longo.
25/11/2014 20
Inteligência Artificial
Exemplos de aplicação dos algoritmos Greedy e HC (com caminho) em 
cálculo de rotas. Guardem o caminho acima dos nós como nos métodos 
de Busca Cega
25/11/2014 21
S
D
C
A
B
I
F
H
E G
4
34
23
0123
2
HC tem sucesso???
Fig. A
Heurística= | Xg - Xn| + |Yg - Yn |
Distância em blocos /Manhattan
0,0
3,3
G tem sucesso??
H
F
ED
C
B
A
S
S
Fig. B
0,0
3,3
6
4
3
4
3
2
4
6
HC tem sucesso???
G tem sucesso??
Heurística= | Xg - Xn| + |Yg - Yn |
Inteligência Artificial
Soluções
• Fig. A: G e HC tem sucesso.
Solução do Greedy: S -> AS -> BSA -> ESAB -> GSABE
Solução do HC: S -> AS -> BSA -> ESAB -> GSABE
• Fig. B: G tem sucesso; HC falha.
Solução do Greedy: S ->AS -> BSA -> ESAB -> HSABE -> 
GSABEH
HC: S -> AS -> BSA (pára)
25/11/2014 22
Inteligência Artificial
Códigos Prolog para A*
:- op(35,xf,e_a_meta).
:- op(35,xf,atinge_a_meta).
:- op(35,xfx,transforma).
:- op(30,xfx,a).
:- op(30,xfx,em).
:- op(35,xfx,nao_produz_circulos_em).
% programas auxiliares
ap([],X,X).
ap([X|Y],Z,[X|W]) :- ap(Y,Z,W).
membro(X,[X|_]):- !.
membro(X,[_|Y]) :- membro(X,Y).
ache_todos(X,Y,Z) :- findall(X,Y,Z), !.
ache_todos(_,_,[]).
% o programa abaixo serve para imprimir uma trajetoria dada na seguinte forma:
% t(f([4]), g([4]), [r([4],g),r([1],c),r(raiz,b)]).
imprima(t(FN,GN,T)) :- imprima_trajet(T).
imprima_trajet([r(raiz,Raiz)]) :- !, write('Estado Inicial: '),
write(Raiz), write('.').
imprima_trajet([r(Ramo,Nodo)|R]) :-
imprima_trajet(R), nl, write(Ramo), write(' e, portanto, temos: '), nl,
write(Nodo), write('.').
25/11/2014 23
Aux_busca_heuristica.pl
Inteligência Artificial
% busca heuristica --- A*
resolva :- estado_inicial(E), calcule_hn(E,HN),
busca([t(HN,0,[r(raiz,E)])],Solucao),
imprima(Solucao), nl.
busca([T|_],Solucao) :- T atinge_a_meta, !, Solucao = T.
busca([T|Fila], Solucao) :-
ache_todos(ExtensaoAteUmFilho,
estende_ate_filho(T,ExtensaoAteUmFilho),Extensoes),
ap(Fila,Extensoes,FilaEstendida),
sort(FilaEstendida,FilaComMelhorNaFrente),
busca(FilaComMelhorNaFrente,Solucao).
estende_ate_filho(t(F,G,[r(Ramo,N)|Trajetoria]),
t(F1,G1,[r(Op,Filho),r(Ramo,N)|Trajetoria])) :-
oper(Op) transforma N em Filho,
Filho nao_produz_circulos_em Trajetoria,
calcule_hn(Filho,HNFilho),
calcule_custo(N,Filho,Custo),
G1 is G+Custo, F1 is G1+HNFilho.
Estado nao_produz_circulos_em Trajetoria :-
not membro(r(Operacao,Estado),Trajetoria).
t(_,_, [r(Ramo,M)|_]) atinge_a_meta:- M e_a_meta.
25/11/2014 24
Busca_A_estrela.pl
Inteligência Artificial
% trajetoria entre duas cidades
:- op(300,xfx,para).
:- op(300,xfx,==>).
oper(X para Y) transforma X em Y :- X ==> Y.
a ==> b. b ==> m. m ==> f. f ==> q. q ==> p.
p ==> n. p ==> s.
b ==> c.
c ==> d.
d ==> q. d ==> n. d ==> g.
n ==> h. n ==> s. h ==> g.
coord(a,2,4) :- !.
coord(c,4,2) :- !.
coord(f,7,8) :- !.
coord(h,10,1) :- !.
coord(n,11,3) :- !.
coord(q,11,7) :- !.
coord(b,5,6) :- !.
coord(d,7,4) :- !.
coord(g,8,2) :- !.
coord(m,9,6) :- !.
coord(p,12,6) :- !.
coord(s,13,2) :- !.
25/11/2014 25
Trajetoria.pl
Inteligência Artificial
calcule_custo(Nodulo,Nodulo_Filho,Custo) :-
coord(Nodulo,XN,YN),
coord(NoduloFilho,XF,YF),
Custo is sqrt((XN - XF) * (XN - XF) + (YN - YF) * (YN - YF)).
calcule_hn(N,HN) :- S e_a_meta, coord(S,XS,YS),
coord(N,XN,YN),
HN is sqrt((XN - XS) * (XN - XS) + (YN - YS) * (YN - YS)).
estado_inicial(a).
s e_a_meta.
25/11/2014 26