Busca sem Informação
Disciplina:
Inteligência Artificial
Prof. Frederico Brito Fernandes
[email protected]
CONTEÚDO
(1) Definição
(2) Estudos de Caso
(3) Busca em Largura
(4) Busca por Custo Uniforme
(5) Busca em Profundidade
(6) Busca com Profundidade Limitada
(7) Busca com Profundidade Interativa
(8) Busca Bidirecional
(9) Comparação
(1) Busca sem Informação: definição
• Um problema de busca é:
– Aquele que é resolvido através da busca do melhor estado (ou
caminho) em todo o espaço de estados.
– Ex: chegar à Areia saindo de JP
• Discutiremos sobre algoritmos
de busca em árvore Ex: Busca
Mamanguape
50
FIM
Areia
60
40
50
CG
20
Guarabira
40
Esperança
JP
Baía da
Traição
em Largura
Mamanguape
CG
Guarabira
Guarabira
Areia
Esperança
50
90
JP
INÍCIO
120
Esperança
• Um problema de busca sem informação é:
– Aquele que não possui informação do melhor caminho para chegar na solução.
Ex: saindo de João Pessoa, não temos idéia de que direção está o objetivo (apesar
de CG estar a 120km, é a melhor direção)
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
2/27
(1) Busca com Informação: definição
• Um problema de busca é:
– Aquele que é resolvido através da busca do melhor estado (ou
caminho) em todo o espaço de estados.
– Ex: chegar à Areia saindo de JP
Origem
Mamanguape
20
Baía da
Traição
50
FIM
Areia
60
40
50
Guarabira
40
Esperança
50
90
JP
CG
INÍCIO
120
Destino Dist. em Linha
Reta (km)
JP
Areia
134
BT
Areia
155
Mamanguape
Areia
130
Guarabira
Areia
89
Esperança
Areia
53
CG
Areia
35
Areia
Areia
0
• Um problema de busca com informação é:
– Aquele que possui informação do melhor caminho para chegar na solução. Ex: indo
pra CG, gasto 120km de percurso + distância em linha reta até Areia (35km) = 155km
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
3/27
(1) Busca: critérios de análise
• Como determinar que um algoritmo é melhor do que outro?
– Ex: para esse exemplo, é melhor usar Busca em Largura ou em
Profundidade?
• Discutiremos sobre algoritmos
de busca em árvore Ex: Busca
Mamanguape
20
Baía da
Traição
JP
em Largura
50
FIM
Areia
60
40
50
Guarabira
40
Esperança
CG
50
Mamanguape
CG
Guarabira
Guarabira
Areia
Esperança
90
JP
INÍCIO
120
Esperança
Critérios de Análise
• O algoritmo Busca
em Largura...
Disciplina: Inteligência Artificial
a) É completo? (ele sempre acha a solução, se existir?)
b) É ótimo? (ele acha a melhor solução?)
c) Leva quanto tempo para achar a solução? (tempo)
d) Produz quantos nós? (memória)
Professor: Frederico Brito Fernandes
4/27
(1) Busca: critérios de análise
• Dado o algoritmo:
Geração da Árvore:
MissaoBregareia(){
cidade = JP
faça
cidadeAnterior = cidade
cidade=proximaCidade(menorDistância,naoVisitada)
cidade.visitada=true
se (cidade=jaVisitada ou cidade=FIM)
cidade=cidadeAnterior
enquanto (cidade  Areia)
}
JP
50
Mamanguape
20
Mamanguape
50
Guarabira
40
X
Esperança
50
CG
30
Areia
Mamanguape
20
Baía da
Traição
50
FIM
Areia
60
30
50
Guarabira
40
Esperança
CG
Disciplina: Inteligência Artificial
90
O algoritmo MissaoBregareia...
50
INÍCIO
JP
120
a) É completo? (ele acha a solução, se existir?)
b) É ótimo? (ele acha a melhor solução?)
c) Leva quanto tempo?
d) Produz quantos nós?
Professor: Frederico Brito Fernandes
5/27
(1) Busca: critérios de análise
•
Completude: A estratégia sempre encontra uma solução quando existe alguma?
•
Custo do tempo: Quanto tempo gasta para encontrar uma solução?
Normalmente medida em termos do número de nós gerados.
•
Custo de memória: Quanta memória é necessária para realizar a busca?
Normalmente medida pelo tamanho máximo que a lista de nós abertos assume
durante a busca.
•
Qualidade/otimalidade (optimality): A estratégia encontra a melhor solução
quando existem soluções diferentes?
• menor custo de caminho
•
As complexidades de tempo e espaço são medidas em termos de:
– b : fator de ramificação máximo da árvore de busca.
– d : profundidade do nó objetivo menos profundo.
– m : profundidade máxima de qualquer caminho no espaço de estados.
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
6/27
(1) Busca sem Informação: algoritmos
• Terminologia:
– Borda: é a coleção de nós que foram gerados mas não expandidos
(nós abertos). Também conhecido como franja
– Nó Folha: qualquer elemento da borda (sem sucessores na árvore)
– Estratégia de Busca: função que seleciona o próximo nó a ser
expandido da borda
• Algoritmos de Busca Desinformada:
–
–
–
–
–
–
Busca em Largura (ou extensão)
Busca por Custo Uniforme
Busca em Profundidade
Busca em Profundidade Limitada
Busca em Profundidade Interativa
Busca Bidirecional
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
7/27
(2) Estudo de Caso 1: Missão Bregareia
• Problema do menor caminho
– Objetivo:
• Ir pro Bregareia, saindo de João Pessoa
– Ações:
• Próxima cidade
– Usando Busca...
•
•
•
•
•
•
Mamanguape
Baía da
Traição
50
FIM
Areia
30
20
60
50
Guarabira
40
Esperança
CG
120
50
90
João INÍCIO
Pessoa
Em Largura
Por Custo Uniforme
Em Profundidade
Em Profundidade Limitada
Em Profundidade Interativa
Bidirecional
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
8/27
(2) Estudo de Caso 2: problema dos sapos
• Problema dos sapos:
– Objetivo:
• Faça com que os machos fiquem na
direita e as fêmeas na esquerda
– Ações:
• Pular para frente, e duas pedras no
máximo
M1
M2
Disciplina: Inteligência Artificial
M3
– Usando Busca...
•
•
•
•
Em Largura
Por Custo Uniforme
Em Profundidade
Em Profundidade
Limitada
• Em Profundidade
Interativa
• Bidirecional
F3
Professor: Frederico Brito Fernandes
F2
F1
9/27
(2) Estudo de Caso 3: menor caminho
Início
objetivo
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
10/27
(3) Busca em Largura
• Expande os nós mais rasos ainda não expandidos
• Todos os nós de profundidade d são expandidos antes dos nós
de profundidade d+1
• Borda organizada como uma fila (FIFO)
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
11/27
(3) Busca em Largura
• Expande os nós mais rasos ainda não expandidos
• Todos os nós de profundidade d são expandidos antes dos nós
de profundidade d+1
• Borda organizada como uma fila (FIFO)
1
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
12/27
(3) Busca em Largura
• Expande os nós mais rasos ainda não expandidos
• Todos os nós de profundidade d são expandidos antes dos nós
de profundidade d+1
• Borda organizada como uma fila (FIFO)
1
2
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
13/27
(3) Busca em Largura
• Expande os nós mais rasos ainda não expandidos
• Todos os nós de profundidade d são expandidos antes dos nós
de profundidade d+1
• Borda organizada como uma fila (FIFO)
1
2
Disciplina: Inteligência Artificial
3
Professor: Frederico Brito Fernandes
14/27
(3) Busca em Largura
• Expande os nós mais rasos ainda não expandidos
• Todos os nós de profundidade d são expandidos antes dos nós
de profundidade d+1
• Borda organizada como uma fila (FIFO)
1
2
Disciplina: Inteligência Artificial
3
Professor: Frederico Brito Fernandes
4
15/27
(3) Busca em Largura
• Expande os nós mais rasos ainda não expandidos
• Todos os nós de profundidade d são expandidos antes dos nós
de profundidade d+1
• Borda organizada como uma fila (FIFO)
1
2
3
4
5
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
16/27
(3) Busca em Largura
• Expande os nós mais rasos ainda não expandidos
• Todos os nós de profundidade d são expandidos antes dos nós
de profundidade d+1
• Borda organizada como uma fila (FIFO)
1
2
5
Disciplina: Inteligência Artificial
3
4
6
Professor: Frederico Brito Fernandes
17/27
(3) Busca em Largura
• Expande os nós mais rasos ainda não expandidos
• Todos os nós de profundidade d são expandidos antes dos nós
de profundidade d+1
• Borda organizada como uma fila (FIFO)
1
2
5
Disciplina: Inteligência Artificial
3
6
4
7
Professor: Frederico Brito Fernandes
18/27
(3) Busca em Largura: análise
•
•
•
•
•
Completude: Sim. Encontra o mais raso, se o fator de ramificação b é finito
Otimalidade: Sim, se o custo do caminho for uma função não decrescente da
profundidade do nó (ou seja, quando todos os caminhos tiverem o mesmo custo)
Custo de Tempo: 1 + b + b2 + b3 + ... + bd + (bd+1-b) = O(bd+1)
Custo de Memória: O(bd+1) – guarda todos os nós na memória
Grande quantidade de espaço e tempo exigida. Pode facilmente gerar 1MB de nós que
devem ser guardados.
1
b = número máximo de filhos
2
3
4
(ou fator de ramificação)
d = altura do nó ótimo
d
5
Disciplina: Inteligência Artificial
6
7
Professor: Frederico Brito Fernandes
19/27
(3) Busca em Largura: análise
• Para um fator de ramificação b=10, e supondo que 1000 nós podem ser
gerados por segundo, temos:
1+b1+b2+(b3-b) = 1+10+100+(1000-10) = 1101
•
–
–
–
–
–
–
–
profundidade
nós
tempo
memória
2
4
6
8
10
12
14
1100
111.100
107
109
1011
1013
1015
0,11 seg
11 seg
19 min
31 horas
129 dias
35 anos
3.523 anos
1 MB
106 MB
10 GB
1 TeraB
101 TeraB
10 PentaB
1 exaB
Cada nó
tem 1KB
• Requisitos de memória são problemas maiores do que o tempo de
execução
• Problemas de busca de complexidade exponencial não podem ser
resolvidos por métodos sem informação (exceto os menores)
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
20/27
(4) Busca por Custo Uniforme
• Expande o nó de menor custo ainda não expandidos (pelo
custo do caminho – g(n))
• Encontra a solução mais barata porque os nós mais baratos
são expandidos primeiro
• Borda é organizada em ordem crescente pelo custo do
caminho de cada nó
S
1
S
5
A
B
15
10
5
G
5
C
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
21/27
(4) Busca por Custo Uniforme
• Expande o nó de menor custo ainda não expandidos (pelo
custo do caminho – g(n))
• Encontra a solução mais barata porque os nós mais baratos
são expandidos primeiro
• Borda é organizada em ordem crescente pelo custo do
caminho de cada nó
S
1
S
5
A
B
15
1
10
5
G
A
5
B
15
C
5
C
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
22/27
(4) Busca por Custo Uniforme
• Expande o nó de menor custo ainda não expandidos (pelo
custo do caminho – g(n))
• Encontra a solução mais barata porque os nós mais baratos
são expandidos primeiro
• Borda é organizada em ordem crescente pelo custo do
caminho de cada nó
S
1
S
5
A
B
15
10
5
5
C
Disciplina: Inteligência Artificial
1
G
A
5
B
15
C
11
G
Professor: Frederico Brito Fernandes
23/27
(4) Busca por Custo Uniforme
• Expande o nó de menor custo ainda não expandidos (pelo
custo do caminho – g(n))
• Encontra a solução mais barata porque os nós mais baratos
são expandidos primeiro
• Borda é organizada em ordem crescente pelo custo do
caminho de cada nó
S
1
S
5
A
B
15
10
5
5
C
Disciplina: Inteligência Artificial
1
G
A
5
B
11
G
Professor: Frederico Brito Fernandes
15
C
10
G
24/27
(4) Busca por Custo Uniforme
• Expande o nó de menor custo ainda não expandidos (pelo
custo do caminho – g(n))
• Encontra a solução mais barata porque os nós mais baratos
são expandidos primeiro
• Borda é organizada em ordem crescente pelo custo do
caminho de cada nó
S
1
S
5
A
B
15
10
5
5
C
Disciplina: Inteligência Artificial
1
G
A
5
B
11
G
Professor: Frederico Brito Fernandes
15
C
10
G
25/27
(4) Busca por Custo Uniforme
• Completude: Sim, se nenhum operador tiver custo negativo
• Custo Tempo: quantidade de nós com g <= custo da solução ótima
(pode ser muito maior que O(bd))
• Custo Memória: quantidade de nós com g <= custo da solução ótima
• Otimalidade: Sim.
• Espaço e tempo continuam sendo um problema
1
S
5
A
B
15
1
10
5
G
A
5
C
Disciplina: Inteligência Artificial
S
5
B
11
G
15
C
10
G
b = número máximo de filhos
(ou fator de ramificação)
g = custo do nó ótimo
Professor: Frederico Brito Fernandes
26/27
(5) Busca em profundidade
• Expande o nó mais profundo ainda não expandido
• Quando encontra um nó que não pode ser expandido, volta
para expandir os outros dos níveis mais rasos
• Borda organizada como uma pilha (LIFO)
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
27/27
(5) Busca em profundidade
• Expande o nó mais profundo ainda não expandido
• Quando encontra um nó que não pode ser expandido, volta
para expandir os outros dos níveis mais rasos
• Borda organizada como uma pilha (LIFO)
1
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
28/27
(5) Busca em profundidade
• Expande o nó mais profundo ainda não expandido
• Quando encontra um nó que não pode ser expandido, volta
para expandir os outros dos níveis mais rasos
• Borda organizada como uma pilha (LIFO)
1
2
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
29/27
(5) Busca em profundidade
• Expande o nó mais profundo ainda não expandido
• Quando encontra um nó que não pode ser expandido, volta
para expandir os outros dos níveis mais rasos
• Borda organizada como uma pilha (LIFO)
1
2
3
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
30/27
(5) Busca em profundidade
• Expande o nó mais profundo ainda não expandido
• Quando encontra um nó que não pode ser expandido, volta
para expandir os outros dos níveis mais rasos
• Borda organizada como uma pilha (LIFO)
1
2
3
4
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
31/27
(5) Busca em profundidade
• Expande o nó mais profundo ainda não expandido
• Quando encontra um nó que não pode ser expandido, volta
para expandir os outros dos níveis mais rasos
• Borda organizada como uma pilha (LIFO)
1
2
3
4
Disciplina: Inteligência Artificial
5
Professor: Frederico Brito Fernandes
32/27
(5) Busca em profundidade
• Expande o nó mais profundo ainda não expandido
• Quando encontra um nó que não pode ser expandido, volta
para expandir os outros dos níveis mais rasos
• Borda organizada como uma pilha (LIFO)
1
2
3
4
Disciplina: Inteligência Artificial
6
5
Professor: Frederico Brito Fernandes
33/27
(5) Busca em profundidade
• Expande o nó mais profundo ainda não expandido
• Quando encontra um nó que não pode ser expandido, volta
para expandir os outros dos níveis mais rasos
• Borda organizada como uma pilha (LIFO)
1
2
3
4
Disciplina: Inteligência Artificial
5
6
7
Professor: Frederico Brito Fernandes
34/27
(5) Busca em profundidade
• Expande o nó mais profundo ainda não expandido
• Quando encontra um nó que não pode ser expandido, volta
para expandir os outros dos níveis mais rasos
• Borda organizada como uma pilha (LIFO)
1
2
3
4
Disciplina: Inteligência Artificial
5
6
7
8
Professor: Frederico Brito Fernandes
35/27
(5) Busca em profundidade
• Expande o nó mais profundo ainda não expandido
• Quando encontra um nó que não pode ser expandido, volta
para expandir os outros dos níveis mais rasos
• Borda organizada como uma pilha (LIFO)
1
2
3
4
Disciplina: Inteligência Artificial
5
9
6
7
8
Professor: Frederico Brito Fernandes
36/27
(5) Busca em profundidade
• Expande o nó mais profundo ainda não expandido
• Quando encontra um nó que não pode ser expandido, volta
para expandir os outros dos níveis mais rasos
• Borda organizada como uma pilha (LIFO)
1
2
3
4
Disciplina: Inteligência Artificial
5
9
6
7
10
8
Professor: Frederico Brito Fernandes
37/27
(5) Busca em profundidade
• Completude: Sim, somente se o
espaço de estados não tiver laços
• Custo Memória: Armazena
somente um caminho simples da
raiz até a folha.
1
2
– Para um fator de ramificação b e
uma profundidade máxima de m
armazena
bm nós (busca
em largura = bd)
• Custo Tempo: O(bm) no pior
caso -> examinar todos os ramos
– Terrível se m é muito maior que
d (m - profundidade máxima de
qq nó)
• Otimalidade: Não
• Necessita de um espaço de
busca finito e não cíclico
Disciplina: Inteligência Artificial
3
4
9
6
5
7
10
m
8
b = número máximo de filhos
(ou fator de ramificação)
m = altura máxima da árvore
Esteja certo de que entende que m  d
Professor: Frederico Brito Fernandes
38/27
(6) Busca com Profundidade Limitada
• Evita os problemas da busca em profundidade impondo um
corte na profundidade de caminho
• Problema => escolher a profundidade correta
• Completude: Sim. Se a solução existente estiver em uma
profundidade d<l, ela é encontrada
• Otimalidade: Não. A solução ótima pode estar em outra
subárvore
• Tempo: O(bl), onde l é o limite de profundidade
• Memória: O(bl)
• Alguns problemas sugerem um valor de l. (20 cidades => l
=19)
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
39/27
(7) Busca com Profundidade Interativa
• Tenta todos os possíveis limites de profundidade,
começando pelo 0.
• Combina os benefícios da busca em largura e em
profundidade
• Ordem de expansão parecida com a busca em
largura
– Alguns nós podem ser expandidos múltiplas vezes
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
40/27
(7) Busca com Profundidade Interativa
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
41/27
(7) Busca com Profundidade Interativa
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
42/27
(7) Busca com Profundidade Interativa
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
43/27
(7) Busca com Profundidade Interativa
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
44/27
(7) Busca com Profundidade Interativa
•
•
•
•
•
•
Completude: Sim
Otimalidade: Sim (se o custo do caminho for uma função não decrescente da
profundidade do nó,ou seja, quando todos os caminhos tiverem o mesmo custo)
Tempo: O(bd) – alguns nós podem ser gerados várias vezes. Mas isso acontecerá nos
níveis superiores que normalmente têm poucos nós
Memória: O(bd)
Preferida quando o espaço de busca é muito grande e a profundidade da solução não
é conhecida
Tempo comparação com a busca em largura com b=10 e d=5
– Prof. Interativa = 123.450 nós gerados
– Largura = 1.111.100 nós gerados
•
É o método de busca sem informação preferido quando existe um espaço de busca
grande e a profundidade da solução não é conhecida
b = número máximo de filhos
(ou fator de ramificação)
d = altura do nó ótimo
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
45/27
(8) Busca Bidirecional
• Busca em duas direções:
– Para frente, a partir do nó
inicial, e
– Para trás, a partir do nó final
(objetivo)
• A busca pára quando os dois
processos geram o mesmo
nó
• Problema: verificar antes de
cada expansão se o nó não
pertence à borda da outra
busca
• É possível utilizar
estratégias diferentes em
cada direção da busca
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
46/27
(8) Busca Bidirecional
• A comparação de cada nó antes da expansão pode
ser feita em tempo constante utilizando uma tabela
hash
• Completude: Sim
• Otimalidade: Sim
• Tempo: O(bd/2)
• Memória: O(bd/2)
• Para b=10 e d=6 temos 22.200 nós gerados, contra
os 11.111.100 da busca em largura
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
47/27
(9) Comparação das Estratégias de Busca
Largura
Custo
Uniforme
Profundidade
Profundidade
limitada
Profundidade
Interativa
Bidirecional (se
aplicável)
Tempo
O(bd + 1)
O(bd + 1)
O(bm)
O(bl)
O(bd)
O(bd/2)
Espaço
>>bd
>>bd
O(bm)
O(bd)
O(bd/2)
Otima?
Sim3
Sim
Não
O(bl)
Não
sim3
Sim3,4
Completa?
sim1
sim1,2
Não
Sim
Sim1
Sim1,2
1 – completa se b é finito
2 – completa se o custo do passo é >= c, para c positivo
3 – ótima se o custo dos passos são todos idênticos
4 – se ambos os sentidos utilizam busca em largura
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
48/27