busca-sem-informacao

Prévia do material em texto

1 
Aula 03 
Métodos de busca 
sem informação 
Prof. Dr. Alexandre da Silva Simões 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 2 9-11 
Problema dos jarros de água 
 Existem dois vasos: um de 4 litros e um de 3 litros, inicialmente 
vazios, e uma fonte que jorra água em abundância. Objetivo: 
Conseguir 2 litros em qualquer um dos vasos. 
  Ações possíveis: 
  Encher os vasos 
  Esvaziar os vasos 
  Completar um vaso com outro 
  Jogar um vaso em outro 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 3 9-11 
Revisão... 
  Tipos de agente: 
•  Agente reativo simples: Seleciona ações com base na 
percepção atual, ignorando o restante do histórico das 
percepções 
•  Agente baseado em modelo: Controla a parte do mundo que 
ele não pode ver agora mantendo um estado interno que 
depende do histórico de percepções 
•  Agente baseado em objetivo: Combina seu objetivo com as 
informações sobre os resultados de ações possíveis a fim de 
escolher ações que alcancem os seus objetivos 
•  Agente baseado em utilidade: Utilizam uma medida de 
desempenho (função de utilidade) que permite uma comparação 
entre diferentes estados do mundo, permitindo selecionar a 
seqüência de ações 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 4 9-11 
Agente baseado em objetivo 
Como um agente pode encontrar uma 
seqüência de ações que alcança seus 
objetivos quando nenhuma ação isolada 
é capaz de fazê-lo? 
2 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 5 9-11 
Resolução de problemas por meio 
de busca 
  Objetivo: ir de Arad a Bucharest 
  Questão: como modelar o problema? 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 6 9-11 
Definição de um problema 
  Componentes: 
1.  Estado inicial: onde o agente começa. Ex: Em(Arad) 
2.  Ações do agente: 
 SUCESSOR(x) retorna um conjunto de 
 pares ordenados <ação, sucessor>, em 
 que cada ação é uma das ações válidas 
 no estado x 
 Exemplo: estando em Arad: {<Ir(Sibiu), Em(Sibiu)> , 
<Ir(Timisoara), Em(Timisoara)>, <Ir(Zerind),Em(Zerind)>} 
3.  Teste de objetivo: determina se um dado estado é o estado-
objetivo (ou meta) 
4.  Custo de caminho: função que atribui um custo numérico a 
cada caminho 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 7 9-11 
Mundo do aspirador de pó 
  Estado inicial: qualquer estado 
  Função sucessor: gera estados válidos que resultam da tentativa 
de executar as três ações (L:Esquerda, R:Direita e S:Aspirar). O 
espaço de estados é: 
  Teste de objetivo: verifica se todos os quadrados estão limpos 
  Custo do caminho: Cada passo custa 1 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 8 9-11 
Quebra-cabeça de 8 peças 
  Estado inicial: qualquer estado 
  Função sucessor: gera os estados válidos que resultam da 
tentativa de executar as quatro ações: espaço vazio se desloca 
para Esquerda, Direita, Acima, Abaixo. 
  Teste de objetivo: verifica se o estado corresponde à configuração 
final 
  Custo do caminho: cada passo custa 1 
3 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 9 9-11 
Problema das 8 rainhas 
  Estado inicial: tabuleiro vazio 
  Função sucessor: colocar uma rainha em qualquer quadrado vazio 
  Teste de objetivo: 8 rainhas estão no tabuleiro e nenhuma é 
atacada 
  Custo do caminho: sem interesse (apenas o estado final é 
importante) 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 10 9-11 
Problemas do mundo real... 
•  Problemas de determinação de trajetórias (redes de 
computadores, planejamento de ações militares, viagens 
aéreas, ...) 
•  Problemas de layout de VLSI 
•  Problemas de navegação de robôs 
•  Problemas de seqüência automática de montagens 
•  Projeto de proteínas 
•  Pesquisas na internet 
•  ... 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 11 9-11 
Em busca de soluções... 
  Busca no espaço de estados 
1.  Estado atual 
2.  Expansão 
3.  Geração de novos estados 
  Técnicas de busca em árvore: 
 qual a melhor estratégia? 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 12 9-11 
