Inteligência

Artificial – ADS-
M3
AGENTES E PROBLEMAS DE BUSCA

PROF. ROGÉRIO FIGUEREDO DE SOUSA

ro g er io. sous a@ifpi. edu.br
Busca sem
Informação
O que estudamos até aqui
• Agentes
• Tipos de agentes
• Agentes planejadores
• Plano
• Problema de busca
• Estratégia de busca (conceito)

3
Estratégias de Busca sem Informação

Estratégias
de busca

Sem Com
informação informação

Greedy
BFS DFS UCS DLS IDS ... A* Search ...
Search

4
Estratégias de Busca sem Informação
• Estratégias de busca sem informação (ou busca cega - blind search)
usam apenas a informação disponível na formulação do problema de
busca para escolher o plano.
• Se distinguem pelo critério usado para selecionar um nó na
fronteira para ser expandido.
• Busca em Largura (breadth-first search, BFS)
• Busca com Custo Uniforme (uniform-cost search, UCS)
• Busca em Profundidade (depth-first search, DFS)
• Busca em Profundidade Limitada (depth-limited search, DLS)
• Busca em Profundidade Iterativa (iterative deepening search, IDS)

5
Busca em Largura (Breadth-First
Search - BFS)

6
BFS
• Estratégia: expandir a árvore de busca usando o nó que esteja mais
perto da raiz.
• “BFS: do all the shallow things before we go the the deep things.”
• Todos nós na profundidade d da árvore devem ser expandidos e
visitados antes dos nós na profundidade d+1.
• Implementação:
• a borda é uma fila FIFO (first-in, first-out), isto é, novos itens entram no final.

7
 BFS: exemplo
Estratégia: expandir primeiro o nó mais próximo da raiz
Implementação: borda é uma fila FIFO

d e p G
a
Camadas da b c
busca b c e h r q
e
d f
a a h r p q f S h
p q r
p q f q c G

q c a
G
a

8
 Exemplo: BFS versus maze
solving

Fonte: https://www.cs.iusb.edu/~danav/teach/c463/4_blind_search.html 9
 Exemplo: BFS versus maze
solving

Fonte: https://en.wikipedia.org/wiki/Breadth-first_search#/media/File:BFS-Algorithm_Search_Way.gif 10
 Exemplo: cidades alemãs

Grafo de espaço Árvore de busca

de estados

Fonte: https://en.wikipedia.org/wiki/Breadth-first_search 11
 Propriedades de uma Estratégia de
12
Busca
• Estratégias são avaliadas de acordo com os seguintes critérios:
• Completa? Sempre encontra a solução, se alguma existe?
• Complexidade de tempo: Número de nós gerados no pior caso
• Complexidade de espaço: Número máximo de nós na memória no pior caso
• Ótima? Garante encontrar a solução ótima? 1 nó
b
• Esboço de uma árvore de busca (pior caso): … b nós

• b é o máximo fator de ramificação b2 nós

• m é a profundidade máxima m níveis
• pode haver soluções (em rosa) em vários níveis

• Número de nós na árvore?

• 1 + b + b2 + …. bm = O(bm)
bm nós
BFS: propriedades
• Completa?
• Sim (se b é finito)
• Complexidade de tempo?
• 1 + b + b2 + b3 + … + bd = O(bd)
• Complexidade de espaço?
• O(bd) (mantém todos os nós na memória até encontrar o objetivo;
complexidade é dominada pelo tamanho da borda.)
• Ótima?
• Sim (se todas as ações tiverem o mesmo custo, i.e., se o custo do
caminho for uma função não-decrescente da profundidade do nó.)

13
BFS: requisitos de tempo e
memória
• Suposições
• Problema de busca com fator de ramificação b=10;
• 1.000.000 nós podem ser gerados por segundo;
• Um nó exige 1KB de espaço.

AIMA, Figure 3.13 14

BFS:
implementação

search.py

15
Busca com Custo Uniforme (Uniform Cost
Search, UCS)

16
UCS
• Similar à BFS, só que expande o nó ainda não expandido n que
tenha o custo de caminho g(n) mais baixo.
• Implementação:
• fronteira = fila ordenada por g(n) (i.e., uma fila de prioridades)
• Equivalente à busca em largura se os custos são todos iguais.
• Particularidades da UCS:
• O teste de objetivo é aplicado a um nó quando ele é selecionado para
expansão, e não quando ele é gerado.
• Há um teste para verificar se um caminho para um nó na fronteira é mais
curto do que algum previamente encontrado.

17
 2 a G
b 8
c
1 2
2 e
3 d

UCS
9 2 f
S h 8 1
1 p r
q
15

