04-Estados_e_buscas

Prévia do material em texto

ESTADOS E BUSCAS 
¡  Muitas vezes não recebemos um algoritmo para resolver um 
problema, mas apenas uma especificação do que é uma 
solução ─ então temos de procurar por uma solução. 
¡  Um problema típico ocorre quando o agente está em um 
estado inicial, tendo um conjunto de ações determinísticas 
que ele pode realizar e quer chegar a um estado objetivo. 
¡  Muitos problemas de IA podem ser abstraídos para o 
problema de encontrar um caminho em um grafo dirigido. 
¡  Muitas vezes há mais de uma maneira de representar um 
problema como grafo. 
RESOLUÇÃO DE PROBLEMAS POR BUSCA 
¡  Formulação 
§  do OBJETIVO 
§  do PROBLEMA 
§  Decidir quais ações e estados considerar. 
¡  Busca 
§  Dada várias sequências de ações, qual é a melhor? 
¡  Execução 
Formulação à Busca àExecução 
TAREFAS PARA A RESOLUÇÃO DE 
PROBLEMAS POR BUSCA 
def	
  agente_resolvedor_problemas_simples(percepção):	
  
	
  
entrada:	
  percepção	
  #	
  uma	
  percepção	
  
	
  
local:	
  sequencia	
  #	
  uma	
  sequência	
  de	
  ações,	
  inicialmente	
  vazia	
  
	
  	
  	
  	
  	
  	
  	
  estado	
  #	
  uma	
  descrição	
  do	
  estado	
  atual	
  do	
  mundo	
  
	
  	
  	
  	
  	
  	
  	
  objetivo	
  #	
  um	
  objetivo,	
  inicialmente	
  nulo	
  
	
  	
  	
  	
  	
  	
  	
  problema	
  #	
  uma	
  formulação	
  de	
  problema	
  	
  
	
  
	
  
estado	
  ß	
  ATUALIZAR_ESTADO(estado,	
  percepção)	
  
	
  
se	
  sequencia	
  está	
  vazia:	
  
	
  objetivo	
  	
  ß	
  FORMULAR_OBJETIVO(estado)	
  
	
  problema	
  	
  ß	
  FORMULAR_PROBLEMA(estado,	
  objetivo)	
  
	
  sequencia	
  ß	
  BUSCA(problema)	
  
	
  
ação	
  ß	
  PRIMEIRO(sequencia)	
  
sequencia	
  ß	
  RESTO(sequencia)	
  
	
  
retornar	
  ação	
  	
  
ESTRUTURA BÁSICA DE UM AGENTE 
RESOLVEDOR DE PROBLEMAS POR BUSCA 
¡  Um estado contém toda a informação necessária para 
predizer os efeitos de uma ação e determinar se ele é um 
estado objetivo. 
¡  O nível de abstração, ou detalhe, que modelamos o mundo 
interfere na resolução do problema. 
§  Um nível muito fino e perderemos a visão do problemas global. 
§  Um nível muito grosso e perderemos detalhes críticos para resolver o 
problema. 
¡  O número de estados depende da representação e do nível de 
abstração escolhidos. 
ESPAÇO DE ESTADOS 
¡  O estado inicial e uma função de ação definem 
implicitamente o espaço de estados, o qual é o conjunto de 
todos os estados acessíveis a partir do estado inicial. 
¡  O espaço de estados forma um grafo (nem sempre explícito) 
em que os nós são estados e os arcos são as ações 
¡  Um caminho no espaço de estados é uma sequência de 
estados conectados por uma sequência de ações. 
ESPAÇO DE ESTADOS 
¡  Consistem de: 
§  Um conjunto de estados; 
§  Um conjunto distinto de estado chamado de estados iniciais; 
§  Um conjunto de ações disponíveis para o agente em cada estado; 
§  Uma função de ação que dado um estado e uma ação retorna um 
novo estado; 
§  Um conjunto de estados objetivos, sempre especificado por uma 
função boolena, objetivo(s), que é verdadeira quando s é um estado 
objetivo; 
§  Um critério que especifica a qualidade de uma solução aceitável. 
PROBLEMAS NO ESPAÇO DE ESTADOS 
¡  Problemas com um único estado: 
§  São problemas em que é possível calcular exatamente que estados 
estaremos após uma sequência de ações. 
¡  Problemas com múltiplos estados: 
§  São problemas em que sabemos os efeitos das ações, mas temos acesso 
limitado ao estado no qual se encontra o ambiente. 
¡  Problemas de contingência: 
§  Sã problemas em que as ações realizadas pelo agente podem resultar 
em efeitos não esperados (não determinístico). Não há como fazer uma 
árvore de busca que garanta o resultado. 
¡  Problemas de exploração: 
§  São problemas em que o agente não tem informações sobre o efeitos de 
suas ações. Ele sabe somente sobre o que foi aprendido anteriormente 
pela exploração do problema. 
TIPO DE PROBLEMAS 
¡  Problemas de estado único: 
§  O agente sabe em que estado está. 
§  O agente sabe o que cada uma das suas ações fazem. 
§  O agente poderá calcular exatamente o que fazer. 
¡  Problemas de múltiplos estados: 
§  O agente sabe o que cada uma das suas ações fazem. 
¡  Problemas de contingência: 
§  O agente deve usar os sensores enquanto age. 
§  A solução é uma árvore de ações ou uma política. 
§  Às vezes pode ser viável o entrelaçamento (agir antes de buscar). 
¡  Problemas de exploração: 
§  O espaço de estados é desconhecido. 
CARACTERÍSTICAS DOS TIPO DE 
PROBLEMAS 
Estado inicial possível Estado final 
EXEMPLO: MUNDO DO ASPIRADOR 
•  Estado é representado por um par: 
<local do robô; sujidade do local> 
•  Número de estados = 2.22 à k. 2k onde k é o número de 
locais. 
¡  Estado único: 
§  Início no estado 5. 
¡  Múltiplos estados: 
§  Início em 
§  {1, 2, 3, 4, 5, 6, 7, 8) 
§  Ação à Direita 
§  {2, 4, 6, 8} 
¡  Contingência: 
§  Ação à Aspirar 
§  Pode sujar um carpete limpo. 
§  Sensoriamento 
§  Local 
§  Sujo ou não 
EXEMPLO DE TIPOS DE PROBLEMAS: 
MUNDO DO ASPIRADOR 
ESPAÇO DE ESTADOS EM PROBLEMAS DE 
ESTADO ÚNICO 
ESPAÇO DE ESTADO EM PROBLEMAS DE 
MÚLTIPLOS ESTADOS 
¡  Estados: matriz 3x3 com a especificação da posição de cada símbolo de 
1-8 e o espaço em branco. 
¡  Estado Inicial : qualquer um dos estados acima especificados. 
¡  Função de ação: gera os estados válidos resultantes das quatro ações de 
mover o espaço vazio para direita , esquerda , cima , baixo . 
¡  Teste de objetivo: verifica se o estado corresponde ao estado objetivo. 
EXEMPLO: 8- PUZZLE 
Número de estados = 9! = 362.880 
8- PUZZLE – ESPAÇO DE ESTADOS 
¡  Estados: qualquer arranjo de 
0 a 8 rainhas no tabuleiro. 
¡  Estado inicial: nenhuma 
rainha no tabuleiro. 
¡  Função de ação: colocar uma 
rainha em uma casa. 
¡  Teste de Objetivo: 8 rainhas 
estão no tabuleiro e 
nenhuma está sendo 
atacada. 
¡  3x1014 possíveis sequências 
a serem investigadas. 
EXEMPLO: 8 RAINHAS 
¡  Estados: 0 a 8 rainhas no 
tabuleiro, uma por coluna nas 
n colunas mais a esquerda e 
sem ataques. 
¡  Estado inicial: nenhuma 
rainha no tabuleiro. 
¡  Função de ação: colocar uma 
rainha em uma casa cuja 
coluna seja a primeira à 
esquerda que não esteja 
ameaçada por outra rainha. 
¡  2057 possíveis sequências a 
serem investigadas. 
A formulação do problema é 
FUNDAMENTAL!!! 
EXEMPLO: 8 RAINHAS – OUTRA 
FORMULAÇÃO 
¡ A busca no espaço de estados assume que: 
§  O agente tem um conhecimento perfeito do espaço de estados 
e pode observar em que estado ele está. 
§  O agente tem um conjunto de ações que tem efeitos 
determinísticos conhecidos. 
§  Alguns estados são estados objetivo e o agente quer atingir um 
destes estados, podendo reconhecer um estado objetivo. 
§  Uma solução é uma sequencia de ações que levam o agente do 
seu estado atual para um estado objetivo. 
BUSCA NO ESPAÇO DE ESTADOS 
¡  Existem muitas formas de representar um problema como um 
grafo, mas duas formas merecem atenção: 
¡  Grafo do Espaço de Estados: no qual um nó representa um 
estado do mundo e um arco representa uma mudança de um 
estado para outro no mundo. 
§  Ex.: problema das 8 rainhas – mudar uma rainha de linha gera um 
novo estado. 
¡  Grafo do Espaço de Problemas: no qual um nó representa um 
problema a ser resolvido e um arco representa decomposições 
alternativas do problemas. 
§  Ex.: problema das 8 rainhas – colocar uma rainha na n-ésima coluna, 
sem gerar conflito com asoutras que já estão no tabuleiro, gera um 
novo estado. 
BUSCANDO EM GRAFOS 
¡  Um grafo consiste em um conjunto N de nós e um conjunto 
A de pares ordenados de nós <nx, ny> , chamados arcos. 
¡  O nó n2 é um vizinho de n1 se houver um arco de n1 para 
n2. Ou seja, se ‹n1, n2› ∈ A. 
¡  Um caminho é uma sequência de nós ‹n0, n1, ..., nK› que tal 
que ‹ni-1, ni› ∈    A. 
¡  Tendo em conta um conjunto de nós de início e de nós 
objetivo, uma solução é um caminho de um nó de início para 
um nó objetivo. 
¡  Muitas vezes há um custo associado com os arcos e o custo 
de um caminho é a soma dos custos dos arcos no caminho. 
GRAFOS DIRIGIDOS 
•  O robô quer ir de fora do quarto 103 para dentro do quarto 
123. 
EXEMPLO: O ROBÔ DE ENTREGA 
EXEMPLO: GRAFO PARA O ROBÔ DE 
ENTREGA 
¡  Um estado é uma representação de uma configuração física. 
¡  Um nó é uma estrutura de dados. 
¡  Estados não têm pais, filhos, profundidade ou custo. 
ESTADOS X NÓS 
¡  Algoritmo genérico de busca: 
§  Dado um grafo, nós iniciais e nós objetivos, explorar 
incrementalmente caminhos a partir dos nós de início até um nó 
objetivo. 
§  Manter uma fronteira de caminhos, a partir do nó de início, que já 
tenham sido explorados. 
§  Com o andamento da busca, a fronteira se expande para os nós 
inexplorados até que seja encontrado um nó objetivo. 
¡  A maneira na qual a fronteira é expandida define a 
estratégia de busca. 
BUSCANDO EM GRAFOS 
RESOLVENDO PROBLEMAS PELA BUSCA 
EM GRAFOS 
¡  A função de exploração (ou função de ação) cria novos nós 
usando os operadores do problema para criar os estados 
correspondentes. 
¡  A definição de busca é simétrica: é possível encontrar o 
caminho dos nós iniciais para a um nó objetivo ou de um nó 
objetivo para algum nó inicial. 
¡  Direção da expansão: 
§  Do estado inicial para um estado final (busca dirigida por dados ou 
encadeamento para frente). 
§  De um estado final para o estado inicial (busca baseada em objetivo 
ou encadeamento para trás). 
§  Busca bidirecional (é realizada nas duas direções ao mesmo tempo). 
DIREÇÃO DA BUSCA 
ENCADEAMENTO PARA FRENTE 
ENCADEAMENTO PARA TRÁS 
•  Você pode buscar para trás a partir do objetivo e 
simultaneamente para frente a partir do início. 
•  Quando os dois lados da busca gerarem um estado igual uma 
solução foi encontrada. 
•  É possível uti l izar estratégias diferentes para cada direção da 
busca 
BUSCA BIDIRECIONAL 
def	
  busca(G,	
  S,	
  goal):	
  