Algoritmo geral de busca em árvore 
função BUSCA-EM-ÁRVORE (problema, estratégia) retorna uma solução ou 
falha 
 inicializar a árvore de busca usando o estado inicial do problema 
 repita 
 se não existe candidato para expansão então retornar falha 
 escolher um nó folha para expansão de acordo com estratégia 
 se o nó contém estado objetivo então retornar a solução 
 senão expandir o nó e adicionar nós resultantes à árvore de busca 
4 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 13 9-11 
Componentes de um nó 
  Estado: o estado no espaço de estados a que o nó corresponde 
  Nó-pai: O nó na árvore de busca que gerou esse nó 
  Ação: A ação que foi aplicada ao pai para gerar o nó 
  Custo do caminho: o custo, tradicionalmente denotado por g(x), do 
caminho desde o estado inicial até o nó 
  Profundidade: O número de passos ao longo do caminho, desde o 
estado inicial 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 14 9-11 
Representando uma coleção de nós 
  Coleção de nós: fila 
  Possíveis operações sobre a fila: 
•  CRIAR-FILA(elemento, ...): cria uma fila com o(s) elemento(s) 
dado(s) 
•  VAZIA?(fila): retorna verdadeiro somente se não existir mais 
nenhum elemento na fila 
•  PRIMEIRO(fila): retorna o primeiro elemento da fila 
•  REMOVER-PRIMEIRO(fila): retorna PRIMEIRO(fila) e o remove 
da fila 
•  INSERIR(elemento, fila): insere um elemento na fila e retorna a 
fila resultante 
•  INSERIR-TODOS(elementos, fila): insere um conjunto de 
elementos na fila e retorna a fila resultante 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 16 9-11 
Estratégias para expansão de nós 
 Estratégias de busca cega (sem 
informação sobre o problema): 
•  Busca em extensão 
•  Busca com custo uniforme 
•  Busca em profundidade 
•  Busca em profundidade limitada 
•  Busca de aprofundamento iterativo 
•  Busca bidirecional 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 17 9-11 
Busca em extensão (breadth first) 
•  O nó raiz é expandido primeiro, em seguida todos os 
sucessores no só raiz, depois os sucessores desses nós 
e assim por diante 
•  Pode ser implementada fazendo: 
 BUSCA-EM-ÁRVORE(problema, FILA-FIFO( )) 
•  FILA “First In First Out”: 
•  Coloca todos os sucessores recém-chegados no final da fila 
•  Escolhe como sucessor o primeiro nó da fila (nós de baixa 
profundidade expandidos primeiro) 
5 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 18 9-11 
Busca em extensão: exemplo 
Fila: 
adicionar: 
 A 
expandir: 
Meta 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 19 9-11 
Busca em extensão: exemplo 
Fila: 
adicionar: 
 B C 
expandir: 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 20 9-11 
Busca em extensão: exemplo 
Fila: 
adicionar: 
 C D E 
expandir: 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 21 9-11 
Busca em extensão: exemplo 
Fila: 
adicionar: 
 D E F G 
expandir: 
6 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 22 9-11 
Busca em extensão: exemplo 
Fila: 
adicionar: 
 E F G 
expandir: 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 23 9-11 
Busca em extensão: exemplo 
Fila: 
adicionar: 
 F G 
expandir: 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 24 9-11 
Busca em extensão: exemplo 
Fila: 
adicionar: 
 F G 
expandir: 
Meta! 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 25 9-11 
Medidas de desempenho 
  Completeza: O algoritmo oferece a garantia de 
encontrar uma solução quando ela existir? 
  Otimização: A estratégia encontra a solução 
ótima? 
  Complexidade de tempo: Quanto tempo ele 
leva para encontrar uma solução? 
  Complexidade de espaço: Quanta memóriaé 
necessária para executar a busca? 
7 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 26 9-11 
Busca em extensão: desempenho 
Sejam: b: número médio de sucessores de cada nó 
 d: profundidade da solução mais rasa 
  Completeza: completa, desde que d seja finita 
  Otimização: ótima, se todos os caminhos têm o mesmo custo 
  Complexidade de tempo: 
  Nós por nível: 1→b1, 2→b2, 3→b3, ..., n→bn 
  Todos os nós são expandidos até o nível d, exceto o último (solução). 
Assim: b+b2+b3+...+bd+(bd+1-b) = O(bd+1) 
  Complexidade de memória: 
 Os nós que já foram visitados precisam ser armazenados em um outro 
