meio de busca Seções 3.1, 3.2 e PDF
Download "meio de busca Seções 3.1, 3.2 e 3.3"
Francisca Azevedo Wagner
1 Resolução de problemas por meio de busca Capítulo 3 Russell & Norvig Seções 3.1, 3.2 e 3.3
2 Agentes de resolução de problemas Agentes reativos não funcionam em ambientes para quais o número de regras condição ação é grande demais para armazenar. mais simples, baseiam suas ações em um mapeamento direto de estados em ações. Nesse caso podemos construir um tipo de agente baseado em objetivo chamado de agente de resolução de problemas. 2
3 Busca Um agente com várias opções imediatas pode decidir o que fazer comparando diferentes sequências de ações possíveis. Esse processo de procurar pela melhor sequência é chamado de busca. Um algoritmo de busca recebe um problema como entrada e retorna uma solução sob forma de uma sequência de ações. Formular obje vo buscar executar 3
4 Exemplo: Romênia De férias na Romênia; atualmente em Arad. Vôo sai amanhã de Bucareste. Formular objetivo: Estar em Bucareste Formular problema: estados: cidades ações: dirigir entre as cidades Encontrar solução: sequência de cidades, ex., Arad, Sibiu, Fagaras, Bucareste. 4
5 Exemplo: Romênia 5
6 Formulação de problemas Umproblema é definido porquatroitens itens: 1. Estado inicial ex., em Arad" 2. Ações ou função sucessor S(x) () = conjunto de pares estado ação ex., S(Arad) = {<Arad Zerind, Zerind>, } 3. Teste de objetivo, pode ser explícito, ex., x = em Bucharest" implícito, ex., Cheque mate(x) 4. Custo de caminho (dii (aditivo) ex., soma das distâncias, número de ações executadas, etc. c(x,a,y) é o custo do passo, que deve ser sempre 0 Uma solução é uma sequência de ações que levam do estado inicial para o estado objetivo. Uma solução ói ótima é uma solução com o menor custo de caminho. 6
7 Agente de Resolução de Problemas função AGENTE DE RESOLUÇÃO DE PROBLEMAS SIMPLES SIMPLES (percepção) ã retorna uma ação entradas: percepção, uma percepção variáveis estáticas: seq, uma sequência de ações, inicialmente vazia estado, alguma descrição do estado atual do mundo objetivo, um objetivo, inicialmente nulo Determinístico: as soluções para problema, uma formulação de problema problemas são sequências de ações únicas, e assim elas não podem lidar estado ATUALIZAR ESTADO(estado, percepção) com quaisquer eventos inesperados; além disso, as soluções são seseq seq está vazia então faça Observável: executadas o estado sem atenção inicial é às objetivo FORUMLAR OBJETIVO(estado) Estático: porque conhecido; percepções a formulação mais fácil conhecê lo e problema FORMULAR PROBLEMA(estado, objetivo) resolução do problema é feita sem seq BUSCA(problema) dedicar atenção a quaisquer Discreto: mudanças a idéia de enumerar ação PRIMEIRO(seq) que possam estar cursos ocorrendo alternativos no de ação seq RESTO(seq) ambiente retornar ação Supõe que ambiente é estático, observável, discreto e determinístico. 7
8 Espaço de estados O conjunto de todos os estados acessíveis a partir de um estado inicial é chamado de espaço de estados. Os estados acessíveis são aqueles dados pela função sucessora. O espaço de estados pode ser interpretado como um grafo em que os nós são estados e os arcos são ações. 8
9 Selecionando um espaço de estados O mundo real é absurdamente complexo o espaço de estados é uma abstração Estado (abstrato) = conjunto de estados reais Ação (abstrata) = combinação complexa de ações reais ex., "Arad Zerind" representa um conjunto complexo de rotas, desvios, paradas, etc. Qualquer estado real do conjunto em Arad deve levar a algum estado real em Zerind. Solução (abstrata) = conjunto de caminhos reais que são soluções no mundo real A abstração é útil se cada ação abstrata é mais fácil de executar que o problema original. 9
10 Exemplo 1: Espaço de Estados do Mundo do Aspirador de Pó Estados: Definidos pela posição do robô e sujeira (8 estados) Estado inicial: Qualquer um Função sucessor: gera os estados td válidos que resultam da tentativa t ti de executar as três ações (esquerda, direita, aspirar). O espaço de estados completos estão mostrados na figura. Teste de objetivo: Verifica se todos osquadrados estão limpos Custo do caminho: Cada passo custa 1, e assim o custo do caminho é o número de passos do caminho 10
11 Exemplo 2: O quebra cabeça de 8 peças Etd Estados: Especifica a posição iã de cada uma das peças e do espaço vazio Estado inicial: Qualquer um Função sucessor: gera os estados válidos que resultam da tentativa de executar as quatro ações (mover espaço vazio para esquerda, direita, it acima ou abaixo) bi Teste de objetivo: Verifica se o estado corresponde à configuração objetivo. Custo do caminho: Cada passo custa 1, e assim o custo do caminho é o número de passos do caminho 11
12 Exemplo 3:Oito rainhas Quase solução Formulação incremental Objetivo: posicionar oito rainhas em um tabuleiro de xadrez de tal forma que nenhuma rainha ataque qualquer outra. - Uma rainha ataca qualquer peça situada na mesma linha, coluna ou diagonal. Estados: qualquer q disposição de 0 a 8 rainhas Estado inicial: nenhuma rainha Função sucessor: colocar 1 rainha em qualquer vazio Teste: 8 rainhas no tabuleiro, nenhuma atacada 64x63x...57 = 3x10 14 sequências para investigar 12
13 Exemplo 3:Oito rainhas Formulação de estados completos lt Quase solução Estados: disposições de n rainhas, uma por coluna, nas n colunas mais a esquerda sem que nenhuma rainha ataque outra Estado inicial: todas asrainhas no tabuleiro Função sucessor: adicionar uma rainha a qualquer quadrado na coluna vazia mais à esquerda, de tal modo que ela não seja atacada Tamanho do espaço de estados:
14 Problemas do mundo real Problema de roteamento encontrar a melhor rota de um ponto a outro (aplicações: redes de computadores, planejamento militar, planejamento de viagens aéreas) Problemas de tour visitar cada ponto pelo menos uma vez Caixeiro viajante visitar iit cada cidade d exatamente t uma vez encontrar o caminho mais curto Layout de VLSI posicionamento de componentes e conexões em um chip Projeto de proteínas encontrar uma sequência de aminoácidos id que serão incorporados em uma proteína tridimensional para curar alguma doença. Pesquisas na Web é fácil pensar na Web como um grafo de nós conectados por links 14
15 Busca de soluções Depois de formular alguns problemas, agora precisamos resolvê los!! los!! Isso é feito por meio de uma busca em todo o espaço de estados. Idéia: Percorrer o espaço de estados a partir de uma árvore de busca. Expandir o estado atual aplicando a função sucessor, gerando novos estados. Busca: seguir um caminho, deixando os outros para depois. A estratégia de busca determina qual caminhoseguir seguir. 15
16 Exemplo de árvore de busca Estado inicial 16
17 Exemplo de árvore de busca Depois de expandir Arad 17
18 Exemplo de árvore de busca Depois de expandir Sibiu 18
19 Descrição informal do algoritmo geral de busca em árvore 19
20 Árvore de busca não é equivalente a espaço de estados! Há 20 estados no mapa da Romênia (espaço de estados), mas infinitos caminhos a percorrer. Portanto a árvore de busca, neste caso, tem tamanho infinito. Caminho infinito: Arad Sibiu Arad Sibiu Arad... 20
21 Estados vs. nós Um estado é uma (representação de) uma configuração física Um nó é uma estrutura de dados que é parte da árvore de busca e inclui estado, nó pai, ação, custo do caminho g(x), profundidade A função Expand cria novos nós, preenchendo os vários campos e usando a função sucessor do problema para gerar os estados correspondentes. A coleção de nós que foram gerados, mas ainda não foram expandidos é chamada de borda (ou fringe) Cada elemento da borda é um nó folha (ie, um nó sem sucessores na árvore) Geralmente implementados como uma fila. A maneira como os nós entram na fila determina a estratégia de busca. 21
22 Algoritmo geral de busca em árvore 22
23 Estratégias de busca Uma estratégia de busca é definida pela escolha da ordem da expansão de nós Estratégias são avaliadas de acordo com os seguintes critérios: completeza: o algoritmo sempre encontra a solução se ela existe? complexidade de tempo: número de nós gerados complexidade de espaço: número máximo de nós na memória otimização: a estratégia encontra a solução ótima? Complexidade de tempo e espaço são medidas em termos de: b: máximo fator de ramificação da árvore (número máximo de sucessores de qualquer nó) d: profundidade do nó objetivo menos profundo m: o comprimento máximo de qualquer caminho no espaço de estados td (pode ser ) ) Custo: Custo de busca: em geral depende da complexidade de tempo, mas também pode incluir um termo para uso da memória Custo total: combina o custo de busca e o custo de caminho da solução encontrada 23
ENG1000 Introdução à Engenharia Aula 09 Vetores e Matrizes Edirlei Soares de Lima Introdução Até agora nós temos usado variáveis simples para armazenar valores usados por nossos
Eleição de Líder. Alysson Neves Bessani Departamento de Informática Faculdade de Ciências da Universidade de Lisboa
Eleição de Líder Alysson Neves Bessani Departamento de Informática Faculdade de Ciências da Universidade de Lisboa Algoritmos de Eleição Muitos algoritmos distribuídos necessitam de seleccionar um processo
Inteligência Artificial IA I. MÉTODOS DE BUSCA
Inteligência Artificial IA Prof. João Luís Garcia Rosa I. MÉTODOS DE BUSCA 2004 V1.4 Sistema de Produção Sistema de Produção: Base de dados global Regras de produção Estratégia de controle Exemplo: tabuleiro
Método de ordenação - objetivos:
Método de ordenação - objetivos: Corresponde ao processo de rearranjar um conjunto de objetos em uma ordem ascendente ou descendente. Facilitar a recuperação posterior de itens do conjunto ordenado. São
ALGORITMOS E COMPLEXIDADE PROBLEMAS E ALGORITMOS
ALGORITMOS E COMPLEXIDADE PROBLEMAS E ALGORITMOS Algoritmos e Complexidade 1 Plano Problemas e algoritmos. Estrutura de um algoritmo e dados manipulados. Métodos algorítmicos para resolução de problemas.
Arquivos Indexados por Chaves Secundárias. Vanessa Braganholo
Arquivos Indexados por Chaves Secundárias Vanessa Braganholo Arquivos Indexados } Até agora, as alternativas que vimos funcionam apenas para indexar arquivos por chaves primárias } Isso otimiza a busca
Introdução à Inteligência Artificial 2007/08
Introdução à Inteligência rtificial 2007/08 Procura em contextos competitivos jogos Contexto Um agente vs multiagente mbiente cooperativo vs competitivo Teoria dos jogos (ramo da Economia) Sistema multiagente
I. Introdução a IA Slides IA-1-introducao.pdf II. Agentes Inteligentes
I. Introdução a IA Slides IA-1-introducao.pdf II. Agentes Inteligentes 1. Definição: Um agente é tudo o que pode ser considerado capaz de perceber seu ambiente por meio de sensores e de agir sobre esse
Arquivos Seqüenciais Atualização em Lote
Arquivos Seqüenciais Atualização em Lote Vanessa Braganholo Baseado no Material de: Inhaúma Neves Ferraz (IC/UFF) Cenário } Arquivos Sequenciais Ordenados } Objetivo: atualizar o arquivo, mantendo sua
2 Conceitos Básicos. onde essa matriz expressa a aproximação linear local do campo. Definição 2.2 O campo vetorial v gera um fluxo φ : U R 2 R
2 Conceitos Básicos Neste capítulo são apresentados alguns conceitos importantes e necessários para o desenvolvimento do trabalho. São apresentadas as definições de campo vetorial, fluxo e linhas de fluxo.