entrada:	
  G	
  #	
  a	
  grafo	
  
	
   	
  	
  	
  	
  S	
  #	
  um	
  conjunto	
  de	
  nós	
  iniciais	
  
	
   	
  	
  	
  	
  objetivo	
  #	
  função	
  booleana	
  que	
  testa	
  se	
  S	
  é	
  um	
  nó	
  objetivo	
  
	
  
saída:	
  um	
  caminho	
  de	
  um	
  membro	
  de	
  S	
  para	
  um	
  nó	
  para	
  o	
  qual	
  a	
  função	
  	
  	
  
objetivo	
  é	
  verdadeira,	
  ou	
  ⟘	
  se	
  não	
  existir	
  solução	
  
	
  
local:	
  fronteira	
  #	
  um	
  conjunto	
  de	
  caminhos	
  
	
  
	
  
fronteira	
  ß	
  {<s>|s	
  ∈	
  S}	
  
	
  
while	
  fronteira	
  ≠{  }:	
  
seleciona	
  e	
  remove	
  <s0,…,sk>	
  da	
  fronteira	
  	
  
	
  
if	
  objetivo(sk):	
  return	
  <s0,…,sk>	
  
	
  
fronteira	
  ß	
  fronteira	
  ∪  {⟨s0,… ,sk,s⟩|⟨𝑠𝑘 ,  𝑠⟩  ∈S}	
  	
  
	
  
return	
  ⟘	
  
ALGORITMO GERAL DE BUSCA EM GRAFO 
¡  Completude (completeza): 
§  A estratégia é completa se, sempre que existir uma solução, ela a 
encontra em uma quantidade de tempo finito. 
¡  Qualidade/otimicidade: 
§  A estratégia é ótima se, quando ela acha uma solução, esta é a 
melhor solução. 
¡  Custo do tempo: 
§  Quanto tempo a estratégia gasta para encontrar a solução no pior 
caso. Normalmente medida em termos do número máximo de nós 
expandidos. 
¡  Custo de memória: 
§  Quanta memória a estratégia usa para encontrar a solução, no pior 
caso. Normalmente medida pelo tamanho máximo que a lista de nós 
abertos (fronteira) assume durante a busca. 
CRITÉRIOS DE AVALIAÇÃO DAS 
ESTRATÉGIAS DE BUSCA 
¡  O fator de ramificação de um nó é o seu número de vizinhos. 
§  Fator de ramificação para frente: número de arcos saindo de um 
nó. 
§  Fator de ramificação para trás: número de arcos entrando um nó. 
¡  As complexidades de tempo e espaço são medidas em termos 
dos seguintes fatores: 
§  b : Fator de ramificação máximo da árvore de busca. 
§  d : Profundidade da solução de menor custo. 
§  m : Profundidade máxima do espaço de estados (pode ser ∞). 
CRITÉRIOS DE AVALIAÇÃO DAS 
ESTRATÉGIAS DE BUSCA 
¡ Busca desinformada: 
§  Busca em profundidade. 
§  Busca em largura. 
§  Busca pelo custo mínimo (Busca Gulosa). 
§  Busca por aprofundamento iterativo. 
 
