Buscas Informadas ou Heurísticas - Parte II - PDF
Download "Buscas Informadas ou Heurísticas - Parte II"
Sérgio Amado Guterres
1 Buscas Informadas ou Heurísticas - Parte II Prof. Cedric Luiz de Carvalho Instituto de Informática - UFG Graduação em Ciência da Computação / 2006
2 FUNÇÕES HEURÍSTICAS - 1/7
3 FUNÇÕES HEURÍSTICAS - 2/7 Solução típica: 20 passos (dependendo do estado inicial) Fator de ramificação: 3 Espaço no centro: 4 Espaço nos cantos: 2 Espaços em outras posições: 3 Busca exaustiva até a profundidade 20: Examina 3 20 = 3.5x10 9.
4 FUNÇÕES HEURÍSTICAS - 3/7 Verificação de estados repetidos: São 9! = arranjos de 9 ladrilhos. Solução melhor: heurística. h 1 = número de ladrilhos em posições erradas. Na figura anterior: 7 dos 8 estão em posições erradas h1 = 7. h 2 = soma das distâncias do ladrilhos até a meta (distâncias verticais + horizontais).
5 FUNÇÕES HEURÍSTICAS - 3/7 Distância Manhattan - para os ladrilhos de 1 a 8: h 2 = = 18
6 FUNÇÕES HEURÍSTICAS - 4/7 b*: Efeito da precisão da heurística na performance. Para uma árvore uniforme, se o número total de nós expandidos por A*, para um problema particular é N e profundidade da solução é d, então: N = 1 + b +(b ) (b ) d. Fator de ramificação efetivo
7 FUNÇÕES HEURÍSTICAS - 5/7 Normalmente, o fator de ramificação efetivo de uma dada heurística é constante. Valores experimentais medidos de b*, para pequenos conjuntos de problemas, podem representar boas dicas para heurísticas de uso mais amplo.
8 FUNÇÕES HEURÍSTICAS - 6/7 Uma boa heurística: Deve ter um b* próximo de 1. Para testar heurísticas (h 1, h 2 ): Gera-se, aleatoriamente, 100 problemas com soluções de comprimento 2, 4,..., 20. Resolve-se os problemas usando-se Busca A* (com h 1 e h 2 ) e também Busca com Aprofundamento Iterativo (IDS).
9 FUNÇÕES HEURÍSTICAS - 7/7 Custo da Busca b* D IDS A*(h 1 ) A*(h 2 ) IDS A*(h 1 ) A*(h 2 )
10 CRIANDO HEURÍSTICAS 1/9 As restrições sobre os operadores podem ser aliviadas: o problema pode ser relaxado. O custo de uma solução exata para um problema relaxado pode ser uma boa heurística para o problema original.
11 CRIANDO HEURÍSTICAS 2/9 Se a definição do problema está escrita em uma linguagem formal é possível construir problemas relaxados automaticamente. Exemplo Quebra-cabeças de 8 Um ladrilho pode ser mover de A para B se A e B são adjacentes e B é vazio.
12 CRIANDO HEURÍSTICAS 3/9 Uma (ou mais) das condições a seguir podem ser removidas: gera-se novos problemas. 1. O movimento pode acontecer se A é adjacente a B. 2. O movimento pode acontecer se B está vazio. 3. O movimento pode acontecer de A para B.
13 CRIANDO HEURÍSTICAS 4/9 Pode-se ter várias heurísticas admissíveis. Deve-se escolher uma. Pode-se obter a melhor solução definindo-se a função: h(n) = max(h 1 (n),..., h m (n)) - n: nó sendo considerado.
14 CRIANDO HEURÍSTICAS 5/9 Pode-se usar informações estatísticas: Executa-se a busca sobre alguns problemas de treinamento. Exemplo Pode-se tomar 100 instâncias do quebra-cabeças escolhidas aleatoriamente. Pode-se identificar que se h 2 (n) = 14, 90% das vezes a distância real até meta é 18. Ao tratar problemas reais: se h 2 (n) indicar 14, usa-se 18.
15 CRIANDO HEURÍSTICAS 6/9 Uso de probabilidades: Pode-se estar abrindo mão da garantia de admissibilidade. É provável que se expanda menos nós, na média.
16 CRIANDO HEURÍSTICAS 7/9 Características dos estados podem contribuir na definição da heurística, mesmo quando é difícil estabelecer qual contribuição seria. Exemplo No xadrez: Número de peças de cada tipo dos oponentes. Número de peças sendo atacadas pelo adversário. Etc.
17 CRIANDO HEURÍSTICAS 8/9 A função pode ser considerada como uma combinação linear dos valores selecionados. Mesmo se não se sabe a importância das características selecionadas; ou Se tais características são boas ou ruins. Um algoritmo de aprendizado pode identificar coeficientes razoáveis para cada característica.
18 CRIANDO HEURÍSTICAS 9/9 O custo do cálculo da função heurística pode ser relevante. O custo do cálculo da função heurística pode ser relevante. Uma boa heurística deve ser eficiente e precisa.
19 PROBLEMA DA COLORAÇÃO DE MAPAS - 1/6 Deve-se evitar que países adjacentes sejam coloridos com a mesma cor. Pode-se usar, no máximo, três cores: verde, vermelho e amarelo. O país A deve aparecer em verde e o país B em vermelho.
20 PROBLEMA DA COLORAÇÃO DE MAPAS - 2/6
21 PROBLEMA DA COLORAÇÃO DE MAPAS - 3/6
22 PROBLEMA DA COLORAÇÃO DE MAPAS - 4/6
23 PROBLEMA DA COLORAÇÃO DE MAPAS - 5/6
24 HEURÍSTICAS PARA PROBLEMAS COM RESTRIÇÕES (CSPs) - 6/6 Não é necessário busca para a resolução do problema: pode-se usar a intuição. Heurística da variável-mais-restrita. É usada em conjunto com a checagem adiante ( foward checking ).
25 HEURÍSTICA DA VARIÁVEL-MAIS-RESTRITA. Identifica os valores que ainda são permitidos para cada variável, em função das escolhas feitas até o momento. A cada momento: A variável com menos possíveis valores é escolhida para ser instanciada. O fator de ramificação tende a ser minimizado.
26 HEURÍSTICA DA VARIÁVEL-MENOS-RESTRITA. Escolher um valor que exclua o menor número possível de valores para as variáveis conectadas à variável corrente pelas restrições. No exemplo anterior: após instanciar A e B, pode-se decidir instanciar C com vermelho, pois esta escolha dá mais opções para futuras escolhas.
27 BUSCA A* - APROFUNDAMENTO ITERATIVO (IDA*) Cada iteração é uma busca em profundidade. O algoritmo de Busca em Profundidade é modificado: Usa-se uma função de custo f, ao invés de um limite de profundidade.
28 AVALIAÇÃO DA BUSCA IDA* Completa e ótima (nas mesmas condições de A*). Como é feita uma Busca em Profundidade: Requer um espaço proporcional ao caminho mais longo que é explorado.
29 AVALIAÇÃO DA BUSCA IDA* Não precisa inserir e retirar nós de uma fila de prioridades: Sua sobrecarga por nó é muito menor que A*. A solução ótima para muitos problemas práticos é encontrada primeiro por IDA*.
30 AVALIAÇÃO DA BUSCA IDA* Não produz bons resultados em domínios muito complexos. Exemplo: problema do caixeiro viajante. O valor heurístico é diferente para cada estado. Cada contorno de f: inclui apenas um nó a mais. Se A* expande N nós: IDA* terá de realizar N iterações terá de expandir N = O(N 2 ) nós.
31 COMPLEXIDADE TEMPORAL Depende fortemente do número de valores diferentes que a função heurística pode tomar. Tipicamente, a função f aumenta duas ou três vezes ao longo do caminho até a solução. Na última iteração: IDA* expande exatamente o mesmo número de nós que A*.
32 ALGORITMO ADMISSÍVEL-ε O limite de custo f pode ser expandido por um valor fixo ε em cada iteração. O número total de iterações é proporcional a 1/ε. Reduz o custo da busca, mas pode retornar uma solução pior que a ótima.
33 BUSCA A* - APROFUNDAMENTO ITERATIVO (IDA*) Não pode lembrar sua história : é condenado a repetí-la. O problema é mais grave quando o espaço de estados é um grafo ao invés de uma árvore. Pode ser modificado para verificar estados repetidos em um mesmo caminho. Não se pode evitar estados repetidos gerados por caminho alternativos.
Figura: Capa do Livro Hamburger, H., Richards, D. Logic and Language Models for Computer Science, Prentice Hall. Universidade Federal de Campina Grande Departamento de Sistemas e Computação Pós-Graduação
Estratégias de Busca: Métodos Informados. March 9, 2015
Estratégias de Busca: Métodos Informados March 9, 2015 Busca de Soluções: Métodos Informados Utilizam conhecimento específico do problema para encontrar a solução algoritmo geral de busca somente permite
Buscas Informadas ou Heurísticas - Parte I
Buscas Informadas ou Heurísticas - Parte I Prof. Cedric Luiz de Carvalho Instituto de Informática - UFG Graduação em Ciência da Computação / 2006 BUSCAS INFORMADAS OU HEURÍSTICAS Consideram a probabilidade
Lista de exercícios 1 Paulo Gurgel Pinheiro MC906A - Inteligência Articial Universidade Estadual de Campinas - UNICAMP pinheiro@ic.unicamp.br 3 de setembro de 2010 1. Considere o problema do quebra-cabeças
Inteligência Artificial Resolvendo Problemas com Busca Agente solucionador de problemas (guiado por objetivo deliberativo) Busca uma sequência de ações que o leve a estados desejáveis (objetivos). Propriedades
Procura Informada. Capítulo 4
Procura Informada Capítulo 4 Material Capítulo 4 Secções 1-3 Resumo Estratégias de procura informadas Gananciosa A * IDA* Melhor Primeiro Recursiva (RBFS) Heurísticas Algorítmos de procura local Hill-climbing
Aula 05 Busca com informação
Revisão Aula 05 Busca com informação Prof. Dr. Alexandre da Silva Simões Principais estratégias de busca sem informação: busca em amplitude e profundidade Estratégias derivadas: Busca com custo uniforme
Trabalho 1: Busca no Pacman
Trabalho 1: Busca no Pacman Este trabalho é parte do Pacman Project desenvolvido na UC Berkeley disciplina CS188 Artificial Intelligence. A tradução é da prof. Bianca Zadrozny, UFF. Adaptação do prof.
Tópicos Especiais: Inteligência Artificial
Tópicos Especiais: Inteligência Artificial RESOLUÇÃO DE PROBLEMAS POR MEIO DE BUSCA Material baseado e adaptado do Cap. 3 do Livro Inteligência Artificial de Russel & Norving Bibliografia Inteligência
Computação Evolutiva. Aula 4 Usando AEs Prof. Tiago A. E. Ferreira
Computação Evolutiva Aula 4 Usando AEs Prof. Tiago A. E. Ferreira Roteiro Exemplos: Problema das 8 rainhas Comportamentos Típicos dos AE CE no contexto da Otimização Global Relembrando Na Aula Passada,
Inteligência Artificial. Estratégias de Busca Outros. Huei Diana Lee
Inteligência Artificial Estratégias de Busca Outros Huei Diana Lee Redução de Problemas Até então consideramos estratégias para as quais o espaço de busca é representado por meio de Grafos OU Objetivo:
Seleção de Atributos 1
Seleção de Atributos 1 Tópicos Por que atributos irrelevantes são um problema Quais tipos de algoritmos de aprendizado são afetados Seleção de atributos antes do aprendizado Benefícios Abordagens automáticas
INTRODUÇÃO À INTELIGÊNCIA COMPUTACIONAL. Aula 02 Prof. Vitor Hugo Ferreira
Universidade Federal Fluminense Escola de Engenharia Departamento de Engenharia Elétrica INTRODUÇÃO À INTELIGÊNCIA COMPUTACIONAL Aula 02 Prof. Vitor Hugo Ferreira Agentes Inteligentes O que torna um agente
PROCURA E PLANEAMENTO Primeiro Exame 10 de Janeiro de 2012 9:00-11:30 Este exame é composto por 16 páginas contendo 6 grupos de perguntas. Identifique já todas as folhas do exame com o seu nome e número.
REDES NEURAIS / INTELIGÊNCIA ARTIFICIAL LISTA DE EXERCÍCIOS 6
REDES NEURAIS / INTELIGÊNCIA ARTIFICIAL LISTA DE EXERCÍCIOS 6 Aluno: 1. Defina o problema de busca (espaço de estados, estado inicial, estado final, ações possíveis, custo) para o seguinte caso: uma pessoa,
Sistemas Inteligentes / Inteligência Artificial, Outros Métodos de Procura
Sistemas Inteligentes / Inteligência Artificial, 14-15 1 Outros Métodos de Procura Sistemas Inteligentes / Inteligência Artificial, 14-15 2 Exemplos de Aplicações Jogo dos oito :-) Mundo dos blocos (ex:
RESOLUÇÃO DE PROBLEMAS Extraído de notas de aula do prof. Michel Gagnon École Polytechnique de Montréal http://www.professeurs.polymtl.ca/michel.gagnon/disciplinas/bac/ia/index_ia.html Conteúdo: Noções