Resolução de Problemas por Meio de Busca Cega no Espaço Extensional de Hipótese Disciplina: Métodos de Computação Inteligente – 1 Aluno: André Felipe Santana

  • View
    106

  • Download
    0

Embed Size (px)

Text of Resolução de Problemas por Meio de Busca Cega no Espaço Extensional de Hipótese Disciplina:...

  • Slide 1
  • Resoluo de Problemas por Meio de Busca Cega no Espao Extensional de Hiptese Disciplina: Mtodos de Computao Inteligente 1 Aluno: Andr Felipe Santana
  • Slide 2
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Resolu o de Problemas por Meio de Busca Cega no Espa o Extensional de Hip tese Objetivo Geral do Seminrio: Apresentar o mtodo de busca cega como meio direto de resoluo de problemas genricos. Objetivos Especficos: Definir o que um problema sob a tica da agentes inteligentes Descrever a formulao de problemas e ilustrar com exemplos Apresentar busca como mtodo genrico de resoluo de problemas Definir busca cega e ilustrar sua implementao Apresentar os diversos mtodos de busca cega com anlise comparativa de desempenho Apresentar restries do uso de busca com informao parcial
  • Slide 3
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE O que um problema? Qualquer situao a ser resolvida por uma seqncia aes a ser executada, com vistas a atingir um objetivo; Na descrio acima: Situao = estado inicial; Seqncia de Aes = operaes que iro gerar uma sucesso de estados; Objetivo = estado final (ou conjunto de) desejado; Metfora da resoluo de problemas por meio de busca: Transformar um problema de raciocnio de um agente diretamente em um problema de navegao num espao de estados, no qual, a partir de um estado inicial, um agente pode buscar uma seqncia de aes que conduzem ao estados final desejado. A soluo de um problema conjunto de seqncias de aes que levam de um estado inicial ao estado objetivado Uma soluo tima uma seqncia de aes que leva de um estado inicial ao estado objetivado com o menor custo*.
  • Slide 4
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Romnia: ir de Arad a Bucharest
  • Slide 5
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Antes de qualquer coisa... Formular o problema Formular o objetivo: definir um estado final que satisfaz o agente ex: Estar em Bucareste Especificar o problema em termos de: Estado Inicialex: Estou em Arad Funo Sucessor S(x) = conjunto de pares ao-estado ex: S(Arad) = { (Arad Zerind, Zerind), (Arad Sibiu, Sibiu),......} Teste do Objetivo: condio que capaz de determinar se o estado final foi alcanado ex: Estou em Bucareste? Custo (path cost)ex: soma de distancias, n de aes executadas, etc.
  • Slide 6
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE A Formulao do Problema define o Espao de Estados possveis O Espao de Estados definido implicitamente pelo estado inicial juntamente com todos os estados alcanveis atravs da funo sucessora S(x). Forma um grafo onde os ns representam estados e os arcos entre os ns representam aes. Entretanto : Estado Corresponde a uma configurao do mundo. Ex: estou em Bucareste N Estrutura de Informao que compe uma seqncia percorrida. Ex: N(Bucareste) (1) Antecessor = N(Pitesti) Path-cost = 418 Km N(Bucareste) (2) Antecessor = N(Fagars) Path-cost = 450 Km
  • Slide 7
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE A Formulao do Problema exige Abstrao do Mundo Real O mundo real absurdamente complexo: espao de estados tem que ser abstrado para a resoluo de problemas. Estado (abstrato) = conjunto de estados reais Ao (abstrata) = combinao complexa de aes reais, onde cada ao abstrata deveria ser mais fcil que o problema original. Ex: Arad Zerind representa um complexo de rotas possveis, paradas para descanso, etc. Soluo (abstrata) = conjunto de caminhos reais que so solues no mundo real para o problema.
  • Slide 8
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Importncia de uma Formulao adequada do Problema O Espao de Estados derivado da formulao do problema impacta na eficincia de busca da soluo Ex: Problema das 8 Rainhas Dispor 8 rainhas num tabuleiro de xadrez, sem que qualquer uma delas esteja sob ataque das demais: no pode haver mais de uma rainha em uma mesma linha, coluna ou diagonal somente o custo da busca conta (n de passos para a soluo)
  • Slide 9
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Importncia de uma Formulao adequada do Problema Problema das 8 Rainhas - Formulao 1: estado inicial: nenhuma rainha no tabuleiro operadores: adicionar uma rainha a qualquer quadrado vazio teste do objetivo: 8 rainhas no tabuleiro sem ataque mtuo?.... E assim por diante, at 64 x 63 x 62 x..... x 57 1,8 x 10 14 seqncias possveis a serem testadas [_,_] 0: [1,1] [1,2][2,1]....... [1,8] [2,2]....... [2,8][8,1] [8,2]....... [8,8]....... (64 estados possveis) 1: [1,2][2,1]....... [1,8] [2,2]....... [2,8][8,1] [8,2]....... [8,8]....... (64 x 63 estados possveis) 2:
  • Slide 10
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Importncia de uma Formulao adequada do Problema Problema das 8 Rainhas - Formulao 2: estado inicial: nenhuma rainha no tabuleiro operadores: adicionar uma rainha a qualquer quadrado da coluna mais a esquerda que no contm nenhuma rainha teste do objetivo: 8 rainhas no tabuleiro sem ataque mtuo?.... E assim por diante, at 8 8 1,7 x 10 7 seqncias possveis a serem testadas [_,_] 0: [1,1] [2,1][3,1]....... [8,1] (8 estados possveis)1: [1,2] [2,2][3,2]....... [8,2] (8 x 8 estados possveis)2: 1,8 x 10 14 possibilidades da formulao 1 conhecimento
  • Slide 13
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em um Espao de Estados AradFagarasOradeaR.VilceaAradLugojAradOradea SibiuTimisoaraZenrid Arad Grafo do espao de estados do problema rvore de Busca A cada passo, a rvore de busca expandida a partir de sua fronteira, pelos operadores definidos na sua funo sucessora
  • Slide 14
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em um Espao de Estados AradFagarasOradeaR.VilceaAradLugojAradOradea SibiuTimisoaraZenrid Arad Grafo do espao de estados do problema rvore de Busca A cada passo, a rvore de busca expandida a partir de sua fronteira, pelos operadores definidos na sua funo sucessora fronteira
  • Slide 15
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em um Espao de Estados AradFagarasOradeaR.VilceaAradLugojAradOradea SibiuTimisoaraZenrid Arad Grafo do espao de estados do problema rvore de Busca A cada passo, a rvore de busca expandida a partir de sua fronteira, pelos operadores definidos na sua funo sucessora fronteira
  • Slide 16
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em um Espao de Estados AradFagarasOradeaR.VilceaAradLugojAradOradea SibiuTimisoaraZenrid Arad Grafo do espao de estados do problema rvore de Busca A cada passo, a rvore de busca expandida a partir de sua fronteira, pelos operadores definidos na sua funo sucessora fronteira
  • Slide 17
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Estratgias de Busca So definidas pela ordem de expanso de ns Avaliao de desempenho de uma estratgia dimenses: Completude: se sempre encontra uma soluo, se ela existe; Complexidade de Tempo: em funo do n de ns gerados/expandidos; Complexidade de Espao: em funo do n mximo de ns armazenados em memria; Otimizao: se sempre encontra a soluo de menor custo Complexidade de tempo e espao mensurada em termos de: b (branching) - fator mximo de ramificao da rvore de busca; d (depth) profundidade da soluo de menor custo; m profundidade mxima do espao de estados (que pode ser infinita)
  • Slide 18
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Estratgias de Busca Cega Busca em Largura (Breadth-first); Busca de Custo Uniforme; Busca em Profundidade (Depth-first); Busca em Profundidade Limitada (Depth-limited) Busca de Aprofundamento Iterativo (Iterative deepening) Busca Bidirecional
  • Slide 19
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em Largura (Breadth-first) Expande sempre o n menos profundo ainda no expandido; Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fim A BC EFDG Fronteira = (A) KMIOJLHN
  • Slide 20
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em Largura (Breadth-first) A BC EFDG Fronteira = (B,C) KMIOJLHN Expande sempre o n menos profundo ainda no expandido; Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fim
  • Slide 21
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em Largura (Breadth-first) A BC EFDG Fronteira = (C,D,E) KMIOJLHN Expande sempre o n menos profundo ainda no expandido; Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fim
  • Slide 22
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em Largura (Breadth-first) A BC EFDG Fronteira = (D,E,F,G) KMIOJLHN Expande sempre o n menos profundo ainda no expandido; Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fim
  • Slide 23
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em Largura (Breadth-first) A BC EFDG Fronteira = (E,F,G,H,I) KMIOJLHN Expande sempre o n menos profundo ainda no expandido; Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fim
  • Slide 24
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em Largura (Breadth-first) A BC EFDG Fronteira = (F,G,H,I,J,K) KMIOJLHN Expande sempre o n menos profundo ainda no expandido; Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fim
  • Slide 25
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em Largura (Breadth-first) A BC EFDG Fronteira = (G,H,I,J,K,L,M) KMIOJLHN Expande sempre o n menos profundo ainda no expandido; Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fim
  • Slide 26
  • 26/05/2003Disciplina: MCI-1 / Cin-UFPE Busca em Largura (Breadth-first) A BC EFDG Fronteira = (H,I,J,K,L,M,N,O) KMIOJLHN Expande sempre o n menos profundo ainda n