Busca não informada (Slide)

Prévia do material em texto

1
Estratégias	de	Busca
Esta	aula	descreve	algumas	estratégias	
de	busca	em	espaço	de	estados
Busca	não	informada
2
Busca	em	IA
• Objetivo:	Transformar	um	problema	do	
mundo	real	em	um	problema	de	busca	
->	Modelar	o	problema	como	espaço	
de	estados
• Usar	uma	estratégia	de	busca	para	
encontrar	a	solução	
->	Busca	no	espaço	de	estados
3
Busca	em	Espaço	de	Estados
• Um	grafo	pode	ser	usado	para	representar	um	
espaço	de	estados em	que:
– Os nós	correspondem	a	situações	de	um	problema
– As	arestas correspondem	a	movimentos	permitidos	ou	ações	ou	passos	
da	solução	
– Um	dado	problema	é	solucionado	encontrando-se	um	caminho	no	grafo
• Um	problema	é	representado	por:
– Um	espaço	de	estados	(um	grafo)
– Um	estado (nó)	inicial
– Uma	condição	de	término	ou	critério	de	parada;	estados	(nós)	terminais	
são	aqueles	que	satisfazem	a	condição	de	término
• Custos
– Se	não	houver	custos,	há	interesse	em	soluções	de	caminho	mínimo
– No	caso	em	que	custos	são	adicionados	aos	movimentos	normalmente	
há	interesse	em	soluções	de	custo	mínimo
– O	custo	de	uma	solução	é	o	custo	das	arestas	ao	longo	do	caminho	da	
solução
4
Exemplo:	Quebra-Cabeça-8
• Estados?
• Operadores?
• Estado	Final:	=	estado	fornecido
• Custo	do	caminho?
5 4
6 1 8
7 3 2
1 2
8
3
4
7 6 5
Estado Inicial Estado Final
5
Exemplo:	Quebra-Cabeça-8
• Estados:	posições	inteiras	dos	quadrados
• Operadores:		mover	espaço	vazio	à	esquerda,	direita,	em	cima,	em	baixo
• Estado	Final:		estado	fornecido
• Custo	do	caminho:	1	por	movimento
5 4
6 1 8
7 3 2
1 2
8
3
4
7 6 5
Estado Inicial Estado Final
6
Exemplo:	8	Rainhas
• Estados?
• Operadores?
• Estado	Final?
• Custo	do	caminho?
7
Exemplo:	8	Rainhas
• Estados:	qualquer	arranjo	de	0	a	8	rainhas	no	tabuleiro
• Operadores:	adicionar	uma	rainha	a	qualquer	posição
• Estado	Final:	8	rainhas	no	tabuleiro,	sem	ataque
• Custo	do	caminho:	zero	(apenas	o	estado	final	é	
interessante...)	mas	não	confundir	com	complexidade	da	
busca....
8
Solução	PROLOG	- 8	RAINHAS
[pos(1,Y1),pos(2,Y2),....pos(8,Y8)]
/*i)		Lista	vazia	não	há	ataque
ii)		[pos(X,Y)|Outras]	 é		solução	se:
– Outras	é	solução	e
– pos(X,Y)	tal	que	(X,Y)	no	intervalo	0	ate	8	e
– pos(X,Y)	nao	ataca	qualquer	 rainha	em	Outras					*/
solucao([]).
solucao([pos(X,Y)|Outras])	:-
solucao(Outras),
pertence(Y,[1,2,3,4,5,6,7,8]),
nao_ataca(pos(X,Y),Outras).
nao_ataca(_,[]).
nao_ataca(pos(X,Y),[pos(X1,Y1)|Outras]):-
Y	=\=	Y1,
Y1-Y	=\=	X1-X,
Y1-Y	=\=	X-X1,
nao_ataca(pos(X,Y),Outras).
%	PARA	EXECUTAR				?- teste(+Numero_teste,?X).
teste(N,X)	:- t(N,X),solucao(X).
t(1,[pos(1,Y1),pos(2,Y2),pos(3,Y3),pos(4,Y4),pos(5,Y5),pos(6,Y6),pos(7,Y7),pos(8,Y8)]).
9
Exemplo:	Missionários	e	Canibais
q Estados?
q Operadores?
q Estado Final?
q Custo do caminho?
Três	missionários	e	três	canibais	encontram-se	na	
margem	esquerda	de	um	rio	e	devem	passar	
para	a	direita	utilizando	um	bote	de	2	lugares.
Em	nenhuma	hipótese	podemos	ter	mais	canibais	
do	que	missionários	quer	no	bote,	quer	em	
qualquer	uma	das	margens.
A	solução	é	representada	por	[M,C,L]	em	que	:
M	=	número	de	missionários	na	margem	esquerda
C	=	número	de	canibais	na	margem	esquerda			e	
L	=	margem	onde	esta	o	bote:	0	– direita;	1	- esquerda																														
10
Exemplo:	Missionários	e	Canibais
• Estados
– um	estado	é	uma	sequência	ordenada	de	três	números	representando	
o	número	de	missionários,	canibais	e	botes	na	margem	do	rio	na	qual	
eles	iniciam
– Assim	o	estado	inicial	é	[3,3,1]
• Operadores
– a	partir	de	cada	estado	os	operadores	possíveis	são	tomar	um	
missionário	e	um	canibal,	dois	missionários	ou	dois	canibais
– Há	no	máximo	5	operadores,	embora	alguns	estados	tenham	menos	
operadores	uma	vez	que	deve-se	evitar	estados	inválidos	(mais	
canibais	que	missionários)
– Se	for	necessário	distinguir	os	indivíduos,	haveria	27	operadores	ao	
invés	de	apenas	5
• Estado	Final:	[0,0,0]
• Custo	do	caminho:	número	de	travessias
11
Exemplo:	Mundo	do	Aspirador
12
Exemplo:	Mundo	do	Aspirador
13
Exemplo:	Mundo	do	Aspirador
• Estados?
• Operadores?
• Estado	Final?
• Custo	do	caminho?
14
Exemplo:	Mundo	do	Aspirador
• Estados:	um	dos	estados	mostrados	na	figura
• Operadores:	L	(esquerda),	R	(direita),	S	(sucção)
• Estado	Final:	nenhuma	sujeira	em	todos	os	ambientes
• Custo	do	caminho:	cada	ação	tem	custo	unitário
15
Exemplo:	Montagem	com	Robô
• Estados:
– coordenadas	de	valor	real	de	ângulos	das	junções	do	 robô
– partes	do	objeto	a	ser	montado
• Operadores:	movimentos	contínuos	das	junções	do	robô
• Estado	Final:	montagem	completa
• Custo	do	caminho:	tempo	para	montagem
16
Exemplo:	Pilha	de	Blocos
• Considere	o	problema	de	encontrar	um	
plano	(estratégia)	para	rearranjar	uma	pilha	
de	blocos	como	na	figura
– Somente	é	permitido	um	movimento	por	vez
– Um	bloco	somente	pode	ser	movido	se	não	há	nada	em	seu	topo
– Um	bloco	pode	ser	colocado	na	mesa	ou	acima	de	outro	bloco
B
A
C
C
B
A?
17
Exemplo:	Pilha	de	Blocos
• Na	situação	inicial	do	problema,	há	apenas	
um	movimento	possível:	colocar	bloco	C	na	
mesa
• Depois	que	C	foi	colocado	na	mesa,	há	três	
alternativas
– Colocar	A	na	mesa	ou
– Colocar	A	acima	de	C	ou
– Colocar	C	acima	de	A	(movimento	que	não	deve	ser	considerado	
pois	retorna	a	uma	situação	anterior	do	problema)
B
A
C C
B
A
?
18
Exemplo:	Pilha	de	Blocos
ABC CAB
B
C
A
C
B
A
B
AC
A
BC
A
BC
C
AB
B
AC
C
A
B
A
C
B
B
A
C
A
B
C
estado inicial
19
Busca	em	Espaço	de	Estados
• EstratégiasBásicas	de	Busca	
(Busca	não	informada	ou	Cega)
— não utiliza informações	sobre	o	problema	para	guiar	a	
busca
— estratégia	de	busca	exaustiva	aplicada	até	uma	solução	ser	
encontrada	(ou	falhar)	
¢Profundidade	(Depth-first)
¢Largura	(Breadth-first)
— Estratégias	Heurísticas	de	Busca
(Busca	Informada)
— utiliza informações	específicas	do	domínio	para	ajudar	na	
decisão
¢Hill-Climbing
¢Best-First
¢A*
20
Busca	em	Espaço	de	Estados
• Um	espaço	de	estados	pode	ser	representado	pela	
relações
— pode_ir(X,Y) que	é	verdadeira	se	há	um	movimento	permitido	
no	espaço	de	estados	do	nó	X	para	o	nó	Y;	neste	caso,	Y	é	um	
sucessor de	X
— final(X) que	é	verdadeira	se	X	é	um	estado	final
• Se	houver	custos	envolvidos,	um	terceiro	argumento	
pode	ser	adicionado,	o	custo	do	movimento
— pode_ir(X,Y,Custo)
• A	relação	pode_ir pode	ser	representada	explicitamente	
por	um	conjunto	de	fatos
• Entretanto,	para	espaços	de	estado	complexos	a	relação	
pode_ir é	usualmente	definida	implicitamente	por	meio	
de	regras que	permitam	calcular	o	sucessor	de	um	dado	
nó
21
Busca	em	Profundidade
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: a
22
Busca	em	Profundidade
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: b, c
23
Busca	em	Profundidade
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: d, e, c
24
Busca	em	Profundidade
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: h, e, c
25
Busca	em	Profundidade
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: e, c
26
Busca	em	Profundidade
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: i, j, c
27
Busca	em	Profundidade
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: j, c
28
Busca	em	Profundidade
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: c
29
Busca	em	Profundidade
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: f, g
30
Busca	em	Profundidaded fe
a
b c
g
h i j k
Inserir na frente, remover da frente: k, g
31
Busca	em	Profundidade
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: g
32
Busca	em	Profundidade
• Estado	inicial:	a
• Estados	finais:	j,f
• Nós	visitados	na	ordem:	
a,b,d,h,e,i,j
• Solução:	[a,b,e,j]
• Após	backtracking,	
a	outra	solução	é
encontrada:	[a,c,f] d fe
a
b c
g
h i j k
33
Busca	em	Profundidade
• Algoritmo	para	busca	em	profundidade:para	encontrar	
uma	solução (Caminho	da	solução)	de	um	estado	inicial	I		
para	um	estado		final	F	(busca	forward)
• Se	F	foi	alcançado	(o	estado	atual	é	F)	o	Caminho	é	
uma	solução
• Se	o	estado	atual	tem	um	sucessor,	e	esse	sucessor	
não	faz	parte	do	caminho	até	agora	(detecção	de	
loops)	insira	no	caminho	até	agora	e	continue
• A	busca	em	profundidade é	o	recurso	mais	
simples	em	programação	recursiva e,	por	
isso,	Prolog	quando	executa	metas	explora	
alternativas	utilizando-a
34
Busca	em	Profundidade	Backward
caminho_cegoBPBackward(I,F,Cam):-
caminho_b(I,[F],Cam).
caminho_b(I,[I|Caminho],[I|Caminho]).
caminho_b(I,[Ult_Estado|Caminho_ate_agora],Cam):-
pode_ir(Est,Ult_Estado),
not( pertence1(Est,Caminho_ate_agora)),
caminho_b(I,[Est,Ult_Estado|Caminho_ate_agora],Cam). 
pertence1(E,[E|_]):- !.
pertence1(E,[_|T]):-
pertence1(E,T).
35
Busca	em	Profundidade	Forward
caminho_cegoBPForward(EI,EF,Cam):-
caminho_f(EF,[EI],Cam).
caminho_f(EF,[EF|Cam],[EF|Cam]).
caminho_f(EF,[Eint|Caminho_ate_agora],Cam):-
pode_ir(Eint,E),
not(pertence1(E,Caminho_ate_agora)),
caminho_f(EF,[E,Eint|Caminho_ate_agora], Cam).
36
Algoritmo	Busca	em	Profundidade
1)Empilhe um nó v origem na pilha P e 
marque-o como alcançado
2) Enquanto a pilha P não vazia faça
v ← elemento do topo da pilha
//(desempilhe)
se existe w a partir de v, // (v,w)
e w ainda não foi alcançado
• marque w como alcançado 
• insira w na pilha P // empilhe(w)
• Um	algoritmo	de	Busca	em	Profundidade	pode	ser:
37
Considerações:	Busca	em	Profundidade
• Um	problema	com	a	busca	em	profundidade	é	que	
pode	existir	espaços	de	estado	nos	quais	o	algoritmo	
se	perde
• Muitos	espaços	de	estado	são	infinitos	e,	nesse	caso,	
o	algoritmo	de	busca	em	profundidade	pode	perder	
um	nó	final,	prosseguindo	por	um	caminho	infinito	no	
grafo
• O	algoritmo	então	explora	esta	parte	infinita	do	
espaço,	nunca	chegando	perto	de	um	nó	final.
• Para	n nós	e	a arestas,	a	complexidade	de	tempo	é	
O(a+n)
• Para	não	prosseguir		por	um	caminho	infinito	no	grafo	
e	perder	uma	eventual	solução,	uma	proposta	é	
limitar	a	busca.
38
Exercício	- Busca	em	Profundidade
• Considere	a	busca	no	espaço	abaixo,	em	que	“a” é	o	
estado	inicial	e	“k” é	o	estado	final.
• 1.Modele	o	espaço	de	busca	com	os	fatos	pode_ir(X,Y).
39
Exercício	– Busca	em	Profundidade	
(continuação)• 2.	Execute	o	algoritmo	em	prolog de	busca	em	
profundidade	para	encontrar	a	solução	do	problema.	
Mostre	o	passo	a	passo	da	execução,	os	nós	visitados	e	o	
caminho	encontrado.
caminho_cegoBPBackward(I,F,Cam):-
caminho_b(I,[F],Cam).
caminho_b(I,[I|Caminho],[I|Caminho]).
caminho_b(I,[Ult_Estado|Caminho_ate_agora],Cam):-
pode_ir(Est,Ult_Estado),
not( pertence1(Est,Caminho_ate_agora)),
caminho_b(I,[Est,Ult_Estado|Caminho_ate_agora],Cam). 
pertence1(E,[E|_]):- !.
pertence1(E,[_|T]):-
pertence1(E,T).
40
Busca	em	Profundidade	Limitada	(L=0)
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: a
41
Busca	em	Profundidade	Limitada	(L=1)
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: a
42
Busca	em	Profundidade	Limitada	(L=1)
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: b, c
43
Busca	em	Profundidade	Limitada	(L=1)
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: c
44
Busca	em	Profundidade	Limitada	(L=2)
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: a
45
Busca	em	Profundidade	Limitada	(L=2)
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: b, c
46
Busca	em	Profundidade	Limitada	(L=2)
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: d, e, c
47
Busca	em	Profundidade	Limitada	(L=2)
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: e, c
48
Busca	em	Profundidade	Limitada	(L=2)
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: c
49
Busca	em	Profundidade	Limitada	(L=2)
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: f, g
50
Busca	em	Profundidade	Limitada	(L=2)
d fe
a
b c
g
h i j k
Inserir na frente, remover da frente: g
51
Busca	em	Profundidade	Limitada
• Um	problema	com	a	busca	em	profundidade	limitada	
é	que	não	se	tem	previamente	um	limite	razoável
• Se	o	limite	for	muito	pequeno	(menor	que	qualquer	
caminho	até	uma	solução)	então	a	busca	falha
• Se	o	limite	for	muito	grande,	a	busca	se	torna	muito	
complexa
• Para	resolver	este	problema	a	busca	em	
profundidade	limitada	pode	ser	executada	de	forma	
iterativa,	variando	o	limite	durante	a	execução	do	
procedimento:	comece	com	um	limite	de	
profundidade	pequeno	e	aumente	gradualmente	o	
limite	até	que	uma	solução	seja	encontrada
• Esta	busca	é	denominada	busca	em	profundidade	
iterativa
52
Busca	em	Largura
• Em	contraste	com	a	busca	em	profundidade,	a	
busca	em	largura escolhe primeiro	visitar	aqueles	
nós	mais	próximos	do	nó	inicial
• O	algoritmo	não	é	tão	simples,	pois	é	necessário	
manter	um	conjunto de	nós	candidatos	
alternativos	e	não	apenas	um	único,	como	na	
busca	em	profundidade
• O	conjunto de	nós	candidatos é	todo	o	nível	
inferior	da	árvore	de	busca
• Além	disso,	só	o	conjunto	é	insuficiente	se	o	
caminho	da	solução	também	for	necessário
• Assim,	ao	invés	de	manter	um	conjunto	de	nós	
candidatos,	é	necessário	manter	um	conjunto	de	
caminhos	candidatos
53
Busca	em	Largura
d fe
a
b c
g
h i j k
Inserir no final, remover da frente: a
54
Busca	em	Largura
d fe
a
b c
g
h i j k
Inserir no final, remover da frente: b, c
55
Busca	em	Largura
d fe
a
b c
g
h i j k
Inserir no final, remover da frente: c, d, e
56
Busca	em	Largura
d fe
a
b c
g
h i j k
Inserir no final, remover da frente: d, e, f, g
57
Busca	em	Largura
d fe
a
b c
g
h i j k
Inserir no final, remover da frente: e, f, g, h
58
Busca	em	Largura
d fe
a
b c
g
h i j k
Inserir no final, remover da frente: f, g, h, i, j
59
Busca	em	Largura
d fe
a
b c
g
h i j k
Inserir no final, remover da frente: g, h, i, j, k
60
Busca	em	Largura
d fe
a
b c
g
h i j k
Inserir no final, remover da frente: h, i, j, k
61
Busca	em	Largura
d fe
a
b c
g
h i j k
Inserir no final, remover da frente: i, j, k
62
Busca	em	Largura
d fe
a
b c
g
h i j k
Inserir no final, remover da frente: j, k
63
Busca	em	Largura
d fe
a
b c
g
h i j k
Inserir no final, remover da frente: k
64
Busca	em	Largura
• Estado	inicial:	a
• Estados	finais:	j,f
• Nós	visitados	na	ordem:	
a,b,c,d,e,f
• A	solução	mais	curta	[a,c,f]	
é	encontrada	antes	da	mais	
longa	[a,b,e,j]
d fe
a
b c
g
h i j k
s(a,b). s(c,f).		 s(e,i).
s(a,c). s(c,g).		 s(e,j).
s(b,d). s(d,h).		 s(f,k).
s(b,e). s(h,d).	
final(f).
final(j).
65
Busca	em	Largura
• O	conjunto	de	caminhos	candidatos	será	
representado	como	uma	lista	de	caminhos	e	cada	
caminho	será	uma	lista	de	nós	naordem	reversa
• A	busca	inicia	com	um	conjunto	de	um	único	
candidato:
– [	[Início]	]
• Um	algoritmo	de	busca	em	largura:
– Se	a	cabeça do	primeiro	caminho	é	um	nó	final então	
este	caminho	é	uma	solução;	caso	contrário
– Remova	o	primeiro	caminho	do	conjunto	de	candidatos	
e	gere	o	conjunto	de	todas	as	extensões	em	um	passo	a	
partir	deste	caminho;	adicione	este	conjunto	de	
extensões	ao	final	do	conjunto	de	candidatos	e	execute	
busca	em	largura	para	atualizar	este	conjunto
66
Busca	em	Largura
• Comece	com	o	conjunto	de	candidatos	inicial
• [	[a]	]
• Gere	extensões	de	[a]	(note	que	estão	em	ordem	reversa):
• [	[b,a],	[c,a]	]
• Remova	o	primeiro	candidato	[b,a]	do	conjunto	de	candidatos	e	gere	
extensões	deste	caminho
• [d,b,a],	[e,b,a]	
• Adicione	as	extensões	ao	final	do	conjunto	de	candidatos
• [	[c,a],	[d,b,a],	[e,b,a]	]
• Remova	[c,a]	e	adicione	as	extensões	ao	final
• [	[d,b,a],	[e,b,a],	[f,c,a],	[g,c,a]	]
• Estendendo	[d,b,a]	
• [	[e,b,a],	[f,c,a],	[g,c,a],	[h,d,b,a]	]
• Estendendo	[e,b,a]
• [	[f,c,a],	[g,c,a],	[h,d,b,a],	[i,e,b,a],	[j,e,b,a]	]
• A	busca	encontra	a	lista	[f,c,a]	que	contém	um	nó	final,	portanto	o	
caminho	é	retornado	como	uma	solução
d fe
a
b c
g
h i j k
67
Implementação	Prolog	Busca	em	Largura
buscaLargura([[No|_]|_],[No|_]):- final(No).
buscaLargura([Caminho|OutrosCaminhos],Sol):-
estender(Caminho,NovosCaminhos),
concatenar(OutrosCaminhos,NovosCaminhos, 
Caminhos1),
buscaLargura(Caminhos1,Sol).
68
Implementação	Prolog	Busca	em	Largura
% resolva(No,Solucao) Solucao é um caminho 
acíclico (na ordem reversa) entre nó inicial No 
e uma solução.
resolva(No,Solucao) :-
buscaLargura([[No]],[Solucao]).
estender([No|Caminho],NovosCaminhos):-
findall([NovoNo,No|Caminho],(s(No,NovoNo),
not(pertence(NovoNo,[No|Caminho]))),
NovosCaminhos).
concatena([],L,L). 
concatena([X|Y],L,[X|Lista]):-
concatena(Y,L,Lista).
69
1)Insere na fila F o nó u e marque-o como 
alcançado
2) Enquanto fila F não vazia faça
v ← elemento da frente da fila
(retire v da fila)
para todo w que partir de v,
e w ainda não foi alcançado
• marque w como alcançado 
• insira w na fila F
Algoritmo	Busca	em	Largura
• Um	algoritmo	de	Busca		em	Largura	pode	ser	definida	da	
seguinte	forma:
70
Exercício	– Busca	em	Largura
• Considere	a	busca	no	espaço	abaixo,	em	que	“a” é	o	
estado	inicial	e	“k” é	o	estado	final.
• Considerando	a	modelagem	do	espaço	de	busca	feita	
no	exercício	do	slide	38,	execute	o	algoritmo	em	prolog
de	busca	em	largura para	encontrar	a	solução	do	
problema.	Mostre	o	passo	a	passo	da	execução,	os	nós	
visitados	e	o	caminho	encontrado.
71
Complexidade	dos	Algoritmos	de	Busca
• b	=	número	de	caminhos	alternativos/
fator	de	bifurcação/ramificação	(branching	factor)
• d	=	profundidade	da	solução
• m	=	profundidade	máxima	da	árvore	de	busca
• l	=		limite	de	profundidade
Tempo Espaço
Solução menor 
altura
garantida
Completa?
(encontra uma solução 
quando ela existe)
Profundidade O(bm) O(bm) Não
Sim (espaços finitos)
Não (espaços infinitos)
Profundidade limitada O(bl) O(bl) Não Sim se l ≥ d
Profundidade iterativa O(bd) O(bd) Sim Sim
Largura O(bd) O(bd) Sim Sim
72
Modele	um	problema	como	uma	
árvore	de	busca
• Use	aplicativos	para	facilitar	o	entendimento	dos	
algoritmos	de	busca	
http://www.aispace.org/search/search.jnlp