Busca Informada

Prévia do material em texto

Estratégias	de	Busca
Esta	aula	descreve	algumas	estratégias	de	
busca	informada	em	espaço	de	estados
Busca	Informada
BUSCA
¢A	busca	em	grafos	pode	atingir	uma	
complexidade	elevada	devido	ao	número	de	
alternativas.	Existem	várias	formas	de	reduzir	
o	tempo/custo	de	busca.	
¢A estratégia de busca com informação 
utiliza conhecimento específico do 
problema, além da definição do próprio 
problema e pode encontrar solução de forma 
mais eficiente que uma estratégia sem 
informação – Busca Heurística.
¢O	principal	papel	da	heurística	é	eliminar (ou	
podar)	ramos	da	busca.
EXEMPLO
¢Dado o grafo abaixo, encontre a menor 
distância de S a G
G
3
4 4
5 5
4
2 4
3
FE
CBA
S
D
S
A
B D
C E
D F
E
B F
G C G
D
A E
B F
A
B
C E C G
F
G
Denota o caminho S-D-A-B-E-F
Denota o caminho S-D
EXEMPLO:	PROBLEMA	DO	CAIXEIRO	
VIAJANTE		(TSP	– TRAVELLING	SALESMAN	PROBLEM)
¢Um caixeiro viajante deve visitar N 
cidades em sua área de vendas
¢O caixeiro começa de uma base, visita 
cada cidade uma única vez e retorna à 
sua cidade no final
¢A cada viagem esta associado um custo
❒O caixeiro deve percorrer a rota mais curta
9hrs
8hrs
7hrs 6hrs
5hrs 6hrs
O	PROBLEMA	Caixeiro	Viajante
Considere as rotas definidas entre estas 4 cidades:
A
B
D
C
O	PROBLEMA	TSP
A
B
C
D C
D
B
C
D
C
B
D
BD BC
representado	como	árvore	de	busca
PROBLEMA:
EXPLOSÃO	COMBINATÓRIA
¢Com quatro cidades, temos 6 
caminhos possíveis.
¢Com dez cidades, temos 362.880 
caminhos possíveis.
¢Quanto mais cidades adicionarmos ao 
TSP, mais caminhos possíveis há.
— O que nos leva a uma explosão 
combinatória.
— Como prevenir ou pelo menos limitar isto?
BUSCA	INFORMADA
¢ O problema do caixeiro viajante e outros problemas 
do mundo real são basicamente problemas de busca. 
¢ Precisamos limitar de alguma forma o espaço de 
busca, e assim tornar o processo de busca mais rápido 
e eficiente.
¢ Humanos utilizariam “macetes”; em IA são chamados 
de Heurísticas.
¢ Estratégias de busca informada utilizam 
informação heurística sobre o problema para 
calcular estimativas para os nós no espaço de 
estados. Essa estimativa indica o quanto o nó é 
promissor com relação a atingir a meta
Outros	PROBLEMAS
Clássicos	de	BUSCA
¢ Encontrar um caminho para um 
objetivo
¢ Missionários e canibais
¢ N-rainhas
¢ Jogos
— Xadrez
— Gamão 
¢ Torres de Hanói
¢Problema do tabuleiro de xadrez 
danificado
HEURÍSTICA
¢Alguns autores consideram as 
heurísticas como funções baseadas em 
cálculos numéricos. 
¢Porém, é conveniente diferenciar e 
chamar essas funções baseadas em 
cálculos numéricos de funções de 
avaliação. 
Em outras palavras: 
¢heurísticas são não numéricas enquanto
¢ funções de avaliação estão baseadas em 
cálculos numéricos.
HEURÍSTICA	– EXEMPLOS	GERAIS
Exemplos de heurísticas:
¢Para planejar um caminho dentro de 
uma cidade, por exemplo: 
— não vire sucessivamente a esquerda (ou direita) 
em uma rua, pois fazendo isso há uma tendência a 
voltar ao mesmo lugar 
— virar quando se chega aos limites da cidade
¢ Para reparar máquinas, retire 
primeiro as peças externas mais 
pequenas, etc...
OBSERVAR	QUE	ALGUNS	ESTADOS	
SÃO	MELHORES	QUE	OUTROS...	
1 2 3
4 5 6
7 8
7 8 4
3 5 1
6 2
FUNÇÕES	DE	AVALIAÇÃO	- FA
¢ Uma função de avaliação, também conhecida 
como função heurística de avaliação ou função 
estática de avaliação é uma função matemática 
utilizada para estimar o valor ou uma boa posição e 
será representada por h(N). 
— A função de avaliação é escrita para ser rápida e precisão não 
é uma preocupação (portanto heurística) e procura na posição 
atual e não explora os movimentos possíveis (é estática).
¢A tradução de uma heurística para um valor 
numérico é realizado pela função de 
avaliação. 
— são não negativas e tal que o estado associado com o menor 
valor é considerado o estado mais promissor. 
— Frequentemente, a FA do estado meta é zero.
FUNÇÕES	DE	AVALIAÇÃO
¢Uma estratégia popular para construir 
funções de avaliação é ponderar a soma de 
vários fatores através de sua influência no 
valor da posição. 
¢Exemplos de funções de avaliação:
— Por exemplo, uma função de avaliação para o xadrez poderia 
ter a seguinte forma:
c1 * material + c2 * mobilidade + c3 * segurança-rei + c4 * controle-centro + ...
— Para planejar um caminho dentro de uma cidade, pegue uma 
linha reta, i.e., prefira o estado sucessor que está mais perto 
do estado meta em uma linha reta.
— Para reparar máquinas, considere o número de peças 
removidas da máquina mais o número de peças defeituosas 
ainda dentro da máquina.
HEURISTICA	PARA	8-PUZZLE	
1 2 3
4 5 6
7 8
1 2 3
4 5 6
7 8
1 2 3
4 5 6
7 8
1 2 3
4 5 6
7 8
N N N
N N N
N Y
Neste caso, somente “8” está fora do lugar, 
assim a função de avaliação seria igual a 1. 
Ou seja a FA traduz a heurística para um 
valor numérico
Meta
Estado
Atual
Heurística 1: 
Número de 
peças fora do 
lugar
(ignorando
espaço vazio)
OUTRA	HEURISTICA	PARA	8-PUZZLE
Neste caso somente “3”, “8” e “1” estão 
fora do lugar por 2, 3, e 3 lugares 
respectivamente, assim a função de 
avaliação h(n) = 8.
3 2 8
4 5 6
7 1
1 2 3
4 5 6
7 8
Meta
Estado 
Atual
3 3
8
8
1
1
2 espaços
3 espaços
3 espaços
Total 8
Por exemplo, num plano que contem os pontos P1 e P2, respectivamente com as
coordenadas (x1,y1) e (x2,y2), a distância de Manhattan é definida pela soma das
diferenças absolutas entre as suas coordenadas - r: |x1-x2| + |y1-y2|
Heurística 2:
Distância de 
Manhattan 
(sem
considerar
espaço vazio)
HEURISTICA	PARA	
NAVEGAÇÃO	DE	ROBÔ
0 211
58 7
7
3
4
7
6
7
6 3 2
8
6
45
23 3
36 5 24 43 5
54 6
5
6
4
5
•H1:Traduzir usando a distância de 
Manhattan até a meta.
HEURISTICA	PARA	
NAVEGAÇÃO	DE	ROBÔ
0,0 2,01,01,0
3,66,3 5,4
6,1
2,2
2,8
5,4
4,5
6,1
6,0 3,0 2,0
6,3
5,1
3,24,1
2,02,2 2,2
2,24,5 3,6 2,02,8 2,82,2 3,6
3,62,8 4,5
4,1
4,5
4,0
4,1
•H2: Também poderia ser utilizada a distância 
Euclidiana. 
HEURISTICA	PARA	
NAVEGAÇÃO	DE	ROBÔ
ESTRATÉGIAS	DE	BUSCA	
INFORMADA
FUNÇÕES	DE	AVALIAÇÃO	E	CUSTO
¢Uma função	de	avaliação, é uma função utilizada 
para estimar o valor ou uma boa posição e é 
representada por h(N). 
¢Além	das	FAs há	outras	funções	que	podem	auxiliar	o	
processo	de	busca,	denominadas	funções	de	custo.	
— São	funções	não	negativas	que	medem	a	dificuldade	de	ir	de	um	
estado	para	um	outro.
¢É	importante	observar	que:
— FAs se	referem	ao	futuro,	denominadas	h(n),	“estimam”	o	
quão	perto	está	um	estado	n do		estado	meta,	
— FCs se	referem	ao	passado,	denominadas	g(n),	sabem	quão	
longe	está	um	estado	n do	estado	inicial.
¢Assim	as	FCs são	mais	concretas que	as	FAs
Heurística
A função heurística é a estimativa 
de custo de ir do estado inicial s
até o estado final t passando pelo nó 
n e é representada por 
f(n) = g(n) + h(n)
— g(n) a FC do nó n, i.e. o custo do 
caminho de s até n (o passado)
— h(n) é FA do no n, i.e. uma estimativa 
para ir de n até t (o futuro)
HEURÍSTICA
¢Os efeitos da heurística são locais
no sentido de “oferecer um conselho” 
referente a escolha do sucessor de um 
estado específico, mas não referente a 
toda a estratégia de busca. 
¢O principal papel da heurística é 
eliminar (ou podar) ramos da 
busca.
A* - minimizando o custo total 
estimado da solução
¢No	caso	de	conhecer	tanto	a	FA	quanto	
a	FC,	é	possível	utilizar	a	estratégia	de	
busca	A*	(busca	pela	melhor	escolha).
¢A	ideia	desse	algoritmo	é	adicionaros	
valores	da	FC	e	FA	dos	sucessores	de	um	
dado	estado	e	usar	esses	valores	para	
selecionar	o	estado	sucessor	mais	
promissor.	
— Para	isso	é	importante	que	as	unidades	de	
ambas	as	funções	sejam	iguais.
Então considere:
¢g(n) a	FC	do	nó	n,	i.e. o	custo	do	caminho	de	s até	
n	(o	passado)
¢h(n) é	FA	do	nó	n,	i.e. uma	estimativa	para	ir	de	n
até	t	(futuro)
¢f(n)	=	g(n)	+	h(n) é	a	estimativa	de	custo	de	ir	da	
raiz	s até	a	meta	t passando	pelo	nó	n
A*
t
s
n
g(n)
h(n)
¢ Ideia:	evitar	a	expansão	de	caminhos	que	são	muito	
custosos
¢Lembrando	que	em	geral	f(n)	=	g(n)	+	h(n) é	a	
estimativa	de	custo	total	de	ir	da	raíz s até	a	meta	t
passando	pelo	nó	n
— g(n) a	FC do	nó	n
— h(n) é	FA do	no	n
¢O	processo	de	busca	pode	ser	visto	como	um	
conjunto	de	sub-processos,	cada	um	explorando	
sua	própria	alternativa,	ou	seja,	sua	própria	sub-
árvore
A*
¢Dentre	todos	os	sub-processos apenas	um	
mantém-se	ativo	a	cada	momento:	aquele	que	
lida	com	a	alternativa	atual	mais	promissora	--
aquela	com	menor	valor	de	f	
f(n)	=	g(n)	+	h(n)
¢Os	sub-processos restantes	aguardam	até	que	a	
estimativa	f	atual	se	altere	e	alguma	outra	
alternativa	se	torne	mais	promissora
¢Então,	a	atividade	é	comutada	para	esta	alternativa
¢O	algoritmo	usa	um	mecanismo	de	ativação-
desativação
A*
¢A	busca,	começando	pelo	nó	inicial	continua	
gerando	novos	nós	sucessores,	sempre	
expandindo	na	direção	mais	promissora	de	
acordo	com	os	valores	f
¢Podemos	imaginar	o	mecanismo	de	ativação-
desativação	da	seguinte	forma
— O	processo	trabalhando	na	alternativa	atual	recebe	um	
orçamento	limite	e	permanece	ativo	até	que	o	orçamento	
seja	exaurido
— Durante	o	período	em	que	está	ativo,	o	processo	continua	
expandindo	sua	sub-árvore e	relata	uma	solução	caso	um	
nó	final	seja	encontrado
— O	orçamento	limite	para	essa	execução	é	definido	pela	
estimativa	heurística	da	alternativa	competidora	mais	
próxima
A*
•Considere o Grafo Exemplo 1
s
e
a
bc
d
f
g
2
2
2
2
3
3 2
2
5
7
5
444
3
2
t
Distância entre duas 
cidades via um 
caminho (rodovia)
FC g(n)
Distância entre a 
cidade em questão e a 
cidade destino (t) em 
linha reta
FA h(n)
A*
¢ Dado um mapa, o objetivo é 
encontrar o caminho mais 
curto entre a cidade inicial 
s e a cidade destino t
— FC (g(X)) - Distância entre 
duas cidades
— Para estimar –FA (h(X))-
uma heurística para calcular 
o caminho restante da cidade 
X até a cidade t é utilizada a 
distância em linha reta 
denotada por dist(X,t)
¢ f(X) = g(X) + h(X) =
= g(X) + dist(X,t)
s
e
a
bc
d
f
g
2
2
2
2
3
3 2
2
5
7
5
444
3
2
t
A*
• Neste exemplo, podemos 
imaginar a busca 
consistindo em dois 
processos, cada um 
explorando um dos 
caminhos alternativos
• Processo 1 explora o 
caminho via a
• Processo 2 explora o 
caminho via e
s
e
a
bc
d
f
g
2
2
2
2
3
3 2
2
5
7
5
444
3
2
t
A*
• f(a)=g(a)+dist(a,t)=2+5=7
• f(e)=g(e)+dist(e,t)=2+7=9
• Como	o	valor-f	de	a é	menor	
do	que	de	e,	
• processo	1	(busca	via	a)	
permanece	ativo	
enquanto	
• processo	2	(busca	via	e)	fica	
em	estado	de	espera
s
e
a
bc
d
f
g
2
2
2
2
3
3 2
2
5
7
5
444
3
2
t
f(e)=9
f(a)=7
A*
• f(a)=g(a)+dist(a,t)=2+5=7
• f(e)=g(e)+dist(e,t)=2+7=9
• Como	o	valor-f	de	a é	menor	do	
que	de	e,	
• processo	1	(busca	via	a)	
permanece	ativo
enquanto	
• processo	2	(busca	via	e)	fica	em	
estado	de	espera
• f(b)=g(b)+dist(b,t)=4+4=8
s
e
a
bc
d
f
g
2
2
2
2
3
3 2
2
5
7
5
444
3
2
t
f(e)=9
f(a)=7
f(b)=8
A*
• f(a)=g(a)+dist(a,t)=2+5=7
• f(e)=g(e)+dist(e,t)=2+7=9
• Como	o	valor-f	de	a é	menor	do	
que	de	e,	
• processo	1	(busca	via	a)	
permanece	ativo	
enquanto	o
• processo	2	(busca	via	e)	fica	em	
estado	de	espera
• f(b)=g(b)+dist(b,t)=4+4=8
• f(c)=g(c)+dist(c,t)=6+4=10
• Como	f(e)<f(c)	agora	o	
processo	2	prossegue	para	a	
cidade	f
s
e
a
bc
d
f
g
2
2
2
2
3
3 2
2
5
7
5
444
3
2
t
f(e)=9
f(a)=7
f(b)=8f(c)=10
A*
• f(f)=g(f)+dist(f,t)=7+4=11
• Como	f(f)>f(c)	agora	
• processo	2	espera	e	
• processo	1	prossegue
s
e
a
bc
d
f
g
2
2
2
2
3
3 2
2
5
7
5
444
3
2
t
f(e)=9
f(a)=7
f(b)=8f(c)=10
f(f)=11
A*
• f(f)=g(f)+dist(f,t)=7+4=11
• Como	f(f)>f(c)	agora	
• processo	2	espera	e	
• processo	1	prossegue
• f(d)=g(d)+dist(d,t)=9+3=12
• Como	f(d)>f(f)	
• o	processo	2	reinicia
s
e
a
bc
d
f
g
2
2
2
2
3
3 2
2
5
7
5
444
3
2
t
f(e)=9
f(a)=7
f(b)=8f(c)=10
f(f)=11
f(d)=12
A*
• f(f)=g(f)+dist(f,t)=7+4=11
• Como	f(f)>f(c)	agora	o	processo	
2	espera	e	o	processo	1	
prossegue
• f(d)=g(d)+dist(d,t)=9+3=12
• Como	f(d)>f(f)	o	processo	2	
reinicia	chegando	até	o	
destino	t
• f(g)=g(g)+dist(g,t)=9+2=11
s
e
a
bc
d
f
g
2
2
2
2
3
3 2
2
5
7
5
444
3
2
t
f(e)=9
f(a)=7
f(b)=8f(c)=10
f(f)=11
f(d)=12
f(g)=11
A*
• f(f)=g(f)+dist(f,t)=7+4=11
• Como f(f)>f(c) agora o 
processo 2 espera e o 
processo 1 prossegue
• f(d)=g(d)+dist(d,t)=9+3=12
• Como f(d)>f(f) o processo 2 
reinicia chegando até o 
destino t
• f(g)=g(g)+dist(g,t)=9+2=11
• f(t)=g(t)+dist(t,t)=11+0=11
s
e
a
bc
d
f
g
2
2
2
2
3
3 2
2
5
7
5
444
3
2
t
f(e)=9
f(a)=7
f(b)=8f(c)=10
f(f)=11
f(d)=12
f(g)=11
f(t)=11
A*
•Durante	o	processo,	uma	árvore	de	busca	é	gerada	
tendo	como	raiz	o	nó	inicial	e	
•o	algoritmo	A*	continua	expandindo	a	árvore	de	
busca	até	que	uma	solução	seja	encontrada
s
ea f(e)=9f(a)=7
•Exemplo 1 – Arvore de Busca
A*
s
ea
b
f(e)=9f(a)=7
f(b)=8
A*
•Exemplo 1 – Arvore de Busca
s
ea
b
c
f(e)=9f(a)=7
f(b)=8
f(c)=10
A*
•Exemplo 1 – Arvore de Busca
s
ea
b
c
f
f(e)=9f(a)=7
f(b)=8
f(c)=10
f(f)=11
A*
•Exemplo 1 – Arvore de Busca
s
ea
b
c
d
f
f(e)=9f(a)=7
f(b)=8
f(c)=10
f(f)=11
f(d)=12
A*
•Exemplo 1 – Arvore de Busca
s
ea
b
c
d
f
g
f(e)=9f(a)=7
f(b)=8
f(c)=10
f(f)=11
f(d)=12
f(g)=11
A*
•Exemplo 1 – Arvore de Busca
s
ea
b
c
d
f
g
t
f(e)=9f(a)=7
f(b)=8
f(c)=10
f(f)=11
f(d)=12
f(g)=11
f(t)=11
A*
•Exemplo 1 – Arvore de Busca
Problema	de	localização	de	rotas	na	Romênia
Qual	o	caminho	para	sair	de	Arad e	chegar	em	
Bucharest usando	A*?
Estado finalExemplo: Livro Russel
Qual	o	caminho	para	sair	de	Arad e	
chegar	em	Bucharest usando	A*?
A*
A*
A*
A*
A*
¢ A* possui	uma	propriedade	muito	
importante:
— Se	a	FA	para	qualquer	estado	e é	sempre	
menor	ou	igual	ao	custo	real	de e para	a	
meta,	então	o	primeiro	caminho	
encontrado	pela	estratégia	de	busca	A*	
é	o	caminho	de	custo	mínimo	(ótimo).
A*
§ Uma	heurística	h(n) é	admissível	
se para	cada nó	n,	h(n)	≤	h*(n),	em	que
h*(n) é	o	custo	real		de	atingir	o	estado	objetivo	
desde	n.
§ Seja h*(n) o custo real para atingir o objetivo, 
então h(n) ≤ h*(n)
Obs: A distância em linha reta é uma heurística admissível.
§ Uma heurística admissível nunca sobreestima
o custo de atingir o objetivo; ela é otimista
§ Teorema:	Se		h(n)	é	admissível,	a	estratégia	
A* é	ótima	
A* - HEURÍSTICA ADMISSÍVEL 
¢Completa? Sim	
(a	menos	que	existam	infinitos	nós	com		f	≤	f(G)	)
¢Tempo? Exponencial
¢Espaço?Mantémtodos	os	nós	em	memória
¢Ótima? Sim
Propriedades de A*
Busca Admissível
¢Um	algoritmo	de	busca	é	admissível se	ele	sempre	
produz	uma	solução	ótima	(caminho	de	custo	
mínimo),	assumindo	que	uma	solução	exista
¢Para	cada	nó	n no	espaço	de	estados	vamos	denotar	
h*(n) como	sendo	o	custo	de	um	caminho	ótimo de	
n até	um	nó	final
¢Um	teorema	sobre	a	admissibilidade	de	A*	diz	que	
um	algoritmo	A*	que	utiliza	uma	função	heurística,	
i.e.	FA	h tal	que	para	todos	os	nós	no	espaço	de	estados	h(n)	
<=	h*(n)	é	admissível
¢ Considerando	h*(n) o custo real para atingir o objetivo, 
então h(n) ≤ h*(n). Há	um	limite	inferior	trivial
— h(n)	=	0	para	todo	n no	espaço	de	estados
¢ Embora	este	limite	trivial	garanta	admissibilidade	sua	
desvantagem	é	que	não	há	nenhuma	heurística	e	assim	não	
há	como	fornecer	nenhum	auxílio	para	a	busca,	resultando	
em	alta	complexidade
¢ A*	usando	h=0	comporta-se	de	forma	similar	à	busca	em	
largura
Início Objetivo Início Objetivo
h(n) = 0
Admissibilidade
¢A*	expande	nós	na	forma	de	contornos.	Se	C*	é	o	
custo	da	solução	ótima:
— Todos	os	nós	f(n)	<	C*	são	expandidos
— Nenhum	nó	f(n)	>	C*	é	expandido.	Por	exemplo,	
Timisoara	não	é	expandido,	mesmo	sendo	vizinho	a	Arad
Contornos
¢Portanto	é	interessante	utilizar	h>0	e	o	mais	próximo	
possível	de	h*	(h ≤	h*)	para	garantir	eficiência
¢Se	múltiplas	heurísticas	estão	disponíveis	busque	a	
melhor
— h(n)	=	max{h1(n),	h2(n),	…,	hm(n)}
¢De	maneira	ideal,	se	h*	é	conhecida,	podemos	
utilizar	h*	diretamente
— A*	utilizando	h*	encontra	uma	solução	ótima	diretamente,	
sem	precisar	realizar	backtracking
Admissibilidade
§ A*	é	otimamente	eficiente.	
o Isto	é,	para	todos	os	algoritmos	ótimos	da	mesma	classe,	
nenhum	deles	expande	menos	nós	do	que	A*
o Qualquer	algoritmo	que	não	expande	todos	os	nós	
com	f(n)	<	C*	podem	perder	a	solução	ótima
§ A*	é	portanto	completo,	ótimo e	otimamente	
eficiente
Entretanto,	o	número
de	nós	dentro	do	
contorno	ainda	pode
ser	exponencial
Otimamente Eficiente
¢Este	resultado	tem	grande	valor	prático
¢Mesmo	que	não	conheçamos	o	exato	valor	
de	h*,	nós	só	precisamos	encontrar	um	
limite	inferior	para	h*	e	utilizá-la	como	FA	h
em	A*
¢Isto	é	suficiente	para	garantir	que	A*	irá	
encontrar	uma	solução	ótima
A*
Algoritmo A*
A fila F é uma fila ordenada pela função f(n) = 
g(n) + h(n)
1) Insere na fila F o nó u e marque-o como 
alcançado
2) Enquanto fila F não está vazia faça
v ← elemento da frente da fila
(retire v (elemento com menor h(n) da fila)
se v não é o estado final
para todo w que partir de v que ainda 
não foi alcançado
• marque w como alcançado
• insira w na fila F (ordenado por 
f(n))
¢A	utilização	de	heurística	para	guiar	o	algoritmo	
reduz	a	busca	apenas	a	uma	região	do	espaço	do	
problema
¢Apesar	da	redução	no	esforço	da	busca,	a	ordem	
de	complexidade	é	ainda	exponencial	na	
profundidade	de	busca
— Isso	é	válido	para	tempo	e	memória	uma	vez	
que	o	algoritmo	mantém	todos	os	nós	gerados
¢Em	situações	práticas	o	espaço	de	memória	é	mais	
crítico	e	A*	pode	utilizar	toda	a	memória	
disponível	em	questão	de	minutos
Complexidade A*
¢Algumas	variações	de	A*	foram	desenvolvidas	para	
utilizar	menos	memória,	penalizando	o	tempo	de	
execução
— A	ideia	básica	é	similar	à	busca	em	profundidade	iterativa
— O	espaço	necessário	reduz	de	exponencial	para	linear	na	
profundidade	de	busca
— O	preço	é	a	re-expansão de	nós	já	expandidos	no	espaço	
de	busca
¢Duas	dessas	técnicas	são:
— IDA*	(Iterative DeepeningA*	– corte	é	o	custo	(g+h)
— RBFS	(Recursive Best-First Search)	– semelhante	a	
profundidade	recursiva	mas	usa	o	valor	f	do	melhor	
caminho	disponível	a	partir	do	nó	ancestral
Complexidade de A*
FUNÇÕES	DE	AVALIAÇÃO
Usando apenas funções de avaliação é 
possível realizar duas estratégias de busca 
informada:
¢Hill-Climbing (ou otimização discreta) 
“parece” uma busca em profundidade 
usando FA.
¢Best-First “parece” uma busca em 
largura usando FA. 
— Entretanto, Best-First é um pouco mais que isso já que 
o estado com a melhor FA, que é o estado considerado para 
continuar a busca, não é, necessariamente, um estado 
que está no mesmo nível que o estado corrente, mas 
pode ser um estado em qualquer parte do espaço de busca 
que ainda não foi visitado. 
ALGORITMOS	DE	BUSCA	LOCAL	
§ Em alguns problemas de 
otimização, o caminho até o objetivo é 
irrelevante; o objetivo é a solução 
§ Espaço de Estados = conjunto completo 
de configurações que satisfaz as 
restrições
§ Em tais casos, podem ser usados 
algoritmos de busca local 
— Manter um estado atual, tentar melhorar 
ele
HILL-CLIMBING	
¢ Os métodos de busca local, que é o caso do "hill
climbing“, são usados para resolver problemas de 
otimização discreta iniciados a partir de uma 
configuração inicial e movendo-se
repetidamente para uma melhor configuração 
vizinha. 
— Uma trajetória é gerada no espaço de busca, 
que mapeia um ponto inicial para um local 
ótimo, onde a busca local é impedida de 
prosseguir. 
— “É como”: “escalar o monte Everest em um 
nevoeiro denso com amnésia” ou “usar óculos que 
limitam sua visão a 3 metros”
HILL-CLIMBING	
funçãoHill-Climbing(problema)	retorna um	estado	que	é	um	máximo	
local
entradas:	problema,	um	problema
variáveis	locais: corrente,	um	no
vizinho,	um	nó
corrente	<- CRIAR-NO(ESTADO-INICIAL[problema])
repita
vizinho	<- um	sucessor	de	corrente	com	valor	mais	alto
se VALOR[vizinho]	≤	VALOR[corrente)	
então	retornar	ESTADO	[corrente]
corrente	<- vizinho
• Em cada passo do algoritmo, o nó corrente é substituído pelo 
melhor vizinho (vizinho com VALOR mais alto). 
• Se for usada uma estimativa de custo de heurística h(n), o 
algoritmo deve ser alterado para encontrar o vizinho com o 
h(n) com valor mais baixo.
HILL-CLIMBING
função
de
avaliação
estado atual espaço de estados
máximo 
global
Se há mais de um vizinho com a melhor 
qualidade:
- Escolher o primeiro melhor
- Escolher um entre todos de forma aleatória
máximo 
global
máximo 
local
máximo 
local “plano”
função
de
avaliação
estado atual espaço de estados
“ombro”
Problema: dependendo do estado inicial, pode 
ficar em máximos locais
HILL-CLIMBING
Considerações na BUSCA	LOCAL	
¢Manter k estados como alternativa a 
um estado
¢Comece gerando k estados 
aleatoriamente 
¢A cada iteração, todos os sucessores 
de todos os k estados devem ser 
gerados
¢Se qualquer um deles for o objetivo, 
pare; caso contrário selecione k
melhores sucessores da lista 
completa e repita
HILL-CLIMBING
8-PUZZLE	(HILL-CLIMBING)
¢Usando como função de 
avaliação h(n) a distância de 
Manhattan, em alguns casos, como 
o mostrado a seguir, hill-climbing
pode chegar rapidamente na 
solução.
1 2 3
4 5
7 8 6
1 2 3
4 5
7 8 6
1 3
4 2 5
7 8 6
1 2
4 5 3
7 8 6
1 2 3
4 5 6
7 8
1 2 3
4 5
7 8 6
1 2 3
4 8 5
7 6
1 2 3
4 8 5
7 6
1 2 3
4 8 5
7 6
1 2
4 8 3
7 6 5
1 2 3
4 8
7 6 5
5
6 4
3
4 2
1 3 3
0 2
. 
Mas hill climbing 
tem um 
problema...
h(n)
1 2 3
4 5 8
6 7
1 2 3
4 5
6 7 8
1 2 3
4 5 8
6 7
1 2 3
4 5
6 7 8
1 2
4 5 3
6 7 8
6
7 5
6 6
Neste exemplo, hill
climbing não 
encontra a solução!
Fica em um mínimo 
local…por ser um 
algoritmo guloso
(greedy) 
h(n)
HILL-CLIMBING:	PROBLEMAS
¢Máximo local: uma vez atingido, o algoritmo 
termina mesmo que a solução esteja longe de 
ser satisfatória
¢Platôs (regiões planas): regiões onde a 
função de avaliação é essencialmente plana; a 
busca torna-se como uma caminhada aleatória
¢Cumes ou “ombros”: regiões que são 
alcançadas facilmente mas até o topo a função 
de avaliação crescede forma amena; a busca 
pode tornar-se demorada
HILL-CLIMBING:	VARIAÇÕES
¢Hill-Climbing Estocástico
— Nem sempre escolhe o melhor vizinho
¢Hill-Climbing Primeira Escolha
— Escolha o primeiro bom vizinho que encontrar
¢Útil se é grande o número de sucessores de um nó
¢Hill-Climbing Reinício Aleatório
— Conduz uma série de buscas hill-climbing a partir de 
estados iniciais gerados aleatoriamente, executando 
cada busca até terminar ou até que não exista 
progresso significativo
— O melhor resultado de todas as buscas é 
armazenado
HILL-CLIMBING	REINÍCIO	ALEATÓRIO
função
de
avaliação
espaço de estados
BEST-FIRST	
¢Ideia: usar uma função de 
avaliação h(n) para cada nó 
para Estimar se ele é 
“promissor”
àExpandir o mais desejável 
¢Casos Especiais:
—greedy best-first (guloso) 
—A*
BEST-FIRST	Guloso
A fila F é uma fila ordenada pela função de 
avaliação h(n)
1) Insere na fila F o nó u e marque-o como 
alcançado
2) Enquanto fila F não está vazia faça
v ← elemento da frente da fila
(retire v (elemento com menor h(n) da fila)
se v não é o estado final
para todo w que partir de v que ainda 
não foi alcançado
• marque w como alcançado
• insira w na fila F (ordenado por 
h(n))
GREEDY	BEST-FIRST	(GULOSO)
¢No Best-first guloso
— A função de avaliação h(n) estima 
o custo de n ao objetivo
— No exemplo a seguir h (n) será a 
distância em linha reta de n a 
Bucharest (estado final)
— O algoritmo “Greedy best-first” 
expande o nó que parece levar mais 
perto do objetivo 
Problema	de	localização	de	rotas	na	Romênia
Qual	o	caminho	para	sair	de	Arad e	chegar	em	
Bucharest usando	Best-first Guloso?
Estado finalExemplo: Livro Russel
GREEDY	BEST-FIRST
Exemplo
GREEDY	BEST-FIRST
Exemplo
GREEDY	BEST-FIRST
Exemplo
GREEDY	BEST-FIRST
Exemplo
¢Completo? Não
¢Tempo? O(bm), uma boa heurística 
pode melhorar ele muito
¢Espaço? O(bm) – mantém todos os 
nós em memória
¢Ótimo? Não
GREEDY	BEST-FIRST
Propriedades do	Algoritmo
Características das Estratégias de Busca
Exemplos	de
Funções	de	Avaliação	h(n)	
8-PUZZLE (A*)
0+4
1+5
1+5
1+3
3+3
3+4
3+4
3+2 4+1
5+2
5+0
Meta
2+3
2+4
2+3
f(N) = g(N) + h(N) , em que
g(N) = número de posições caminhadas para chegar na posição atual (N).
h(N) = número de peças fora de lugar
Custo de um movimento = 1
Meta
8-PUZZLE (A*)
0+4
1+5
1+5
1+3
3+3
3+4
3+4
3+2 4+1
5+2
5+0
Meta
2+3
2+4
2+3
f(N) = g(N) + h(N) em que
g(N) = número de posições caminhadas para chegar na posição atual.
h(N) = número de peças fora de lugar
Custo de um movimento = 1
Meta
ALGUMAS	FUNÇÕES	
HEURÍSTICAS
¢Vamos	olhar	para	algumas	heurísticas	para	o	
quebra-cabeça-8	
— Soluções	em	média	a	distância	22
— Fator	de	ramificação	em	média	de	3
— 9!/2	estados	possíveis	em	um	grafo	=	181.440
¢Possíveis	heurísticas
— h1 =	número	de	peças	em	posições	erradas
— h2 =	soma	das	distâncias	das	peças	para	as	suas	posições	
finais
1 2
4
3
5
6 7 8
¢Comparação	de	e	:
— 1200	problemas	aleatórios	com	soluções	entre	2	e	24	
passos
— Solução	com	busca	em	profundidade	limitada	iterativa	e	
A*
— Comparação	com	número	de	nós	gerados	e	com	fator	de	
ramificação
¢Fator	de	ramificação:	em	média,	para	cada	nó	
visitado,	quantos	nós	são	expandidos
— Quanto	mais	próximo	de	1,	melhor	é	a	busca
1 2
4
3
5
6 7 8
ALGUMAS	FUNÇÕES	
HEURÍSTICAS
1 2
4
3
5
6 7 8
ALGUMAS	FUNÇÕES	
HEURÍSTICAS
Exemplo do Livro (Russel e Norvig)
Navegação de Robô (A*)
f(N) = g(N)+h(N), em que
g(N) = passos dados até estado atual (N)
h(N) = distancia de Manhattan até a meta
0 211
58 7
7
3
4
7
6
7
6 3 2
8
6
45
23 3
36 5 24 43 5
54 6
5
6
4
57+0
6+1
6+1
8+1
7+0
7+2
6+1
7+2
6+1
8+1
7+2
8+3
7+2 6+36+3 5+45+4 4+54+5 3+63+6 2+7
8+3 7+47+4 6+5
5+6
6+3 5+6
2+7 3+8
4+7
5+6 4+7
3+8
4+7 3+83+8 2+92+9 3+10
2+9
3+8
2+9 1+101+10 0+11
Custo de um passo (horizontal/vertical) = 1
Custo de um passo (horizontal/vertical) = 1 
Custo de um passo diagonal = √2
•f(N) = g(N) + h(N) 
•com h(N) = distância Euclideana até a meta
Navegação de Robô (A*)
1 2 3 4 5
A
B
D
C
E
Ir de A3 pra E2, um passo por 
vez, evitando obstáculos (quadros 
pretos).
Operadores: (nessa ordem)
•esquerda
•abaixo
•direita
• acima
Custo unitário.
Função de avaliação h(n): 
distância de Manhattan
Navegação de Robô (A*)
Operadores: (nessa ordem)
•esquerda
•abaixo
•direita
• acima
A2
A3
B3 A4g(A2) = 1h(A2) = 4
g(B3) = 1
h(B3) = 4
g(A4) = 1
h(A4) = 6
C3 B4g(C3) = 2h(C3) = 3
g(B4) = 2
h(B4) = 5
A1 g(A1) = 2h(A1) = 5
1 2 3 4 5
A
B
D
C
E
B1 g(B1) = 3h(B1) = 4
B5 g(B5) = 3h(B5) = 6
¢ Encontrar	o	caminho	para	ir		da	cidade	de	Arad a	cidade	de	
Bucharest utilizando	os	algoritmos	de	busca	informada	hill-
climbing,	best-first e	A*	
Arad
Oradea
Zerind
Timisoara
Lugoj
Dobreta
Sibiu
Rimnicu Vilcea
Fagaras
Pitesti
Mehadia
Craiova
Bucharest
Giurgia
Urzicenl
Neamt
Iasi
Vasini
Hirsova
Eforie
71
75
118
140
151
99
80
111
70
75
120
146
97
138
101
211
85
90
142
92
87
98
86
Exercício
Funções de Avaliação
Para Bucharest (Romenia)
Arad 366 Mehadia 241
Bucharest 0 Neamt 234
Craiova 160 Oradea 380
Dobreta 242 Pitesti 100
Eforie 161 Rimnicu Vilcea 193
Fagaras 176 Sibiu 253
Giurgiu 77 Timisoara 329
Hirsova 151 Urziceni 80
Iasi 226 Vaslui 199
Lugoj 244 Zerind 374
FUNÇÕES	DE	AVALIAÇÃO
Usando funções de avaliação é possível 
realizar duas estratégias de busca informada:
¢Hill-Climbing (ou otimização discreta) 
consiste de uma busca em profundidade 
usando FA.
¢Best-First “parece” uma busca em 
largura usando FA. 
— Entretanto, Best-First é um pouco mais que isso
já que o estado com a melhor FA, que é o estado 
considerado para continuar a busca, não é, 
necessariamente, um estado que está no 
mesmo nível que o estado corrente, mas pode 
ser um estado em qualquer parte do espaço de 
busca que ainda não foi visitado. 
A*
A*
A*
A*
A*
A*
Exercício
Use	as	estratégias	de	busca	informada	e	encontre	os	caminhos
¢Use	aplicativos	para	facilitar	o	entendimento	dos	
algoritmos	de	busca	
¢Além	dos	apresentados	na	aula	prática	utilizando	a	
Biblioteca	aima-java,	que	implementa	diversos	
algoritmos	utilizados	na	disciplina,	é	parte	do	
material	de	apoio	livro	Artificial	Intelligence - A	
Modern Approach,	de	Stuart	Russel	e	Peter	Norvig
¢Pode	ser	usado	
http://www.aispace.org/search/search.jnlp
Modele um Problema como 
uma Árvore de Busca
¢ Bibliografia
— RUSSEL,	S.;	NORVIG,	P.	- Artificial	Intelligence:	A	Modern Approach.	Prentice	
Hall;	3	edition	 (December	11,	2009).	
— NILSSON,	NILS	J.	- Artificial	Intelligence,	SAN	FRANCISCO	:	MORGAN	KAUFMANN,	
1998.	513	P.	IL.	
— WINSTON,P.H. - Artificial	Intelligence,	Reading.	Addison-Wesley,	 1977.	
— BRATKO,	I.	- Prolog	Programming	 for	Artificial	Intelligence.	Mitchell,	T.	Machine	
Learning,	McGraw-Hill,	1997.	
— RICH,	E.,	KNIGHT,	K.	- Inteligência	Artificial.	2ª	Ed.	McGraw-Hill,	Inc.	1993.	
— LUGER,	G.	F.	- Artificial	Intelligence:	Structures and Strategies for	Complex
Problem Solving,	 Addison-Wesley,	 4th	edition,	 2002.	
¢ Material	preparado pelos professores:
— Maria	Carolina	Monard
— Solange Oliveira	Rezende
— Thiago Pardo
— Gustavo	Batista
— José	Augusto	 Baranauskas (Depto.	Física e	Matemática-FFCLRP/USP)
— +	colaboradores
Referências
/*	Uma	implementação	do	PROBLEMA	DOS	MISSIONARIOS	E	CANIBAIS(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	)
A	solução	é	representada	por	[M,C,L]	em	que:
Ei	=	[5,5,5]			Ef =	[0,0,0]
oposto(0,1).	oposto(1,0).
permitido(5,C,_)	:- C	>=	0,	C	=<	5,	!.											%	corte	verde
permitido(0,C,_)	:- C	>=	0,	C	=<	5,	!.											%	corte	verde
permitido(X,X,_)	:- X	>=	0,	X	=<	5.
Uma	possível	heurística	pode	ser	procurar	pelo	mínimo	
de	H	=	M	+	C	- 2	*	L
/*	Tresmissionários	no	bote	*/	
pode_ir([M,C,L],[M1,C,L1])	:-
oposto(L,L1),
M1	is	M	+	3	- 6	*	L,
permitido(M1,C,L1).
/*	Dois	missionários	no	bote	*/																					
pode_ir([M,C,L],[M1,C,L1])	:-
oposto(L,L1),
M1	is	M	+	2	- 4	*	L,
permitido(M1,C,L1).
/*	Um	missionario no	bote	*/																																
pode_ir([M,C,L],[M1,C,L1])	:-
oposto(L,L1),
M1	is	M	+	1	- 2	*	L,
permitido(M1,C,L1).
/*	Dois	missionarios e	um	canibal	*/																										
pode_ir([M,C,L],[M1,C1,L1])	:-
oposto(L,L1),
M1	is	M	+	2	- 4	*	L,
C1	is	C	+	1	- 2	*	L,
permitido(M1,C1,L1).	
/*	Um	missionario e	um	canibal	no	bote	*/
pode_ir([M,C,L],[M1,C1,L1])	:-
oposto(L,L1),
M1	is	M	+	1	- 2	*	L,
C1	is	C	+	1	- 2	*	L,
permitido(M1,C1,L1).
/*	Tres canibais	no	bote	*/															
pode_ir([M,C,L],[M,C1,L1])	:-
oposto(L,L1),
C1	is	C	+	3	- 6	*	L,
permitido(M,C1,L1).
/*	Dois	canibais	no	bote	*/																								
pode_ir([M,C,L],[M,C1,L1])	:-
oposto(L,L1),
C1	is	C	+	2	- 4	*	L,
permitido(M,C1,L1).
/*	Um	canibal	no	bote	*/										
pode_ir([M,C,L],[M,C1,L1])	:-
oposto(L,L1),
C1	is	C	+	1	- 2	*	L,
permitido(M,C1,L1).		
/*	caminho	usando	busca	cega																																						*/
caminho_cego(I,F,Cam)	:-
caminho1(F,[I],Cam).
caminho1(F,[F|Caminho],[F|Caminho]).
caminho1(F,[Ultimo_Estado|Caminho_ate_agora],Cam)	:-
pode_ir(Ultimo_Estado,Est),
not (pertence(Est,Caminho_ate_agora)),
caminho1(F,[Est,Ultimo_Estado|Caminho_ate_agora],Cam).
/*	Usando	heurística pega	o	primeiro	elemento	da	lista,	onde	a	lista	
esta	ordenada		pela	função	heurística													*/
melhor([X|_],X).
melhor([_|Cauda],X)	:-
melhor(Cauda,X).
¢ Bibliografia
— RUSSEL, S.; NORVIG, P. - Artificial Intelligence: A Modern Approach. 
Prentice Hall; 3 edition (December 11, 2009). 
— NILSSON, NILS J. - Artificial Intelligence, SAN FRANCISCO : MORGAN 
KAUFMANN, 1998. 513 P. IL. 
— WINSTON,P.H. - Artificial Intelligence, Reading. Addison-Wesley, 1977. 
— BRATKO, I. - Prolog Programming for Artificial Intelligence. Mitchell, T. 
Machine Learning, McGraw-Hill, 1997. 
— RICH, E., KNIGHT, K. - Inteligência Artificial. 2ª Ed. McGraw-Hill, Inc. 
1993. 
— LUGER, G. F. - Artificial Intelligence: Structures and Strategies for 
Complex Problem Solving, Addison-Wesley, 4th edition, 2002. 
¢ Material preparado pelos professores:
— Maria Carolina Monard
— Solange Oliveira Rezende
— Thiago Pardo
— Gustavo Batista
— José Augusto Baranauskas (Depto. Física e Matemática-FFCLRP/USP)
— + colaboradores
Referências