Estratégia: expandir o nó mais barato primeiro:

Borda é uma fila de prioridade com chave igual ao custo cumulativo, g(n).

S 0

3 e 9 p 1
d

b 4 c e 5 h 17 r 11 q 16
11
Curvas de a 6 a h 13 r 7 p q f
custo

p q f 8 q c G

q 11 c a
G 10
a

18
UCS: algoritmo e exemplo

19
UCS: algoritmo e exemplo
Fronteira: {(S,0)}

20
UCS: algoritmo e exemplo
Fronteira: {(SR,80); (SF,99)}

Os sucessores de Sibiu são

Rimnicu Vilcea e Fagaras,
S
com custos de 80 e 99,
respectivamente.

R F

21
UCS: algoritmo e exemplo
Fronteira: {(SRP,177); (SF,99)}

O nó de menor custo, Rimnicu

Vilcea, é expandido em
S
seguida, acrescentando Pitesti
com custo de 80 + 97 = 177.

R F

22
UCS: algoritmo e exemplo
Fronteira: {(SRP,177); (SFB,310)}

O nó de menor custo é agora

Fagaras; sendo assim, ele é
S
expandido, acrescentando
Bucareste com custo 99 + 211
= 310.
R F

P B

23
UCS: algoritmo e exemplo
Fronteira: {(SRP,177); (SFB,310)}

Agora um nó objetivo foi

gerado, mas o algoritmo
S
continua escolhendo SRP para
expansão.

R F

P B

24
UCS: algoritmo e exemplo
Fronteira: {(SRPB,278); (SFB,310)}

Como resultado, um segundo

caminho para Bucareste (com
S
custo 80 + 97 + 101 = 278) é
adicionado à fronteira.

R F

P B

25
UCS: algoritmo e exemplo
Fronteira: {(SFB,310)}

O algoritmo agora seleciona

para expansão o plano de
S
menor custo. Repare que o
plano anterior é descartado
(i.e., permanece da fronteira).
R F

P B

26
UCS: algoritmo e exemplo

O novo plano, com o valor

g(SRPB) = 278, é a solução
S
encontrada.

R F

P B

27
UCS: propriedades
• Completa? Sim, se o custo de cada passo ≥ ε b
c1
…
c2
C*/ “tiers”
• Complexidade de Tempo? Quantidade de nós
c3
com g ≤ custo da solução ótima, O(bC*/ ε) onde
C* é o custo da solução ótima

• Complexidade de Espaço? Quantidade de nós

com g ≤ custo da solução ótima, O(b C*/ ε )

• Ótima? Sim, pois os nós são expandidos em

ordem crescente de custo total.
28
UCS:
implementação

30
Busca em Profundidade (Depth First Search
- DFS)

31
 DFS: exemplo
Estratégia: expandir primeiro o nó mais distante da raiz a G
Implementação: borda é uma pilha LIFO (Stack) b c
e
d f
S h
p q r

d e p

b c e h r q

a a h r p q f

p q f q c G

q c a
G
a 32
DFS: implementação

33
DFS: propriedades
1 node
b
• Complexidade de tempo? … b nodes
• A DFS expande algum prefixo à esquerda da
b2 nodes
árvore de busca.

m níveis
• Potencial de processar a árvore inteira!
• Se m é finito, complexidade de espaço é O(bd)

• Complexidade de espaço?
• Tem apenas “irmãos” no caminho para
a raiz, então O(bd) bm nodes

• Completa?
• d pode ser infinito, então completa apenas se evitar ciclos (ver DLS)

• Ótima?
• Não. DFS encontra a solução “mais à esquerda” na árvore de busca, independente da profundidade ou custo
correspondente.

34
Busca em Profundidade Limitada
(Depth-limited search - DLS)

35
Busca em profundidade limitada
(depth limited search, DLS)
• DFS não vai encontrar um objetivo se a busca entrar em um
caminho de comprimento infinito.
• A menos que evite ciclos.
• Solução (DLS): definir um limite de profundidade (𝑙) para a
árvore a ser expandida.
• Planos com profundidade maior do que 𝑙 na árvore de busca não são
expandidos.
• A DFS é um caso particular da DLS, com 𝑙 = ∞.
36
Busca em profundidade limitada
(DLS) – valor de 𝑙
• Repare que, se 𝑙 for...
• ...muito pequeno (i.e., o objetivo se encontra em uma
profundidade maior do que 𝑙), uma solução não será
encontrada.
• ...muito grande, soluções subótimas podem ser encontradas.
• Estratégia útil quando a profundidade máxima
da solução para o problema de busca é
conhecida.
37
Busca em profundidade limitada
(DLS) – valor de 𝑙
• Qual seria um valor adequado para 𝑙 no caso do problema da Romênia?
• Há 20 cidades no mapa; então não existe plano com mais de 19 ações.
• Na verdade, cada cidade pode ser alcançada a partir de outra com até 9 ações.