BUSCA SISTEMÁTICA 
¡  Trata a fronteira como uma pilha. 
§  i.e. sempre seleciona um dos últimos elementos adicionados à 
fronteira. 
¡  Se a lista de caminhos na fronteira é [p1, p2, ... ] 
§  p1 é selecionado e os caminhos que estendem p1 são adicionados 
à frente da pilha (em frente a p2). 
§  p2 é selecionado somente quando todos os caminhos de p1 foram 
explorados. 
BUSCA EM PROFUNDIDADE 
¡  Considere o seguinte problema: 
§  Estado inicial: A 
§  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
§  Estado objetivo: M 
§  Custo do caminho: zero 
¡  Representação de cada nó da fronteira: 
§  no(último estado, [caminho], custo) 
¡  Fronteira inicial: [no(A, [A], 0)] 
BUSCA EM PROFUNDIDADE - EXEMPLO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado A não é o objetivo. 
•  Fronteira após expandir o estado A: 
•  [no(B, [A, B], 0), no(C, [A, C], 0)] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado B não é o objetivo. 
•  Fronteira após expandir o estado B: 
•  [no(D, [A, B, D], 0), no(E, [A, B, E], 0), no(C, [A, C], 0)] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado D não é o objetivo. 
•  Fronteira após expandir o estado D: 
•  [no(H, [A, B, D, H], 0), no(I, [A, B, D, I], 0), no(E, [A, B, E], 0), no(C, [A, 
C], 0)] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado H não é o objetivo. 
•  Fronteira após expandir o estado H (sem filhos): 
•  [no(I, [A, B, D, I], 0), no(E, [A, B, E], 0), no(C, [A, C], 0)] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado I não é o objetivo. 
•  Fronteira após expandir o estado I (sem filhos): 
•  [no(E, [A, B, E], 0), no(C, [A, C], 0)] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado E não é o objetivo. 
•  Fronteira após expandir o estado E: 
•  [no(J, [A, B, E, J], 0), no(K, [A, B, E, K], 0), no(C, [A, C], 0)] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado J não é o objetivo. 
•  Fronteira após expandir o estado J (sem filhos): 
•  [no(K, [A, B, E, K], 0), no(C, [A, C], 0)] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado K não é o objetivo. 
•  Fronteira após expandir o estado K (sem filhos): 
•  [no(C, [A, C], 0)] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado C não é o objetivo. 
•  Fronteira após expandir o estado C: 
•  [no(F, [A, C, F], 0), no(G, [A, C, G], 0)] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado F não é o objetivo. 
•  Fronteira após expandir o estado F: 
•  [no(L, [A, C, F, L], 0), no(M, [A, C, F, M], 0), no(G, [A, C, G], 0)] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado L não é o objetivo. 
•  Fronteira após expandir o estado L: 
•  [no(M, [A, C, F, M], 0), no(G, [A, C, G], 0)] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
¡  Função de ação: 
§  O estado A gera os estados B e C 
§  O estado B gera os estados D e E 
§  O estado C gera os estados F e G 
§  O estado D gera os estados H e I 
§  O estado E gera os estados J e K 
§  O estado F gera os estados L e M 
§  O estado G gera os estados N e O 
§  Os estados H, I, J, K, L, M, N e O não geram sucessores 
•  O estado M é o objetivo. 
•  A busca para tendo como solução o caminho: [A, C, F, M] 
EXEMPLO – ONDE M É O NÓ OBJETIVO 
•  O algoritmo de busca gera como resultado implícito uma 
árvore de busca: 
ÁRVORE DE BUSCA DA BUSCA EM 
PROFUNDIDADE 
def	
  busca_em_profundidade(G,	
  S,	
  goal):	
  
entrada:	
  G	
  #	
  a	
  grafo	
  
	
   	
  	
  	
  	
  S	
  #	
  um	
  conjunto	
  de	
  nós	
  iniciais	
  
	
   	
  	
  	
  	
  objetivo	
  #	
  função	
  booleana	
  que	
  testa	
  se	
  S	
  é	
  um	
  nó	
  objetivo	
  
	
  
saída:	
  um	
  caminho	
  de	
  um	
  membro	
  de	
  S	
  para	
  um	
  nó	
  para	
  o	
  qual	
  a	
  função	
  	
  	
  
objetivo	
  é	
  verdadeira,	
  ou	
  ⟘	
  se	
  não	
  existir	
  solução	
  
	
  
local:	
  fronteira	
  #	
  um	
  conjunto	
  de	
  caminhos	
  
	
  
	
  
fronteira	
  ß	
  {<s>|s	
  ∈	
  S}	
  
	
  
while	
  fronteira	
  ≠{  }:	
  
selecione	
  e	
  remova	
  o	
  1o	
  nó	
  <s0,…,sk>	
  da	
  fronteira	
  	
  
	
  
if	
  objetivo(sk):	
  return	
  <s0,…,sk>	
  
	
  
adicione({<s0,…,sk,s>}|<sk,s>	
  ∈	
  S},	
  fronteira,	
  início)	
  
	
  
return	
  ⟘	
  
 
ALGORITMO PARA BUSCA EM 
PROFUNDIDADE 
¡  A busca em profundidade não tem garantia de terminar em 
grafos infinitos ou em grafos com ciclos. 
¡  A complexidade do espaço é linear no tamanho do caminho 
a ser explorado O(mb), onde b é o fator de ramificação e m 
é o tamanho do caminho. 
¡  A complexidade do tempo é exponencial no tamanho do 
caminho a ser explorado O(bm), onde b é o fator de 
ramificação e m é o tamanho do caminho. 
¡  A busca não é restringida pelo objetivo até que aconteça 
dela tropeçar no objetivo. 
COMPLEXIDADE DA BUSCA EM 
PROFUNDIDADE 
¡ Apropriada: 
§  O espaço de estados é restrito (representação complexa de 
estados, e.g. robótica) 
§  Existe muitas soluções, talvez com caminhos longos, 
particularmente para o caso em que todos os caminhos levam 
a uma solução. 
¡ Inapropriada: 
§  Quando se tem ciclos no espaço de estados. 
§  Quando existem soluções rasas. 
§  Se a otimalidade é importante. 
QUANDO A BUSCA EM PROFUNDIDADE É 
APROPRIADA 
¡  Trata a fronteira como uma fila. 
¡  Sempre seleciona um dos primeiros elementos adicionados 
à fronteira. 
¡  Se a lista de caminhos na fronteira [p1, p2, ... , pr]: 
§  p1 é selecionada e seus vizinhos são adicionados ao final da fila, 
após pr. 
§  p2 é selecionado em seguida. 
BUSCA EM LARGURA 
GRÁFICO ILUSTRATIVO ─ BUSCA EM 
LARGURA 
def	
  busca_em_largura(G,	
  S,	
  goal):	
  
entrada:	
  G	
  #	
  a	
  grafo	
  
	
   	
  	
  	
  	
  S	
  #	
  um	
  conjunto	
  de	
  nós	
  iniciais	
  
	
   	
  	
  	
  	
  objetivo	
  #	
  função	
  booleana	
  que	
  testa	
  se	
  S	
  é	
  um	
  nó	
  objetivo	
  
	
  
saída:	
  um	
  caminho	
  de	
  um	
  membro	
  de	
  S	
  para	
  um	
  nó	
  para	
  o	
  qual	
  a	
  função	
  	
  	
  
objetivo	
  é	
  verdadeira,	
  ou	
  	
  se	
  não	
  existir	
  solução	
  
	
  
local:	
  fronteira	
  #	
  um	
  conjunto	
  de	
  caminhos	
  
	
  
	
  
fronteira	
  ß	
  {<s>|s	
  ∈	
  S}	
  
	
  
while	
  fronteira	
  :	
  
selecione	
  e	
  remova	
  o	
  1o	
  nó	
  <s0,…,sk>	
  da	
  fronteiraif	
  objetivo(sk):	
  return	
  <s0,…,sk>	
  
	
  
adicione({<s0,…,sk,s>}|<sk,s>	
  ∈	
  S},	
  fronteira,	
  fim)	
  
	
  
return	
  ⟘	
  
 
 