vetor na memória, pois pode ser necessário consultá-los após encontrar a 
meta para determinar o caminho do estado inicial à meta. 
 Logo, todo nó permanece na memória (complexidade de espaço é igual 
à complexidade de tempo) 
d 
b 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 27 9-11 
Busca em extensão: resumo 
  Sempre expande o nó mais raso 
  Requisitos de memória e tempo são um grande problema 
Supondo b=10, análise de 10.000 nós/segundo e 1.000 bytes/nó 
Profundidade Nós Tempo Memória 
2 1100 0,11 seg 1 megabytes 
4 111.100 11 seg 106 megabytes 
6 107 19 min 10 gigabytes 
8 109 31 horas 1 terabyte 
10 1011 129 dias 101 terabytes 
12 1013 35 anos 10 pentabytes 
14 1015 3.523 anos 1 exabyte 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 28 9-11 
Busca de custo uniforme 
•  Busca em amplitude: ótima quando os custos de todos 
os passos são iguais 
•  Busca de custo uniforme: em vez de expandir o nó mais 
raso, expande o nó com o caminho de custo mais baixo. 
Expande os nós em ordem de custo crescente 
•  “Não importa o número de passos que o caminho tem, 
mas apenas o seu custo total” 
•  Se todos os custos de passos são iguais, é idêntica à 
busca em extensão 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 29 9-11 
Busca de custo uniforme: exemplo 
A 
B C D 
E F G H I J K L M 
5 7 9 
A 
B C D 
E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
 E F G H I J K L M 
7 10 6 
(15) (13) (12) (17) (13) (14) 
5 7 
9 
10 
8 7 
A 
B C D 
E F G H I J K L M 
(15) (13) (12) 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (10) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (10) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
8 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 30 9-11 
Busca de custo uniforme: exemplo 
A 
B C D 
E F G H I J K L M 
5 7 9 
A 
B C D 
E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
 E F G H I J K L M 
7 10 6 
(15) (13) (12) (17) (13) (14) 
5 7 
9 
10 
8 7 
A 
B C D 
E F G H I J K L M 
(15) (13) (12) 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (10) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (10) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 31 9-11 
Busca de custo uniforme: exemplo 
A 
B C D 
E F G H I J K L M 
5 7 9 
A 
B C D 
E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
 E F G H I J K L M 
7 10 6 
(15) (13) (12) (17) (13) (14) 
5 7 
9 
10 
8 7 
A 
B C D 
E F G H I J K L M 
(15) (13) (12) 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (10) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (10) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 32 9-11 
Busca de custo uniforme: exemplo 
A 
B C D 
E F G H I J K L M 
5 7 9 
A 
B C D 
E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
 E F G H I J K L M 
7 10 6 
(15) (13) (12) (17) (13) (14) 
5 7 
9 
10 
8 7 
A 
B C D 
E F G H I J K L M 
(15) (13) (12) 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (10) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (10) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 33 9-11 
Busca de custo uniforme: exemplo 
A 
B C D 
E F G H I J K L M 
5 7 9 
A 
B C D 
E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
 E F G H I J K L M 
7 10 6 
(15) (13) (12) (17) (13) (14) 
5 7 
9 
10 
8 7 
A 
B C D 
E F G H I J K L M 
(15) (13) (12) 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (12) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (10) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
9 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 34 9-11 
Busca de custo uniforme: exemplo 
A 
B C D 
E F G H I J K L M 
5 7 9 
A 
B C D 
E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
 E F G H I J K L M 
7 10 6 
(15) (13) (12) (17) (13) (14) 
5 7 
9 
10 
8 7 
A 
B C D 
 E F G H I J K L M 
(15) (13) (12) 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (12) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
5 7 
9 
10 
8 7 
A 
B C D 
7 10 6 
(15) (13) (12) (12) (11) (10) (17) (13) (14) 
3 2 1 
 E F G H I J K L M 
Explora grandes árvores de pequenos passos antes de explorar caminhos 
envolvendo passos grandes. 
Meta! 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 35 9-11 
Busca de custo uniforme: desempenho 
•  Difícil caracterizar em termos de b e d, já que a busca é orientada a 
caminho 
•  Como o algoritmo pode explorar soluções mais profundas do que d 
primeiro, sua complexidade pode ser maior do que O(bd) 
•  Desempenho: 
•  Completeza: completa 
•  Otimização: ótima 
•  Complexidade de tempo e memória: O(b[C*/ ε]) 
  Custo da solução ótima: C* 
  Custo de cada passo > ε 
  A árvore pode ser reinterpretada como 
 dependente do custo. No pior caso, todos 
 os nós com custo menor do que C* serão 
 analisados primeiro 