38
 Busca em profundidade limitada
(DLS) - exemplos
𝑙=3
{A}
{AZ, AS, AT}
{AZ, ASF, ASR, ASO, AT}
{AZ, ASFB, ASR, ASO, AT}

Solução encontrada (ASFB)

𝑙=2
{A}
{AZ, AS, AT}
{AZ, ASF, ASR, AT}
{AZ, ASR, AT}
{AZ, AT}
{AZ, ATL}
{AZ}
{AZO}
{}

Solução não encontrada

NB: ignorando nós mais recentemente expandido

39
DLS: pseudocódigo
Implementação recursiva:

cutoff indica que o limite de

profundidade foi alcançado.

chamada recursiva

failure indica que nenhuma

solução foi encontrada

40
41
DLS: propriedades
• Completa? Não, pois a solução (objetivo) pode estar
além do limite de profundidade estabelecido (i.e., pode
ser que 𝑙 < 𝑑).
• Tempo? O(𝑏 𝑙 )
• Espaço? O(𝑏𝑙)
• Ótima? Não

42
Busca em Profundidade Iterativa
(Depth-First Iterative Deepening Search, IDS)

43
IDS
• A IDS consiste em aplicar repetidamente a busca em
profundidade limitada (DLS), com limites gradativamente
crescentes.
• A IDS termina quando uma solução for encontrada, ou se
a busca em profundidade limitada retorna falha (failure),
o que significa que não existe uma solução.

44
IDS

45
IDS – exemplo: 𝑙 = 0

46
IDS – exemplo: 𝑙 = 1

47
IDS – exemplo: 𝑙 = 2

48
IDS – exemplo: 𝑙 = 3

49
 IDS – exemplo
• Considere o grafo de espaço de estados a
seguir, em que A é o estado inicial.
• Qual a ordem dos estados visitados pela
IDS para sucessivos valores de 𝑙?

50
Fonte do exemplo: Wikipedia (https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search)
 IDS – exemplo (cont.)
• 𝑙 = 0: A
• 𝑙 = 1: A, B, C, E
• Observe que a IDS já viu C; uma busca usando DFS não
o faria.
• 𝑙 = 2: A, B, D, F, C, G, E, F
• Note que IDS ainda vê C, mas um pouco depois. Note
também que ele vê E por meio de um caminho
diferente, e volta em F duas vezes.
• 𝑙 = 3: A, B, D, F, E, C, G, E, F, B
51
Fonte do exemplo: Wikipedia (https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search)
IDS versus BFS
• Número de nós gerados na BFS com fator de
ramificação b:
NBFS = 𝑏1 + 𝑏2 + 𝑏3 + ⋯ + 𝑏𝑑
• Número de nós gerados na IDS até a profundidade d
com fator de ramificação b:
NIDS = 𝑑 𝑏1 + 𝑑 − 1 𝑏2 + 𝑑 − 2 𝑏3 + ⋯ + (1)𝑏𝑑
• Por exemplo, para 𝑏 = 10, 𝑑 = 5:
• NBFS = 10 + 100 + 1.000 + 10.000 + 100.000 = 111.100
• NIDS = 50 + 400 + 3.000 + 20.000 + 100.000 = 123.450
• Overhead = (123.456 – 111.110)/111.110 = 11%
52
IDS – propriedades (cont.)
• Completa? Sim
• Tempo? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd)
• Espaço? O(bd)
• Ótima? Sim, se custo de caminho = 1

• Repare que a IDS usa somente espaço linear e não muito

mais tempo que outros algoritmos de busca sem informação.

53
IDS – implementação

54
Considerações finais
Comentários finais
• A formulação de problemas usualmente requer a
abstração de detalhes do mundo real para que seja
definido um espaço de estados que possa ser explorado
por meio de algoritmos de busca.
• Há uma variedade de estratégias de busca sem
informação (ou busca cega) além dos estudados aqui.

56
Comentários finais
• Algoritmos de busca ainda ocupam uma posição
fundamental no projeto de agentes inteligentes.
• Diversas abordagens em IA têm alguma relação com
algum tipo de busca em estados.
• Ler o cap. 3 do livro texto (Russell & Norvig)
• Ver documentário “AlphaGo” (procurar no Youtube)

57
Próxima aula

Estratégias
de busca

Sem Com
informação informação

Greedy
BFS DFS UCS DLS IDS ... A* Search ...
Search

58