ALGORITMO PARA BUSCA EM LARGURA 
¡  Se o fator de ramificação para todos os nós é finito, a busca 
em largura é completa. Também é garantido que ela 
encontrará o caminho com o menor número de arcos. 
¡  A complexidade do espaço é exponencial no comprimento 
do caminho O(bn), onde b é fator de ramificação, n é o 
comprimento do caminho. 
¡  A complexidade de tempo é exponencial no comprimento do 
caminho: O(bn), onde b é fator de ramificação, n é o 
comprimento do caminho. 
¡  A busca não é restringida pelo objetivo. 
COMPLEXIDADE DA BUSCA EM LARGURA 
¡ Apropriada: 
§  Quando espaço de memória não é problema. 
§  Quando é necessário achar a solução com menos arcos. 
§  Apesar de nem todas as soluções serem rasas, algumas são. 
¡ Inapropriada: 
§  Quando o espaço de memória é limitado. 
§  Quando todas as soluções estão fundas na árvore de busca. 
§  Quando o fator de ramificação é muito grande. 
QUANDO A BUSCA EM LARGURA É 
APROPRIADA 
BUSCA DESINFORMADA COM CUSTOS 
¡  Às vezes há custos associados com os arcos. O custo de um 
caminho é a soma dos custos de seus arcos. 𝑐𝑜𝑠𝑡(⟨𝑛0,  …,  𝑛𝑘⟩)=∑𝑖=1↑𝑘▒|𝑛𝑖−1,𝑛𝑖|  
¡  Em cada fase, a busca pelo menor-custo-primeiro seleciona um 
caminho na fronteira com o menor custo. 
¡  A fronteira é uma f ila de prioridade ordenada pelo custo do 
caminho. 
¡  Encontra um caminho de menor custo para um nó de objetivo. 
¡  Quando os custos do arco são iguais temos uma busca em 
largura. 
BUSCA PELO MENOR-CUSTO-PRIMEIRO 
¡  Considere o seguinte problema: 
§  Estado inicial: S 
§  Função de ação: 
§  O estado S gera os estados A(custo=1), B(custo=5) e C(custo=15) 
§  O estado A gera o estado G(custo=10) 
§  O estado B gera o estado G(custo=5) 
§  O estado C gera o estado G(custo=5) 
§  O estado G não gera sucessores 
§  Estado objetivo: G 
¡  Representação de cada nó da fronteira: 
§  no(último estado, [caminho], custo) 
¡  Fronteira inicial: [no(S, [S], 0)] 
59 
BUSCA PELO MENOR CUSTO PRIMEIRO - 
EXEMPLO 
¡  Considere o seguinte problema: 
§  Estado inicial: S 
§  Função de ação: 
§  O estado S gera os estados A(custo=1), B(custo=5) e C(custo=15) 
§  O estado A gera o estado G(custo=10) 
§  O estado B gera o estado G(custo=5) 
§  O estado C gera o estado G(custo=5) 
§  O estado G não gera sucessores 
¡  O estado S não é o objetivo. 
¡  Fronteira após expandir o estado S: 
§  [no(A, [S, A], 1), no(B, [S, B], 5), no(C, [S, C], 15)] 
60 
EXEMPLO – ONDE G É O OBJETIVO 
¡  Considere o seguinte problema: 
§  Estado inicial: S 
§  Função de ação: 
§  O estado S gera os estados A(custo=1), B(custo=5) e C(custo=15) 
§  O estado A gera o estado G(custo=10) 
§  O estado B gera o estado G(custo=5) 
§  O estado C gera o estado G(custo=5) 
§  O estado G não gera sucessores 
¡  O estado A não é o objetivo. 
¡  Fronteira após expandir o estado A: 
§  [no(B, [S, B], 5), no(A, [S, A , G], 11), [no(C, [S, C], 15)] 
61 
EXEMPLO – ONDE G É O OBJETIVO 
¡  Considere o seguinte problema: 
§  Estado inicial: S 
§  Função sucessor: 
§  O estado S gera os estados A(custo=1), B(custo=5) e C(custo=15) 
§  O estado A gera o estado G(custo=10) 
§  O estado B gera o estado G(custo=5) 
§  O estado C gera o estado G(custo=5) 
§  O estado G não gera sucessores 
¡  O estado B não é o objetivo. 
¡  Fronteira após expandir o estado B: 
§  [no(G, [S, B, G], 10), no(A, [S, A , G], 11), [no(C, [S, C], 15)] 
¡  O estado G é o objetivo. 
¡  A busca para tendo como resultado o caminho: [S, B, G] com custo = 
10 
62 
BUSCA PELO MENOR-CUSTO-PRIMEIRO - 
EXEMPLO 
63 
BUSCA PELO MENOR-CUSTO-PRIMEIRO 
def	
  busca_pelo_menor_custo(G,	
  S,	
  goal):	
  
entrada:	
  G	
  #	
  a	
  grafo	
  
	
   	
  	
  	
  	
  S	
  #	
  um	
  conjunto	
  de	
  nós	
  iniciais	
  
	
   	
  	
  	
  	
  objetivo	
  #	
  função	
  booleana	
  que	
  testa	
  se	
  S	
  é	
  um	
  nó	
  objetivo	
  
	
  
saída:	
  um	
  caminho	
  de	
  um	
  membro	
  de	
  S	
  para	
  um	
  nó	
  para	
  o	
  qual	
  a	
  função	
  	
  	
  
objetivo	
  é	
  verdadeira,	
  ou	
  	
  se	
  não	
  existir	
  solução	
  
	
  
local:	
  fronteira	
  #	
  um	
  conjunto	
  de	
  caminhos	
  
	
  
	
  
fronteira	
  ß	
  {<s>|s	
  ∈	
  S}	
  
	
  
while	
  fronteira	
  :	
  
selecione	
  e	
  remova	
  o	
  1o	
  nó	
  <s0,…,sk>	
  da	
  fronteira	
  
	
  
if	
  objetivo(sk):	
  return	
  <s0,…,sk>	
  
	
  
adicione({<s0,…,sk,s>}|<sk,s>	
  ∈	
  S},	
  fronteira,	
  ordem	
  crescente	
  de	
  custo)	
  
	
  
return	
  ⟘ 
ALGORITMO PARA BUSCA PELO MENOR-
CUSTO-PRIMEIRO 
¡  Completude: 
§  Não, pois um ciclo com custo zero ou negativo poderia ser seguido 
para sempre. 
§  Sim, dado que os custos dos arcos sejam sempre positivos. 
¡  Otimalidade: 
§  Não, pois podem existir arcos com custo negativos. 
§  Sim, sempre que os arcos tiverem custos não negativos. 
¡  A complexidade de tempo é exponencial O(bm). 
¡  A complexidade de espaço é exponencial O(bm), pois se tem 
que armazenar toda a fronteira na memória. 
ANALISE DA BUSCA PELO MENOR-CUSTO-
PRIMEIRO 
¡  Até agora todas as estratégias de pesquisa que são 
garantidas de parar usam espaço exponencial. 
¡  Ideia: 
§  Vamos recalcular os elementos de fronteira em vez de salvá-los. 
§  Assim, vamos procurar caminhos da profundidade 0 e, em seguida, 
1, 2, 3, etc. 
§  Se um caminho não pode ser encontrado na profundidade B, 
procure por um caminho na profundidade B + 1. Aumente o limite 
de profundidade quando a busca falhar de forma não natural (i.e. o 
limite de profundidade for atingido). 
¡  É necessário um buscador em profundidade que verifique 
um limite máximo para a profundidade da busca. 
BUSCA POR APROFUNDAMENTO 
ITERATIVO 
67 
EXEMPLO: BUSCA POR 
APROFUNDAMENTO ITERATIV0 
68 
EXEMPLO: BUSCA POR 
APROFUNDAMENTO ITERATIV0 
69 
EXEMPLO: BUSCA POR 
APROFUNDAMENTO ITERATIV0 
70 
EXEMPLO: BUSCA POR 
APROFUNDAMENTO ITERATIV0 
¡  Apesar de parecer bem pouco eficiente… 
 
§  Os nós que são “recomputados” várias vezes são os nós dos níveis 
mais altos a árvore de busca , os quais normalmente são em menor 
quantidade. 
 
§  O custo de memória é linear como na busca em profundidade. 
 
¡  É completa quando o fator de ramificação for finito. 
 
¡  É ótima quando o custo do caminho é uma função não-
decrescente da profundidade do nó. 
71 
BUSCA POR APROFUNDAMENTO 
ITERATIV0 
def	
  busca_aprofudamento_iterativo(S,	
  G,	
  objetivo):	
  
entrada:	
  G	
  #	
  a	
  grafo	
  
	
   	
  	
  S	
  #	
  um	
  conjunto	
  de	
  nós	
  iniciais	
  
	
   	
  	
  objetivo	
  #	
  função	
  booleana	
  que	
  testa	
  se	
  S	
  é	
  um	
  nó	
  objetivo	
  
saída:	
  um	
  caminho	
  de	
  um	
  membro	
  de	
  S	
  para	
  um	
  nó	
  para	
  o	
  qual	
  a	
  função	
   	
  	
   	
  	
  objetivo	
  é	
  
verdadeira,	
  ou	
  ⟘	
  se	
  não	
  existir	
  solução	
  
local:	
  limite	
  #	
  profundidade	
  máxima	
  	
  
	
  
def	
  busca_profundidade_limitada(<s0,…,sk>,	
  G,	
  limite):	
  
	
  	
  	
  	
  local:	
  atingiu_limite	
  #	
  máxima	
  profundidade	
  
	
  
	
  	
  	
  	
  atingiu_limite	
  ß	
  False	
  
if	
  objetivo(sk):	
  return	
  <s0,…,sk>	
  	
  
elif	
  profundidade(sk)	
  =	
  limite:	
  returninterrupção	
  
else:	
  for	
  each	
  {<s0,…,sk,s>}|<sk,s>	
  ∈	
  S}:	
  
	
  	
  	
  	
  	
  	
  resultado	
  ß	
  busca_profundidade_limitada(<s0,…,sk,s>,	
  G,	
  limite)	
  
	
  	
  	
  	
  	
  	
  if	
  resultado	
  =	
  interrupção:	
  atingiu_limite	
  ß	
  True	
  
	
  	
  	
  	
  	
  	
  elif	
  resultado	
  ≠	
  ⊥:	
  return	
  resultado	
  
