Upload
julio-mendonca-sabala
View
233
Download
3
Embed Size (px)
Citation preview
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 custosdiferentes devem ser considerados:• Custo computacional gasto para encontrar um
caminho• Custo de “viagem” decorrente da utilização destecaminho 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: bastaencontrar 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 damesma 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 estadoobjetivo (paradigma de resolução de problemas)• Forma simplificada de raciocínio Simples sistemas de IA reduzem raciocínio à busca
• Problemas de busca sãofrequentemente descritos utilizandodiagramas de árvores de busca• Árvores semânticas onde cada nó denota
um passo no caminho do nó inicial parao nó objetivo
• Nó inicial (I) = onde a busca começa• Nó objetivo (O) = onde ela termina
• Objetivo: Encontrar um caminho queligue 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 busca1 Definir um conjunto L de nós iniciais;2 Se L é vazio
Então Busca não foi bem sucedidaSenão Escolher um nó n de L;
3 Se n é um nó objetivoEntão Retornar caminho do nó inicial até n;
PararSenã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ó nalista (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 BP1 Definir um conjunto L de nós iniciais2 Se L é vazio
Então Busca não foi bem sucedidaSenão Seja n o primeiro nó de L;
3 Se n é um nó objetivoEntão Retornar caminho do nó inicial até n;
PararSenã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 BA1 Definir um conjunto L de nós iniciais2 Se L é vazio
Então Busca não foi bem sucedidaSenão Seja n o primeiro nó de L;
3 Se n é um nó objetivoEntão Retornar caminho do nó inicial até n;
PararSenã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 BN1 Definir um conjunto L de nós iniciais2 Se L é vazio
Então Busca não foi bem sucedidaSenão Seja n o primeiro nó de L;
3 Se n é um nó objetivoEntão Retornar caminho do nó inicial até n;
PararSenã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 ClimbingExemplo 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 ClimbingCaracterí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 Climbing1 Definir um conjunto L de nós iniciais classificados de acordo com suasdistâncias ao nó objetivo (em ordem crescente)2 Se L é vazio
Então Busca não foi bem sucedidaSenão seja n o primeiro nó de L;
3 Se n é um nó objetivoEntão Retornar caminho do nó inicial até n;
PararSenã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, rotulandocada um com o seu caminho até o nó inicial;Voltar ao passo 2;
Hill ClimbingProblemas• 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 ClimbingProblemas• 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 BF1 Definir um conjunto L de nós iniciais2 Se L é vazio
Então Busca não foi bem sucedidaSenão seja n o primeiro nó de L;
3 Se n é um nó objetivoEntão Retornar caminho do nó inicial até n;
PararSenã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-PrimeiroFuncionamento• 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-Primeiro1 Definir um conjunto L de nós iniciais2 Seja n o nó de L mais próximo do objetivo;
Se L é vazioEntão Busca não foi bem sucedida
3 Se n é um nó objetivoEntão Retornar caminho do nó inicial até n;
PararSenã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