ε 
2ε 2ε 
ε 
. . . C* 
b 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 36 9-11 
Busca em profundidade (depth first) 
  Sempre expande o nó mais profundo 
 na árvore de busca. 
  Pode ser implementado fazendo: 
 BUSCA-EM-ÁRVORE(problema, PILHA( )) 
 ou usando função recursiva 
  Pilha (Last in First Out): 
•  Coloca todos os sucessores recém-chegados no topo 
da pilha 
•  Escolhe como sucessor o primeiro nó da fila (nós 
chegados por último expandidos primeiro) 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 37 9-11 
Busca em profundidade 
 Pilha: 
 
 A 
Meta 
10 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 38 9-11 
Busca em profundidade 
 Pilha: 
 
 B 
 C 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 39 9-11 
Busca em profundidade 
 Pilha: 
 
 D 
 E 
 C 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 40 9-11 
Busca em profundidade 
 Pilha:H 
 I 
 E 
 C 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 41 9-11 
Busca em profundidade 
 Pilha: 
 
 I 
 E 
 C 
11 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 42 9-11 
Busca em profundidade 
 Pilha: 
 
 E 
 C 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 43 9-11 
Busca em profundidade 
 Pilha: 
 
 J 
 K 
 C 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 44 9-11 
Busca em profundidade 
 Pilha: 
 
 K 
 C 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 45 9-11 
Busca em profundidade 
 Pilha: 
 
 C 
12 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 46 9-11 
Busca em profundidade 
 Pilha: 
 
 F 
 G 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 47 9-11 
Busca em profundidade 
 Pilha: 
 
 L 
 M 
 G 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 48 9-11 
Busca em profundidade 
 Pilha: 
 
 M 
 G 
Meta! 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 49 9-11 
Busca em profundidade: desempenho 
Sejam: b: número médio de sucessores 
 m: profundidade máxima 
  Completeza: não é completa (se um ramo não tiver fim, a busca 
em profundidade nunca termina) 
  Otimização: não é ótima (não retorna necessariamente o nó com 
menor custo) 
  Complexidade de tempo: O(bm) 
  Complexidade de memória: Uma vez que um ramo da memória 
(um nó e seus descendentes) tenha sido completamente explorado, 
essa parte do caminho pode ser removida da memória. É essencial 
que permaneçam na memória apenas um único caminho da raiz até 
o nó folha sendo analisado, juntamente com os seus nós irmãos 
não-expandidos. 
 Logo: armazena bm+1 nós, isto é: O(bm) 
m 
b 
13 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 50 9-11 
Busca em profundidade limitada 
 Busca em profundidade com limite de 
profundidade limitado em L 
 Desempenho: 
•  Completeza: incompleta se L<d 
•  Otimização: Não será ótima se L>d 
•  Complexidade de tempo: O(bL) 
•  Complexidade de memória: O(bL) 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 51 9-11 
Busca em profundidade limitada: algoritmo 
função BUSCA-EM-PROFUNDIDADE-LIMITADA (problema, limite) retorna uma 
solução ou falha/corte 
 retorna BPL-RECURSIVA(CRIAR-NÓ(ESTADO-INICIAL[problema]), problema, limite) 
função BPL-RECURSIVA(nó, problema, limite) retorna uma solução ou falha/corte 
 corte_ocorreu? ← falso 
 se TESTAR-OBJETIVO[problema](ESTADO[nó]) então retornar SOLUÇÃO(nó) 
 senão se (PROFUNDIDADE[nó]=limite) então retornar corte 
 senão para cada sucessor em EXPANDIR(nó, problema) faça 
 resultado ← BPL-RECURSIVA(sucessor, problema, limite) 
 se (resultado=corte) então corte_ocorreu? ← verdadeiro 
 senão se (resultado ≠falha) então retornar resultado 
 se corte_ocorreu? então retornar corte senão retornar falha 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 52 9-11 
Busca de aprofundamento iterativo 
  Aumenta gradativamente o limite de profundidade (0,1,2,...) até 