if	
  atingiu_limite:	
  return	
  interrupção	
  
else:	
  return	
  resultado	
  
	
  
for	
  limite	
  =	
  0	
  until	
  ∞:	
  
resultado	
  ß	
  busca_profundidade_limitada({<s>  ∈	
  S},	
  G,	
  limite)	
  
if	
  resultado	
  ≠	
  ⊥	
  :	
  return	
  resultado	
  
BUSCA POR APROFUNDAMENTO 
ITERATIVO 
•  Complexidade com uma solução na profundidade k e fator 
de ramificação b: 
COMPLEXIDADE DA BUSCA POR 
APROFUNDAMENTO ITERATIVO 
Tipo de Busca Seleção da fronteira Completa Ótima Custo de 
Tempo 
Custo de 
Espaço 
Profundidade Último nó adicionado N 
S à sem ciclos e 
espaço de busca finito 
N O(bm) O(mb) 
Largura Primeiro nó adicionado S S O(bm) O(bm) 
Menor-custo-primeiro Mínimo custo à g(n) S à custos > 0 S à custos > 0 O(bm) O(bm) 
Aprofundamento 
interativo 
Último nó adicionado 
 
N 
S à sem ciclos e 
espaço de busca finito 
N O(bm) O(mb) 
SUMÁRIO: BUSCA SISTEMÁTICA 
DESINFORMADA 
¡  Porque todas as estratégias anteriores são chamadas de 
desinformadas? 
§  Porque elas não consideram qualquer informação sobre os estados 
para decidir qual caminho expandir em primeiro lugar na fronteira. 
¡  Em outras palavras, elas são gerais e não levam em conta a 
natureza específica do problema. 
BUSCA INFORMADA (HEURÍSTICA) 
¡  Idéia: não ignore o objetivo ao selecionar os caminhos. 
¡  Muitas vezes há conhecimento extra que pode ser usado 
para orientar a busca: uma estimativa da distância do nó n 
para um nó objetivo, 
¡  Uma heurística, h(n), é uma estimativa do custo do 
caminho mais curto do nó n para um nó objetivo. 
§  h(n) usa apenas informações que podem ser facilmente obtidas 
(que são fáceis de calcular) sobre um nó. 
§  h pode ser estendido para caminhos: h(<n0, ... , nk>) = h(nk). 
§  h(n) é uma subavaliação se não houver nenhum caminho de n para 
um nó objetivo que tenha comprimento inferior a h(n). 
BUSCA INFORMADA (HEURÍSTICA) 
¡  Definição de função heurística admissível: 
§  Uma função heurística h(n) é admissível se ela nunca é uma 
sobrestimação do custo do nó n para um nó objetivo. 
¡  As heurísticas admissíveis tem natureza otimista, pois elas 
sempre indicam que o custo da solução é melhor do que ele 
realmente é. 
§  Desta maneira se uma solução ainda não foi encontrada sempre 
existirá um nó com custo menor do que ela. 
•  Nunca existe um caminho do nó n para um nó objetivo que 
tenha caminho de comprimento inferior a h(n) . Outra maneira 
de dizer isto: 
•  h(n) é um limite inferior sobre o custo de ir do nó n para o nó 
objetivo mais próximo. 
FUNÇÕES HEURÍSTICAS 
 
 
•  Se os nós são pontos num plano Euclidiano e o custo é a 
distância, então podemos usar a distância linear entre o 
nó n e o nó objetivo mais próximo como o valor da h(n). 
EXEMPLO DE FUNÇÕES HEURÍSTICAS 
ADMISSÍVEIS 
 
 
•  Exemplo de heurísticas para o quebra-cabeças de 8 peças 
•  h1(n) = número de quadrados em locais errados 
•  h2(n) = distância Manhattan total 
•  número de espaços na vertical e horizontal que devem ser movidos 
para chegar no local correto. 
•  h1(s) = 7 (só o número 7 está no local correto) ‏ 
•  h2(s) = 2+3+3+2+4+2+0+2 = 18 
EXEMPLO DE FUNÇÕES HEURÍSTICAS 
ADMISSÍVEIS 
 
¡  Você deve identif icar uma versão relaxada do problema: 
§  Na qual uma ou mais restrições sobre as ações foram descartadas. 
 
¡  Exemplo: 
§  Robô: o agente pode mover através das paredes 
§  Motorista: o agente pode mover-se em linha reta ao local 
§  8-puzzle: 
§  1) os elementos podem mover em qualquer lugar 
§  2) os elementos podem mover para qualquer casa adjacente 
¡  Resultado: 
§  O custo de uma solução ideal para o problema relaxado é uma 
heurística admissível para o problema original (porque sempre é 
fracamente menos custoso resolver um problema menos restrito!) 
COMO CONSTRUIR UMA HEURÍSTICA 
¡  Você deve identificar restrições que, quando removidas, 
fazem o problema extremamente fácil de ser resolvido 
§  Isso é importante porque as heurísticas não são úteis se eles são 
tão difíceis de resolver quanto o problema original! 
¡  Este é o caso em nossos exemplos: 
§  Robô: permitindo que o agente se mova através das paredes. A 
solução ideal para este problema relaxado é distância Manhattan. 
§  Motorista: permitindo que o agente se mova em linha reta ao 
local. A solução ideal para este problema relaxado é 
distância em linha reta. 
§  8-puzzle: (1) os elementos podem mover-se para qualquer lugar. A 
solução ideal para esse problema relaxado é o número de peças 
no local errado; (2) os elementos podem mover-se para qualquer 
local adjacente ... 
COMO CONSTRUIR UMA HEURÍSTICA 
¡  Se h2(n) ≥ h1(n) para todos os n (ambas admissíveis) então h2 
domina h1. 
§  Qual é a melhor para a busca (porque?) 
¡  8-puzzle: 
§  (1) os elementos podem mover-se para qualquer lugar. 
§  (2) os elementos podem mover-se para qualquer casa adjacente. 
§  
¡  No problema original os elementos podem mover-se para um 
quadrado adjacentes se ele estiver vazio). 
¡  Custos da busca para o 8-puzzle (número médio de caminhos 
expandidos): 
d = 12 IDS = 3,644,035 caminhos onde d é a profundidade da solução 
 A*(h1) = 227 caminhos 
 A*(h2) = 73 caminhos 
 
d = 24 IDS = caminhos demais 
 A*(h1) = 39,135 caminhos 
 A*(h2) = 1,641 caminhos 
