Principais Tópicos
• Introdução
• Métodos de busca
• Busca cega
• Busca em profundidade
• Busca em amplitude
(largura)
• Busca heurística
• Hill Climbing
• Busca em feixe
• Busca melhor-primeiro
Problema:
• Suponha que você quer descobrir o
caminho de uma cidade (S) para uma
outra (G) usando um mapa
Para encontrar o melhor caminho, dois custos
diferentes devem ser considerados:
• Custo computacional gasto para encontrar um
caminho
• Custo de “viagem” decorrente da utilização deste
caminho
Possíveis situações:
• Viagem frequente: Vale a pena gastar algum
tempo para encontrar um bom caminho
• Viagem rara e difícil de achar um caminho: basta
encontrar um caminho
• Problema pode ser representado por uma rede (grafo)
• Ao percorrer uma rede, deve-se evitar visitar o mesmo
nó
• mais de uma vez
• Representa um ciclo, o que significa que loops infinitos
podem
• ocorrer
• Solução: remover loops
• Remoção de loops
• Solução: traçar todos os caminhos possíveis até não
poder estender nenhum deles sem criar um loop
• Vide próxima imagem
• Um sistema de IA pode resolver problemas da
mesma forma:
• Ele sabe onde ele está (conjunto de informações
iniciais)
• Ele sabe onde deseja ir (estado objetivo)
• Resolver problema em IA envolve busca do estado
objetivo (paradigma de resolução de problemas)
• Forma simplificada de raciocínio
Simples sistemas de IA reduzem raciocínio à busca
• Problemas de busca são
frequentemente descritos utilizando
diagramas de árvores de busca
• Árvores semânticas onde cada nó denota
um passo no caminho do nó inicial para
o nó objetivo
• Nó inicial (I) = onde a busca começa
• Nó objetivo (O) = onde ela termina
• Objetivo: Encontrar um caminho que
ligue o nó inicial a um nó objetivo
• Problema de busca
• Entrada:
• Descrição dos nós inicial e objetivo
• Procedimento que produz os sucessores de um
dado nó
• Saída:
• Sequência válida de nós, iniciando com o nó
inicial e terminando com o nó objetivo
• Exemplo: palavras cruzadas
• Definições importantes:
• Profundidade: número de ligações entre um dado
nó e o nó inicial
• Amplitude: número de sucessores (filhos) de um
nó
• Nó raíz: Nó que não tem pai (ascendente)
• Nó folha: nó que não tem filhos (descendentes)
• Nó objetivo: nó que satisfaz o problema
• Definições importantes:
• Caminho parcial: caminho onde o nó final (folha)
não é um objetivo
• Caminho final ou completo: caminho onde o nó
final é um nó objetivo
• Expandir um nó: gerar as crianças de um nó
• Em busca, você aprende como encontrar um
caminho entre o nó inicial e o nó objetivo
• Problemas da operação de busca
• Com o aumento do tamanho da árvore de busca e
do número de possíveis caminhos, o tempo de
busca aumenta
• Existem várias formas de reduzir o tempo de
busca, alguns dos quais serão discutidos mais
adiante
• Possíveis situações
• Mais de um nó objetivo
• Mais de um nó inicial
• Nestas situações
• Encontrar qualquer caminho de um nó inicial para
um nó objetivo
• Encontrar melhor caminho
Algoritmo básico de busca
1 Definir um conjunto L de nós iniciais;
2 Se L é vazio
Então Busca não foi bem sucedida
Senão Escolher um nó n de L;
3 Se n é um nó objetivo
Então Retornar caminho do nó inicial até n;
Parar
Senão Remover n de L;
Adicionar a L todos os filhos de n, rotulando
cada um com o seu caminho até o nó inicial;
Voltar ao passo 2
Algoritmos de busca
• Existem vários algoritmos de busca diferentes
• O que os distingue é a maneira como o nó n é escolhido
no passo 2
• Métodos de busca
Busca cega: escolha depende da posição do nó na
lista (escolhe o primeiro elemento)
• Busca heurística: escolha utiliza informações específicas
do domínio para ajudar na decisão
• Maneira mais direta de encontrar uma solução:
• Visitar todos os caminhos possíveis, sem repetir um
mesmo nó
• Busca cega não utiliza informações sobre o problema para
guiar a busca
• Estratégia de busca exaustivamente aplicada até
uma solução ser encontrada (ou falhar)
• Ex.: suponha que você deseja encontrar o melhor
caminho de Recife a São Paulo
• Utilizando um mapa de estradas sem as distâncias
• Seu caminho começa em Recife (ponto de partida) e
termina em São Paulo (objetivo)
Busca cega
• Existe um grande número de técnicas
• Busca em Profundidade (BP)
• A árvore é examinada de cima para baixo
• Aconselhável nos casos onde os caminhos
improdutivos não são muito longos
• Busca em Amplitude (BA)
• A árvore é examinada da esquerda para a direita
• Aconselhável quando o número de ramos (filhos)
dos nós não é muito grande (não vale a pena
quando os nós objetivos estão em um mesmo nível)
• Algoritmo BP
1 Definir um conjunto L de nós iniciais
2 Se L é vazio
Então Busca não foi bem sucedida
Senão Seja n o primeiro nó de L;
3 Se n é um nó objetivo
Então Retornar caminho do nó inicial até n;
Parar
Senão Remover n de L;
Adicionar ao início de L todos os filhos de n,
rotulando cada um com o seu caminho até o nó
inicial;
Voltar ao passo 2;
Algoritmo BA
1 Definir um conjunto L de nós iniciais
2 Se L é vazio
Então Busca não foi bem sucedida
Senão Seja n o primeiro nó de L;
3 Se n é um nó objetivo
Então Retornar caminho do nó inicial até n;
Parar
Senão Remover n de L;
Adicionar ao final de L todos os filhos de n,
rotulando cada um com o seu caminho até o nó
inicial;
Voltar ao passo 2;
BA versus BP
• BP e BA não precisam ser realizadas em uma ordem
específica
• Memória utilizada pelas duas técnicas
• BP: precisa armazenar todos os filhos não visitados
entre nó atual e nó inicial
• BA: antes de examinar nó a uma profundidade d, é
necessário examinar e armazenar todos os nós a uma
profundidade d - 1
• BP geralmente utiliza menos memória
BA versus BP
• Quanto ao tempo
• BP é geralmente mais rápida
• Melhor busca depende da árvore
• Quando não se conhece a árvore, pode-se buscar um
compromisso entre BA e BP
• Busca não determinística (BN)
• Combina BA com BP
Busca não determinística
• Escolhe aleatoriamente o nó da árvore a ser expandido
• Tiro no escuro
• Provavelmente vantajosa apenas para árvores muito
pequenas, com uns poucos ramos infinitos
• Alternativa válida se BP e BA são impraticáveis
Algoritmo BN
1 Definir um conjunto L de nós iniciais
2 Se L é vazio
Então Busca não foi bem sucedida
Senão Seja n o primeiro nó de L;
3 Se n é um nó objetivo
Então Retornar caminho do nó inicial até n;
Parar
Senão Remover n de L;
Adicionar em posições aleatórias de L todos os
filhos de n, rotulando cada um com o seu
caminho até o nó inicial;
Voltar ao passo 2;
Busca
• Busca cega não é eficiente
• É necessário limitar de alguma forma o espaço de
busca para torná-la mais rápida e eficiente
• Busca seria mais eficiente se as escolhas pudessem ser
ordenadas
• Escolhas mais promissores seriam exploradas antes
• Em várias situações é possível determinar um
ordenamento razoável
• Alternativas podem ser ordenadas através de
heurísticas
Busca
• Exemplo
• Imagine que você está em uma cidade, e quer pegar
um trem para casa, mas não sabe qual deve pegar
• Se você morasse na zona Norte, naturalmente ignoraria
todos os trens que fossem para o sul
• Se você morasse na zona Sul, naturalmente ignoraria
todos os trens que fossem para o Norte
• Estas heurísticas ajudam a limitar a busca
Busca
• Heurísticas
• Humanos utilizariam “macetes”ou dicas
• Em IA,estas “dicas” são chamadas de heurísticas
• Busca heurística
• Métodos de busca heurística
• Busca hill climbing
• Busca em feixe
• Busca melhor-primeiro
Busca heurística
• Observação
• Tempo gasto avaliando uma função heurística deve ser
recuperado por uma redução correspondente no
espaço de pesquisa
• Atividade nível base: esforço gasto tentando resolver o
problema
• Atividade nível meta: trabalho gasto decidindo como
resolver o problema
• Por que escolher e usar regras heurísticas quando é
mais rápido executar uma busca cega?
Busca heurística
• Observação (cont.)
• Existe um trade-off atividade no nível base versus
atividade no nível meta
• Busca eficiente: tempo gasto no nível meta é
recuperado com reduções no tempo necessário para o
nível base
• As vezes pode ser melhor definir um novo espaço de
busca
Funcionamento – Hill Climbing
• Procurar entre os nós próximos, aquele mais perto do
objetivo
• Seleciona o filho do nó mais próximo do objetivo,
segundo uma medida heurística
• “Raio de visão” limitado à proximidade do nó atual
• Semelhante à otimização de função
• Procurar a combinação de valores dos parâmetros que
fazem com que a função assuma o maior valor
Hill Climbing
Exemplo de funcionamento
• Imagine que você queira escalar uma montanha e:
• Está fazendo uma neblina forte
• Você possui apenas um altímetro e uma bússola
• Procurar o ponto mais alto em um terreno durante uma
caminhada
• Alternativa: dá um passo em cada possível direção e
escolher aquela em que você sobe mais
Hill Climbing
Características
• Funciona como BP, mas escolhe o filho de acordo com sua
“distância” ao objetivo
• Quanto melhor a medida heurística, mais eficiente é a
busca
• Quantidade maior de conhecimento leva a uma redução
no tempo de busca
• Ex.: Suponha que a medida utilizada seja a distância física
ao nó objetivo
Algoritmo Hill Climbing
1 Definir um conjunto L de nós iniciais classificados de acordo com suas
distâncias ao nó objetivo (em ordem crescente)
2 Se L é vazio
Então Busca não foi bem sucedida
Senão seja n o primeiro nó de L;
3 Se n é um nó objetivo
Então Retornar caminho do nó inicial até n;
Parar
Senão Remover n de L;
Ordenar os filhos de n em ordem crescente, de acordo
com suas distâncias ao nó objetivo
Adicionar ao início de L todos os filhos de n, rotulando
cada um com o seu caminho até o nó inicial;
Voltar ao passo 2;
Hill Climbing
Problemas
• Menor caminho da primeira para a segunda cidade pode
levar a uma outra mais distante
• Opção 1: voltar atrás e tomar o segundo menor
caminho, etc
• Este processo de “olhar para a frente e voltar atrás”
certamente leva tempo
• Opção 2: incluir não determinismo
• Número de passos, tamanho dos passos, direção
aleatórios
• Opção 3: utilizar outros métodos heurísticos
Hill Climbing
Problemas
• Máximo local
• Existe um pico mais elevado, que não é
necessariamente o objetivo
• Planície
• Todos os pontos vizinhos levam ao mesmo valor
• Aresta (ponte)
• Existe pelo menos uma direção que aumenta o
valor, mas nenhuma das transições possíveis segue
esta direção
Busca em feixe (BF)
Funcionamento
• Assim como BA, progride nível a nível
• Move para baixo apenas através dos M melhores nós
de cada nível
• Outros nós do mesmo nível são ignorados
• M é constante para todos os níveis
• Vantagens:
• Reduz número de nós visitados
• Escapa do problema de ramificação infinita
Algoritmo BF
1 Definir um conjunto L de nós iniciais
2 Se L é vazio
Então Busca não foi bem sucedida
Senão seja n o primeiro nó de L;
3 Se n é um nó objetivo
Então Retornar caminho do nó inicial até n;
Parar
Senão Remover n de L;
Adicionar ao final de L os M melhores filhos de n,
rotulando cada um com o seu caminho até o nó
inicial;
Voltar ao passo 2;
Busca Melhor-Primeiro
Funcionamento
• Busca segue pelo melhor nó aberto (que ainda tem filho
para ser visitado)
• Hill Climbing sem a restrição da busca em profundidade
• Escolhe o melhor nó n da lista L
• Geralmente encontra caminhos mais curtos que o Hill
Climbing
• Sempre move em direção ao nó mais próximo do
objetivo, não importa onde ele esteja na árvore
Algoritmo Melhor-Primeiro
1 Definir um conjunto L de nós iniciais
2 Seja n o nó de L mais próximo do objetivo;
Se L é vazio
Então Busca não foi bem sucedida
3 Se n é um nó objetivo
Então Retornar caminho do nó inicial até n;
Parar
Senão Remover n de L;
Adicionar a L todos os filhos de n, rotulando cada
um com o seu caminho até o nó inicial;
Voltar ao passo 2;
Observações
• Perguntas a serem feitas antes de utilizar métodos de
busca:
• Busca é a melhor maneira para resolver o problema?
• Quais métodos de busca resolvem o problema?
• Qual deles é o mais eficiente para este problema?
Conclusão
• Definições básicas
• Busca cega
• Busca em profundidade
• Busca em largura
• Busca não determinística
• Busca heurística
• Hill Climbing
• Busca em Feixe
• Busca Best first