encontrar o objetivo (L=d) 
  Combina as vantagens da busca em largura e profundidade 
  Algoritmo: 
função BUSCA-POR-APROFUNDAMENTO-ITERATIVO(problema) retorna uma 
solução ou falha 
 
 para profundidade ← 0 até ∞ faça 
 resultado ← BUSCA-EM-PROFUNDIDADE-LIMITADA(problema, 
 profundidade) 
 se (resultado≠corte) então retornar resultado 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 53 9-11 
Busca de aprofundamento iterativo 
14 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 54 9-11 
Busca de aprofundamento iterativo 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 55 9-11 
Busca de aprofundamento iterativo 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 56 9-11 
Busca de aprofundamento iterativo 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 57 9-11 
Busca de aprofundamento iterativo: 
desempenho 
  Completeza: completo, como na busca em extensão 
  Otimização: ótimo, como na busca em extensão 
  Complexidade de tempo: 
 Pode parecer um desperdício, mas... 
 Os nós do primeiro nível são gerados d vezes, os nós 
do segundo nível são gerados (d-1) vezes, e assim 
sucessivamente... 
 Logo: (d)b + (d-1)b2 + ... + (1)bd → O(bd) 
  Complexidade de memória: trata-se de uma busca em 
profundidade. Logo: O(b.d) 
15 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 58 9-11 
Busca bidirecional 
  Executar duas buscas simultâneas: uma do estado 
inicial para o objetivo, outra do objetivo para o estado 
inicial, parando quando as buscas se encontram no 
estado intermediário 
  Motivação: bd/2+bd/2 é muito menor que bd 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 59 9-11 
Busca bidirecional 
  Desempenho: 
•  Completeza: completo 
•  Otimização: ótimo (para passos de custo uniforme) 
•  Complexidade de tempo: O(bd/2) 
•  Complexidade de espaço: O(bd/2) 
  Restrições: 
•  O objetivo precisa ser conhecido 
•  Os predecessores de um nó precisam ser 
computáveis 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 60 9-11 
Estratégias de busca sem 
informação: quadro comparativo 
Critério Em 
extensão 
Custo 
uniforme 
Em 
profund. 
Em 
profund. 
limitada 
Aprofund.
iterativo 
Bidirec. 
(se 
aplicável) 
Completa Sim Sim Não Não Sim Sim 
Tempo O(bd+1) O(b[C*/ ε]) O(bm) O(bL) O(bd) O(bd/2) 
Espaço O(bd+1) O(b[C*/ ε]) O(bm) O(bL) O(bd) O(bd/2) 
Ótima Sim Sim Não Não Sim Sim 
Exercício 
16 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 62 9-11 
Problema dos jarros de água 
 Existem dois vasos: um de 4 litros e um de 3 litros, inicialmente 
vazios, e uma fonte que jorra água em abundância. Objetivo: 
Conseguir 2 litros em qualquer um dos vasos. 
  Ações possíveis: 
  Encher os vasos 
  Esvaziar os vasos 
  Completar um vaso com outro 
  Jogar um vaso em outro 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 63 9-11 
Problema dos jarros de água: modelagem 
  Estado: (x,y), onde: 
  x é a quantidade de água no vaso de 4 Litros; 
  y é a quantidade de água no vaso de 3 Litros; 
  Estado inicial: (0,0) 
  Estados-meta: (X,2) ou (2,X) 
  Regras: 
  R0: Encher_vaso_4 
  R1: Encher_vaso_3 
  R2: Esvaziar_vaso_4 
  R3: Esvaziar_vaso_3 
  R4: Completar_3_com_4 
  R5: Completar_4_com_3 
  R6: Esvaziar_4_em_3 
  R7: Esvaziar_3_em_4 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 64 9-11 
Problema dos jarros de água: solução 
 Busca em largura: Busca em profundidade: 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 65 9-11 
Problema dos jarros de água: outras 
soluções 
 Busca em largura: Busca em profundidade: 
17 
Inteligência Artificial - Prof. Dr. 
Alexandre da Silva Simões 66 9-11 
Atividades extra-classe 
 Leitura: 
 RUSSELL, S. NORVIG, P. Inteligência 
Artificial. Campus. Capítulo 3. 
 Exercícios recomendados: 
 3.1 a 3.15