HEURÍSTICA: DOMINÂNCIA 
¡  Se h2(n) ≥ h1(n) para todos os n (ambas admissíveis) então h2 
domina h1. 
§  h2 é melhor para a pesquisa 
¡  8-puzzle: 
§  (1) os elementos podem mover-se para qualquer lugar. 
§  (2) os elementos podem mover-se para qualquer casa adjacente. 
§  
¡  No problema original os elementos podem mover-se para um 
quadrado adjacentes se ele estiver vazio). 
¡  Custos da busca para o 8-puzzle (número médio de caminhos 
expandidos): 
d = 12 IDS = 3,644,035 caminhos onde d é a profundidade da solução 
 A*(h1) = 227 caminhos 
 A*(h2) = 73 caminhos 
 
d = 24 IDS = caminhos demais 
 A*(h1) = 39,135 caminhos 
 A*(h2) = 1,641 caminhos 
HEURÍSTICA: DOMINÂNCIA 
¡  Como combinar heurística quando não há nenhuma 
dominância? 
¡  Se h1(n) é admissível e h2(n) também é admissível, então 
h(n) = max(h1, h2) também é admissível e domina todos seus 
componentes. 
COMBINANDO HEURÍSTICAS 
¡  Busca informada 
§  Busca pelo melhor-primeiro 
§  Busca A* 
§  Busca em aprofundamento por enumeração e poda 
BUSCA HEURÍSTICA SISTEMÁTICA 
¡  Ideia: selecione o caminho cujo fim está mais próximo a um 
nó objetivo de acordo com a função heurística. 
¡  A busca pelo melhor-primeiro seleciona um caminho na 
fronteira com o valor h mínimo. 
¡  Ela trata a fronteira como uma fila de prioridade ordenada 
por h(n). 
¡  É um algoritmo guloso que seleciona o melhor caminho 
local. 
BUSCA PELO MELHOR-PRIMEIRO 
GRÁFICO ILUSTRATIVO ─ BUSCA PELO 
MELHOR-PRIMEIRO 
• Estado Inic ial : Em(Arad) = Arad 
• Estado Final : Em(Bucharest) = Bucharest 
• Nós que podem gerar c ic los são marcados com *, e não são inser idos na 
fronteira 
 
Começando pelo nó inicial: 
[no(Arad, [Arad], 366)] 
 
Arad não é o objetivo – Expandindo Arad => Sibiu, Timisoara, Zerind, 
[no(Sibiu, [Arad, Sibiu],253), 
 no(Timisoara, [Arad, Timisoara], 329), 
 no(Zerind, [Arad, Zerind], 374)] 
 
Sibiu não é o objetivo – Expandindo Sibiu => Arad*, Fagaras, Oradea, RV 
[no(Fagaras, [Arad, Sibiu, Fagaras], 176), 
 no(RV, [Arad, Sibiu, RV], 193), 
 no(Timisoara, [Arad, Timisoara], 329), 
 no(Zerind, [Arad, Zerind], 374), 
 no(Oradea, [Arad, Sibiu, Oradea], 380)] 
EXEMPLO DE BUSCA PELO MELHOR 
PRIMEIRO (GULOSA) ‏ 
Fagaras não é o objetivo – Expandindo Fagaras => Bucharest, Sibiu* 
[no(Bucharest, [Arad, Sibiu, Fagaras, Bucharest], 0), 
 no(RV, [Arad, Sibiu, RV], 193), 
 no(Timisoara, [Arad, Timisoara], 329), 
 no(Zerind, [Arad, Zerind], 374), 
 no(Oradea, [Arad, Sibiu, Oradea], 380)] 
 
§  Bucharest é o objetivo 
§  Caminho encontrado [Arad, Sibiu, Fagaras, Bucharest] 
§  Custo = 450 
EXEMPLO DE BUSCA PELO MELHOR 
PRIMEIRO (GULOSA) ‏ 
EXEMPLO DE BUSCA PELO MELHOR 
PRIMEIRO (GULOSA) ‏ 
EXEMPLO DE BUSCA PELO MELHOR 
PRIMEIRO (GULOSA) ‏ 
•  Nós em cinza já foram expandidos 
•  Nós em preto não são inseridos por já estarem no 
caminho. 
EXEMPLO DE BUSCA PELO MELHOR 
PRIMEIRO (GULOSA) ‏ 
EXEMPLO DE BUSCA PELO MELHOR 
PRIMEIRO (GULOSA) ‏ 
•  O solução encontrada não é a solução ótima. 
•  A solução ótima passa por Rimnicu Vilcea e Pitest e tem 32 km a 
menos. 
def	
  busca_pelo_melhor_primeiro(G,	
  S,	
  goal):	
  
entrada:	
  G	
  #	
  a	
  grafo	
  
	
   	
  	
  	
  	
  S	
  #	
  um	
  conjunto	
  de	
  nós	
  iniciais	
  
	
   	
  	
  	
  	
  objetivo	
  #	
  função	
  booleana	
  que	
  testa	
  se	
  S	
  é	
  um	
  nó	
  objetivo	
  
	
  
saída:	
  um	
  caminho	
  de	
  um	
  membro	
  de	
  S	
  para	
  um	
  nó	
  para	
  o	
  qual	
  a	
  função	
  	
  	
  
objetivo	
  é	
  verdadeira,	
  ou	
  	
  se	
  não	
  existir	
  solução	
  
	
  
local:	
  fronteira	
  #	
  um	
  conjunto	
  de	
  caminhos	
  
	
  
	
  
fronteira	
  ß	
  {<s>|s	
  ∈	
  S}	
  
	
  
while	
  fronteira	
  :	
  
selecione	
  e	
  remova	
  o	
  1o	
  nó	
  <s0,…,sk>	
  da	
  fronteira	
  
	
  
if	
  objetivo(sk):	
  return	
  <s0,…,sk>	
  
	
  
adicione({<s0,…,sk,s>}|<sk,s>	
  ∈	
  S},	
  fronteira,	
  ordem	
  crescente	
  de	
  h(n))	
  
	
  
return	
  ⟘ 
BUSCA PELO MELHOR PRIMEIRO 
(GULOSA) ‏ 
¡  Usa espaço exponencial no comprimento do caminho O(bm). 
¡  Usa tempo exponencial no comprimento do cominho O(bm). 
¡  Não é garantido que ela encontra uma solução, mesmo se 
houver uma, pois um valor de heurística baixo pode fazer 
com que a busca fique em um ciclo para sempre. 
§  No exemplo abaixo os nós laranja tem valor heurístico melhores 
que os verde, os quais são o caminho certo para a solução 
¡  Nem sempre encontra o caminho 
mais curto. 
COMPLEXIDADE DO BUSCA PELO 
MELHOR-PRIMEIRO 
¡  Usa tanto o custo do caminho até o nó atual quanto o valor da heuríst ica do 
nó atual . 
¡  cost(p ) é o custo do caminho até p . 
¡  h (p ) est ima o custo do f inal do caminho de p até um nó objet ivo. 
¡  Logo, f (p ) = cost(p ) + h(p ) . 
§  f(p) estima o custo total do caminho para ir de um nó de início até um nó objetivo 
passando por p. 
BUSCA A* 
n  Problema: 
n  Ir de Arad à Bucharest. 
 
n  Função heurística: 
n  Distância em linha reta entre a cidade n e Bucharest. 
 
n  Satisfaz a condição de admissibilidade, pois não existe distância 
menor entre dois pontos do que uma reta. 
 
n  É uma boa heurística, pois induz o algoritmo a atingir o objetivo 
mais rapidamente. 
EXEMPLO: BUSCA A* 
EXEMPLO: DE BUSCA A* 
EXEMPLO: DE BUSCA A* 
EXEMPLO: DE BUSCA A* 
EXEMPLO: DE BUSCA A* 
EXEMPLO: DE BUSCA A* 
EXEMPLO: DE BUSCA A* 
¡  A* é uma mistura de busca pelo menor-custo-primeiro 
(baseada em cost(n)) e busca pelo melhor-primeiro 
(baseada em h(n)). 
¡  Ela trata a fronteira como uma fila de prioridade ordenada 
por f(p). 
¡  Ela sempre seleciona o nó p na fronteira com a menor 
distância estimada a partir do início até um nó objetivo, 
restringida a passar pelo nó p. 
ALGORITMO DA BUSCA A* 
def	
  busca_A*(G,	
  S,	
  goal):	
  
entrada:	
  G	
  #	
  a	
  grafo	
  
	
   	
  	
  	
  	
  S	
  #	
  um	
  conjunto	
  de	
  nós	
  iniciais	
  
	
   	
  	
  	
  	
  objetivo	
  #	
  função	
  booleana	
  que	
  testa	
  se	
  S	
  é	
  um	
  nó	
  objetivo	
  
	
  
saída:	
  um	
  caminho	
  de	
  um	
  membro	
  de	
  S	
  para	
  um	
  nó	
  para	
  o	
  qual	
  a	
  função	
  	
  	
  
objetivo	
  é	
  verdadeira,	
  ou	
  	
  se	
  não	
  existir	
  solução	
  
	
  
local:	
  fronteira	
  #	
  um	
  conjunto	
  de	
  caminhos	
  
	
  
	
  
fronteira	
  ß	
  {<s>|s	
  ∈	
  S}	
  
	
  
while	
  fronteira	
  :	
  
selecione	
  e	
  remova	
  o	
  1o	
  nó	
  <s0,…,sk>	
  da	
  fronteira	
  
	
  
if	
  objetivo(sk):	
  return	
  <s0,…,sk>	
  
	
  
adicione({<s0,…,sk,s>}|<sk,s>	
  ∈	
  S},	
  fronteira,	
  ordem	
  crescente	
  de	
  f(n))	
  
	
  
return	
  ⟘ 
 
ALGORITMO DA BUSCA A* 
¡  Vamos supor que os custos do arco são estritamente 
positivos. 
¡  Complexidade de tempo é O(bm) 
§  Se a heurística for completamente não informativa e os custos dos 
arcos forem os mesmos, a busca A* faz a mesma coisa que a 
busca em largura. 
¡  Complexidade de espaço é O(bm) como na busca em 
largura, a busca A* mantém uma fronteira que cresce com o 
tamanho da árvore 
¡  Completa: Sim. 
¡  Ótima: Sim. 
ANÁLISE DA BUSCA A* 
¡  Se houver uma solução, a busca A* sempre encontra a 
solução ótima – i.e. o primeiro caminho para um nó objetivo 
selecionado – se: 
§  O fator de ramificação é finito. 
§  O custo dos arcos são delimitados acima de zero (existe algum 
ε > 0 tal que todos os custos dos arcos são superiores a ε). 
§  h(n) é uma subavaliação do comprimento do caminho mais curto 
da n para um nó de objetivo (heurística admissível). 
¡  No entanto, a complexidade de espaço ainda é um problema. 
 
ADMISSIBILIDADE DA BUSCA A* 
¡  Se um caminho p para um nó objetivo é selecionado da fronteira, 
pode haver um caminho mais curto para um nó objetivo? 
¡  Suponha que caminho p´ está na fronteira. Porque p foi escolhido 
antes de p´ e h(p) = 0: 
 cost(p) ≤ cost(p´) + h(p´): 
¡  Porque h é uma subavaliação: 
 cost(p´) + h(p´) ≤ cost(p´´) 
 para qualquer caminho p´´ até um nó objetivo que estende p´ 
¡  Logo cost(p) ≤ cost(p´´) para quaisquer outros caminhos p´´ até 
um nó objetivo. 
PORQUE A BUSCA A* É ÓTIMA? 
p'' 
p p' 
¡  Há sempre um elemento do caminho da solução ótima na 
fronteira, antes de um nó objetivo ter sido selecionado. 
§  Isso ocorre porque, no algoritmo de pesquisa abstrata, existe a 
parte inicial de cada caminho para um nó objetivo. 
¡  A busca A* para, pois os custos dos caminhos na fronteira 
continuam a aumentar e, eventualmente, eles excederão 
qualquer número finito. 
¡  Se os custos forem positivos não há necessidade verificar a 
existência de ciclos na busca A*, pois os custos dos 
caminhos com ciclos serão sempre maiores e, portanto, não 
serão escolhidos. 
PORQUE A BUSCA A* É ÓTIMA? 
•  Um buscador pode podar um caminho que termina em um nó que 
já está no caminho, sem remover a solução ideal. 
 
•  Usando métodos de busca em profundidade, com o grafo 
explicitamente armazenado, isso pode ser feito em tempo 
constante. 
•  Para outros métodos, o custo é l inear no comprimento do 
caminho. 
VERIFICAÇÃO DE CICLOS 
def	
  busca_em_grafo(G,	
  S,	
  goal):	
  
entrada:G	
  #	
  a	
  grafo	
  
	
   	
  	
  	
  	
  S	
  #	
  um	
  conjunto	
  de	
  nós	
  iniciais	
  
	
   	
  	
  	
  	
  objetivo	
  #	
  função	
  booleana	
  que	
  testa	
  se	
  S	
  é	
  um	
  nó	
  objetivo	
  
	
  
saída:	
  um	
  caminho	
  de	
  um	
  membro	
  de	
  S	
  para	
  um	
  nó	
  para	
  o	
  qual	
  a	
  função	
  objetivo	
  é	
  
	
  verdadeira,	
  ou	
  ⟘	
  se	
  não	
  existir	
  solução	
  
	
  
local:	
  fronteira	
  #	
  um	
  conjunto	
  de	
  caminhos	
  
	
  	
  	
  	
  	
  	
  	
  fechado	
  #	
  conjunto	
  de	
  nós	
  já	
  visitados	
  
	
  
	
  
fechado	
  ß	
  {}	
  
fronteira	
  ß	
  {<s>|s	
  ∈	
  S}	
  
	
  
	
  
while	
  fronteira	
  ≠{  }:	
  
seleciona	
  e	
  remove	
  <s0,…,sk>	
  da	
  fronteira	
  	
  
	
  
if	
  objetivo(sk):	
  return	
  <s0,…,sk>	
  
	
  
if	
  not	
  sk	
  ∈	
  fechado:	
  
	
  fechado	
  ß	
  {sk}	
  
	
  fronteira	
  ß	
  fronteira	
  ∪  {⟨s0,… ,sk,s⟩|⟨𝑠𝑘 ,  𝑠⟩  ∈S}	
  	
  
	
  
return	
  ⟘	
  
ALGORITMO GENÉRICO DE BUSCA EM 
GRAFO COM DETECÇÃO DE CICLO 
•  A remoção de caminho múltiplos consiste em podar um caminho 
para o nó n para o qual o buscador já tenha encontrado um 
outro caminho. 
•  A remoção de caminhos múltiplos engloba a verif icação de 
ciclos. 
•  Isto implica em armazenar na memória todos os nós para os 
quais já se encontrou caminhos. 
•  É importante garantir que após a remoção uma solução ótima 
ainda pode ser encontrada. 
REMOÇÃO DE CAMINHOS MÚLTIPLOS 
¡  Problema: o que fazer se um caminho subsequente para n é 
menor do que o primeiro caminho para n? 
§  Remova todos os caminhos da fronteira que usam o caminho mais 
longo. 
§  Altere o segmento inicial dos caminhos na fronteira para usar o 
caminho mais curto. 
§  Certifique-se de que isto não aconteça, garantindo que o caminho 
mais curto para um nó é encontrado antes. 
REMOÇÃO DE CAMINHOS MÚLTIPLO E 
SOLUÇÕES ÓTIMAS 
¡  Suponha que o caminho p para o nó n foi selecionado, mas ainda 
há um caminho mais curto para n. Suponha que esse caminho 
mais curto é via o nó p´ na fronteira. 
¡  Suponha que caminho p´ termina no nó n´. 
¡  cost(p) + h(n) ≤ cost(p´) + h(n´) porque p foi selecionado antes de 
p´. 
¡  cost(p´) + cost(n´ , n) < cost(p) porque o caminho para n via p´ é 
mais curto. 
cost(n´, n) < cost(p) - cost(p´) ≤ h(n´) - h(n): 
¡  Você pode garantir que isso não ocorrerá caso: 
|h(n´) - h(n)| ≤ cost(n´, n). 
REMOÇÃO DE CAMINHOS MÚLTIPLO E 
BUSCA A* 
¡  A função heurística h satisfaz a restrição monotônica se |
h(m) - h (n) | ≤ custo (m; n) para cada arco <m, n>. 
¡  Se h satisfaz a restrição monotônica, a busca A* com 
remoção de caminhos múltiplos sempre encontra o caminho 
mais curto para um objetivo. 
¡  Este é um reforço ao critério de admissibilidade. 
RESTRIÇÃO MONOTÔNICA 
¡  Remoção de múltiplos caminhos engloba a checagem de ciclos. 
§  Pode ser feito em tempo constante se todos os nós encontrados 
estiverem armazenados. 
 
¡  Remoção de múltiplos caminhos. 
§  Métodos em largura primeiro – quando temos que armazenar 
virtualmente todos os nós considerados. 
 
¡  Checagem de ciclos. 
§  Métodos em profundidade primeiro – quando armazenamos somente o 
caminho para o qual estamos realizando a busca. 
116 
QUANDO USAR? 
¡  É uma forma de combinar a busca em profundidade com 
informações de heurísticas. 
¡  Os nós vizinhos (nós gerados) são ordenados primeiro para 
depois serem colocados na fronteira (que ainda é uma pilha) ‏ . 
 
§  Seleciona localmente qual subárvore expandir, mas continua fazendo 
busca em profundidade. 
 
¡  A complexidade de espaço é linear no tamanho do caminho. 
 
¡  Não garante encontrar uma solução (como a busca em 
profundidade), mas se encontrar é a solução ideal. 
¡  Mais útil quando há várias soluções e queremos uma solução 
ótima. 
BUSCA EM APROFUNDAMENTO POR 
ENUMERAÇAO E PODA (DEPTH-FIRST BRANCH-AND-
BOUND) 
¡  Ideia: manter o custo do caminho de menor-custo 
encontrado até um objetivo até agora, chamar isto de l imite. 
¡  Se a busca encontrar um caminho p tal que 
cost(p) + h(p) ≤ l imite o caminho p pode ser removido. 
¡  Se for encontrado um caminho não-podado para um 
objetivo, ele deve ser melhor do que o melhor caminho 
anterior. Esta nova solução é lembrada e o l imite é definido 
como o seu custo. 
¡  A busca pode ser uma busca em profundidade para 
economizar espaço. 
¡  Como o l imite deve ser inicializado? 
BUSCA EM APROFUNDAMENTO POR 
ENUMERAÇAO E PODA 
¡  O l imite pode ser inicializado em ∞. 
¡  O l imite pode ser definido como uma estimativa do custo do 
caminho ótimo. Após a busca em profundidade terminar 
podemos ter as seguintes situações: 
§  Uma solução foi encontrada. 
§  Nenhuma solução foi encontrada e nenhum caminho foi podado. 
§  Nenhuma solução foi encontrada e um caminho foi removido. 
BUSCA EM APROFUNDAMENTO POR 
ENUMERAÇAO E PODA: INICIALIZANDO O 
LIMITE 
def	
  busca_por_aprofundamento_enumeração_poda(G,	
  S,	
  goal):	
  
entrada:	
  G	
  #	
  a	
  grafo	
  
	
   	
  	
  	
  	
  S	
  #	
  um	
  conjunto	
  de	
  nós	
  iniciais	
  
	
   	
  	
  	
  	
  objetivo	
  #	
  função	
  booleana	
  que	
  testa	
  se	
  S	
  é	
  um	
  nó	
  objetivo	
  
	
  
saída:	
  um	
  caminho	
  de	
  um	
  membro	
  de	
  S	
  para	
  um	
  nó	
  para	
  o	
  qual	
  a	
  função	
  	
  	
  
objetivo	
  é	
  verdadeira,	
  ou	
  	
  se	
  não	
  existir	
  solução	
  
	
  
local:	
  fronteira	
  #	
  um	
  conjunto	
  de	
  caminhos	
  
	
  
	
  
fronteira	
  ß	
  {<s>|s	
  ∈	
  S}	
  
	
  
while	
  fronteira	
  :	
  
selecione	
  e	
  remova	
  o	
  1o	
  nó	
  <s0,…,sk>	
  da	
  fronteira	
  
	
  
if	
  objetivo(sk):	
  return	
  <s0,…,sk>	
  
	
  
adicione({ordenar(<s0,…,sk,s>|<sk,s>	
  ∈	
  S,	
  crescente},	
  fronteira,	
  início)	
  
	
  
return	
  ⟘ 
 
ALGORITMO DA BUSCA EM APROFUNDAMENTO 
POR ENUMERAÇAO E PODA 
EXEMPLO: BUSCA EM APROFUNDAMENTO 
POR ENUMERAÇAO E PODA 
EXEMPLO: BUSCA EM APROFUNDAMENTO 
POR ENUMERAÇAO E PODA 
EXEMPLO: APROFUNDAMENTO POR 
ENUMERAÇAO E PODA 
• Completa: não, pelas mesmas razões que a busca em 
profundidade não é completa. 
• No entanto, para muitos problemas de interesse não há nenhum 
caminho infinito e nenhum ciclo, portanto, para muitos problemas 
B & B é completa. 
• Complexidade de tempo: O(bm) 
• Complexidade de espaço: O(bm) 
• Enumeração e poda tem a mesma complexidade de espaço da 
busca em profundidade. 
 
• Ótima: Sim 
ANALISE DO APROFUNDAMENTO POR 
ENUMERAÇAO E PODA 
Tipo de Busca Seleção da fronteira Completa Ótima Custo de 
Tempo 
Custo de 
Espaço 
Profundidade Último nó adicionado N 
S à sem ciclos e 
espaço de busca finito 
N O(bm) O(mb) 
Largura Primeiro nó adicionado S S O(bm) O(bm) 
Menor-custo-primeiro Mínimo custo à g(n) S à custos > 0 S à custos > 0 O(bm) O(bm) 
Melhor-primeiro Mínimo local à h(n) N O(bm) O(bm) 
A* Mínimo custo estimado 
à f(n) 
S S O(bm) O(bm) 
Aprofundamento 
interativo 
Último nó adicionado 
 
N 
S à sem ciclos e 
espaço de busca finito 
N O(bm) O(mb) 
Aprofundamento 
enumeração-poda 
Mínimo custo estimado 
à f(n) 
N S O(bm) O(mb) 
SUMÁRIO: BUSCA 
¡  A definição de busca é simétrica (se os operadores forem 
reversíveis), i.e. encontrar o caminho dos nós iniciais para 
um nó objetivo ou de um nó objetivo para algum nó inicial. 
§  Fator de ramificaçãopara frente: número de arcos saindo de um 
nó. 
§  Fator de ramificação para trás: número de arcos entrando um nó. 
 
¡  Se a complexidade da busca é bn, deve-se usar a busca 
para frente se o fator de ramificação para frente for inferior 
ao fator de ramificação para trás e vice-versa. 
¡  Nota: às vezes quando o grafo é construído dinamicamente, 
você pode não ser capaz de construir o grafo para trás. 
ESCOLHANDO A DIREÇÃO DA BUSCA 
¡  Resulta em ganho devido ao fato de que 2.bk/2 ≪  bk, o que 
pode resultar em uma economia exponencial no tempo e no 
espaço. 
¡  O principal problema é ter certeza que as fronteiras se 
encontram. 
¡  É muitas vezes usada com um método de busca em largura 
que cria um conjunto de locais que podem levar a um 
objetivo. Na outra direção, outro método pode ser usado 
para encontrar um caminho para esses locais interessantes, 
como a busca em profundidade, por exemplo. 
BUSCA BIDIRECIONAL 
¡  Idéia: encontrar um conjunto de i lhas (pequenos espaços de 
busca) entre s e g. 
S →┴  i1  →┴ i2 →┴  ... →┴   im-1 →┴   g 
¡  Deste modo, tem-se m problemas menores em vez de 1 grande 
problema. Isso resulta em ganho devido ao fato de que mbk/m ≪  
bk . 
¡  O problema está em identif icar as i lhas que o caminho deve 
passar, sendo difíci l garantir otimalidade. 
¡  É possível aplicar a ideia de forma recusrisva, i.e. pode-se 
resolver os subproblemas usando i lhas ⇒┴  hierarquia de 
abstrações. 
BUSCA DIRIGIDA POR ILHA