Transcript
Page 1: 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

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

Page 2: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Resolução de Problemas por Meio de Busca Cega no Espaço Extensional de Hipótese

Objetivo Geral do Seminário: Apresentar o método de busca cega como meio direto de

resolução de problemas genéricos. Objetivos Específicos:

Definir o que é um problema sob a ótica da agentes inteligentes Descrever a formulação de problemas e ilustrar com exemplos Apresentar busca como método genérico de resolução de

problemas Definir busca cega e ilustrar sua implementação Apresentar os diversos métodos de busca cega com análise

comparativa de desempenho Apresentar restrições do uso de busca com informação parcial

Page 3: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

O que é um problema? Qualquer situação a ser “resolvida” por uma seqüência ações a ser

executada, com vistas a atingir um objetivo; Na descrição acima:Situação = estado inicial;Seqüência de Ações = operações que irão gerar uma sucessão de estados;Objetivo = estado final (ou conjunto de) desejado;

Metáfora da resolução de problemas por meio de busca: Transformar um problema de raciocínio de um agente diretamente em um

problema de navegação num espaço de estados, no qual, a partir de um estado inicial, um agente pode buscar uma seqüência de ações que conduzem ao estados final desejado.

A solução de um problema é conjunto de seqüências de ações que levam de um estado inicial ao estado objetivado

Uma solução ótima é uma seqüência de ações que leva de um estado inicial ao estado objetivado com o menor custo*.

Page 4: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Romênia: ir de Arad a Bucharest

Page 5: 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

26/05/2003 Disciplina: 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 Inicial ex: “Estou em Arad” Função Sucessor S(x) = conjunto de pares ação-estado

ex: S(Arad) = { (Arad→Zerind, Zerind), (Arad→Sibiu, Sibiu), ......} Teste do Objetivo: condição que é capaz de determinar se o

estado final foi alcançado ex: “Estou em Bucareste?”

Custo (path cost) ex: soma de distancias, nº de ações executadas, etc.

Page 6: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

A Formulação do Problema define o Espaço de Estados possíveis

O Espaço de Estados É definido implicitamente pelo estado inicial juntamente com todos

os estados alcançáveis através da função sucessora S(x). Forma um grafo onde os nós representam estados e os arcos

entre os nós representam ações.Entretanto:

Estado Corresponde a uma

configuração do mundo.Ex: “estou em Bucareste”

Nó Estrutura de Informação que compõe

uma seqüência percorrida. Ex: Nó(“Bucareste”) (1)Antecessor = Nó(“Pitesti”)Path-cost = 418 Km

Nó(“Bucareste”) (2)Antecessor = Nó(“Fagarás”)Path-cost = 450 Km

Page 7: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

A Formulação do Problema exige Abstração do Mundo Real

O mundo real é absurdamente complexo: espaço de estados tem que ser abstraído para a resolução de problemas.

Estado (abstrato) = conjunto de estados reais

Ação (abstrata) = combinação complexa de ações reais, onde cada ação abstrata deveria ser “mais fácil” que o

problema original. Ex: “Arad→Zerind” representa um complexo de rotas possíveis,

paradas para descanso, etc.

Solução (abstrata) = conjunto de caminhos reais que são soluções no mundo real para o problema.

Page 8: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Importância de uma Formulação adequada do Problema

O Espaço de Estados derivado da formulação do problema impacta na eficiência de busca da solução

Ex: Problema das 8 Rainhas Dispor 8 rainhas num tabuleiro de xadrez, sem que qualquer

uma delas esteja “sob ataque” das demais: não pode haver mais de uma rainha em uma mesma linha, coluna ou diagonal somente o custo da busca conta (nº de passos para a solução)

Page 9: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Importância de uma Formulação adequada do Problema

Problema das 8 Rainhas - Formulação 1: estado inicial: nenhuma rainha no tabuleiro operadores: adicionar uma rainha a qualquer quadrado vazio teste do objetivo: 8 rainhas no tabuleiro sem ataque mútuo?

.... E assim por diante, até 64 x 63 x 62 x ..... x 57 1,8 x 1014 seqüências possíveis a serem testadas

[_,_]0:

[1,1] [1,2] [2,1]....... [1,8] [2,2] ....... [2,8] [8,1] [8,2] ....... [8,8].......

(64 estados possíveis)

1:

[1,2] [2,1]....... [1,8] [2,2] ....... [2,8] [8,1] [8,2] ....... [8,8].......

(64 x 63 estados possíveis)

2:

Page 10: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Importância de uma Formulação adequada do Problema

Problema das 8 Rainhas - Formulação 2: estado inicial: nenhuma rainha no tabuleiro operadores: adicionar uma rainha a qualquer quadrado da coluna mais a esquerda que

não contém nenhuma rainha teste do objetivo: 8 rainhas no tabuleiro sem ataque mútuo?

.... E assim por diante, até 88 1,7 x 107 seqüências possíveis a serem testadas

[_,_]0:

[1,1] [2,1] [3,1] ....... [8,1] (8 estados possíveis)1:

[1,2] [2,2] [3,2] ....... [8,2] (8 x 8 estados possíveis)2:

1,8 x 1014 possibilidadesda formulação 1

<<

Page 11: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Mais um exemplo...

Aspirador de pó estados = estado inicial = teste de término = operadores = custo da solução =

Page 12: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em um Espaço de Estados Uma vez o problema bem formulado... usa-se um método de

busca para encontrar o estado final desejado.

Métodos genéricos de busca: Busca exaustiva ou cega

Não sabe qual o melhor nó da fronteira a ser expandido = menor custo de caminho desse nó até um nó final (objetivo).

Busca heurística - informada Estima qual o melhor nó da fronteira a ser expandido com

base em funções heurísticas => conhecimento

Page 13: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em um Espaço de Estados

Arad Fagaras Oradea R.Vilcea Arad Lugoj Arad Oradea

Sibiu Timisoara Zenrid

Arad

Grafo do espaço 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 função sucessora

Page 14: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em um Espaço de Estados

Arad Fagaras Oradea R.Vilcea Arad Lugoj Arad Oradea

Sibiu Timisoara Zenrid

Arad

Grafo do espaço 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 função sucessora

fronteira

Page 15: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em um Espaço de Estados

Arad Fagaras Oradea R.Vilcea Arad Lugoj Arad Oradea

Sibiu Timisoara Zenrid

Arad

Grafo do espaço 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 função sucessora

fronteira

Page 16: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em um Espaço de Estados

Arad Fagaras Oradea R.Vilcea Arad Lugoj Arad Oradea

Sibiu Timisoara Zenrid

Arad

Grafo do espaço 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 função sucessora

fronteira

Page 17: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Estratégias de Busca São definidas pela ordem de expansão de nós

Avaliação de desempenho de uma estratégia – dimensões: Completude: se sempre encontra uma solução, se ela existe; Complexidade de Tempo: em função do nº de nós

gerados/expandidos; Complexidade de Espaço: em função do nº máximo de nós

armazenados em memória; Otimização: se sempre encontra a solução de menor custo

Complexidade de tempo e espaço é mensurada em termos de:b (branching) - fator máximo de ramificação da árvore de busca;d (depth) – profundidade da solução de menor custo;m – profundidade máxima do espaço de estados (que pode ser infinita)

Page 18: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Estratégias 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

Page 19: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Largura (Breadth-first)

Expande sempre o nó menos profundo ainda não expandido; Fronteira é uma fila do tipo FIFO, i.e., novos sucessores são

postos no fimA

B C

E FD G

Fronteira = (A)

K MI OJ LH N

Page 20: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Largura (Breadth-first)

A

B C

E FD G

Fronteira = (B,C)

K MI OJ LH N

Expande sempre o nó menos profundo ainda não expandido; Fronteira é uma fila do tipo FIFO, i.e., novos sucessores são

postos no fim

Page 21: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Largura (Breadth-first)

A

B C

E FD G

Fronteira = (C,D,E)

K MI OJ LH N

Expande sempre o nó menos profundo ainda não expandido; Fronteira é uma fila do tipo FIFO, i.e., novos sucessores são

postos no fim

Page 22: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Largura (Breadth-first)

A

B C

E FD G

Fronteira = (D,E,F,G)

K MI OJ LH N

Expande sempre o nó menos profundo ainda não expandido; Fronteira é uma fila do tipo FIFO, i.e., novos sucessores são

postos no fim

Page 23: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Largura (Breadth-first)

A

B C

E FD G

Fronteira = (E,F,G,H,I)

K MI OJ LH N

Expande sempre o nó menos profundo ainda não expandido; Fronteira é uma fila do tipo FIFO, i.e., novos sucessores são

postos no fim

Page 24: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Largura (Breadth-first)

A

B C

E FD G

Fronteira = (F,G,H,I,J,K)

K MI OJ LH N

Expande sempre o nó menos profundo ainda não expandido; Fronteira é uma fila do tipo FIFO, i.e., novos sucessores são

postos no fim

Page 25: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Largura (Breadth-first)

A

B C

E FD G

Fronteira = (G,H,I,J,K,L,M)

K MI OJ LH N

Expande sempre o nó menos profundo ainda não expandido; Fronteira é uma fila do tipo FIFO, i.e., novos sucessores são

postos no fim

Page 26: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Largura (Breadth-first)

A

B C

E FD G

Fronteira = (H,I,J,K,L,M,N,O)

K MI OJ LH N

Expande sempre o nó menos profundo ainda não expandido; Fronteira é uma fila do tipo FIFO, i.e., novos sucessores são

postos no fim

Page 27: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Completa?

Tempo?

Espaço?

Ótima?

Desempenho da Busca em Largura (Breadth-first)

Sim, desde que b (fator de ramificação) seja finito

1 + b + b2 + b3 + ... + bd + b(bd – 1) = O(bd+1), i.e., exponencial em d (fator de profundidade)

O(bd+1) (armazena cada nódulo na memória)

Em geral, não. Sim quando o custo é constante a cada passo

Espaço é o grande problema; pode facilmente gerar nódulos a 10MB/sec, o que em 24h chegaria a 860GB !!!!!

Page 28: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Expande sempre o próximo nó ainda não expandido que possui caminho de menor custo

• Fronteira = fila de nós ordenada pelo custo do caminho até cada nó

Busca de Custo Uniforme

A C E

B

D

Cidades:

1 10

515

5 5

A

B C D

1 5 15Fronteira = (B,C,D)

A

B C D

11

5 15

Fronteira = (C, EB ,D)

EB

A

B C D

11 10

15

Fronteira = (Ec, EB ,D)

EB Ec

A

Fronteira = (A)

Page 29: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

• Completa?

• Tempo?

• Espaço?

• Ótima?

Desempenho da Busca de Custo Uniforme

Sim, desde que o custo de cada nó 0

Nº de nós com custo(nó) < custo(solução ótima)

Sim, já q os nódulos expandem em ordem crescente de custo(nó)

Nº de nós com custo(nó) < custo(solução ótima)

Se o custo dos nós de um mesmo nível for igual, o desempenho é equivalente ao da Busca em Largura

Page 30: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Profundidade (Depth-first)

Expande sempre o nó mais profundo ainda não expandido; Fronteira é uma fila do tipo LIFO, i.e., novos sucessores são postos no

início

A

B C

E FD G

J LH NK MI O

Fronteira = (A)

Page 31: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Profundidade (Depth-first)

A

B C

E FD G

J LH NK MI O

Fronteira = (B,C)

Expande sempre o nó mais profundo ainda não expandido; Fronteira é uma fila do tipo LIFO, i.e., novos sucessores são postos no

início

Page 32: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Profundidade (Depth-first)

A

B C

E FD G

J LH NK MI O

Fronteira = (D,E,C)

Expande sempre o nó mais profundo ainda não expandido; Fronteira é uma fila do tipo LIFO, i.e., novos sucessores são postos no

início

Page 33: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Profundidade (Depth-first)

A

B C

E FD G

J LH NK MI O

Fronteira = (H,I,E,C)

Expande sempre o nó mais profundo ainda não expandido; Fronteira é uma fila do tipo LIFO, i.e., novos sucessores são postos no

início

Page 34: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Profundidade (Depth-first)

A

B C

E FD G

J LH NK MI O

Fronteira = (I,E,C)

Expande sempre o nó mais profundo ainda não expandido; Fronteira é uma fila do tipo LIFO, i.e., novos sucessores são postos no

início

Page 35: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Profundidade (Depth-first)

A

B C

E FD G

J LH NK MI O

Fronteira = (E,C)

Expande sempre o nó mais profundo ainda não expandido; Fronteira é uma fila do tipo LIFO, i.e., novos sucessores são postos no

início

Page 36: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Profundidade (Depth-first)

A

B C

E FD G

J LH NK MI O

Fronteira = (J,K,C)

Expande sempre o nó mais profundo ainda não expandido; Fronteira é uma fila do tipo LIFO, i.e., novos sucessores são postos no

início

Page 37: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Profundidade (Depth-first)

A

B C

E FD G

J LH NK MI O

Fronteira = (K,C)

Expande sempre o nó mais profundo ainda não expandido; Fronteira é uma fila do tipo LIFO, i.e., novos sucessores são postos no

início

Page 38: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca em Profundidade (Depth-first)

A

B C

E FD G

J LH NK MI O

Fronteira = (C)

Expande sempre o nó mais profundo ainda não expandido; Fronteira é uma fila do tipo LIFO, i.e., novos sucessores são postos no

início

Page 39: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Completa?

Tempo?

Espaço?

Ótima?

Desempenho da Busca em Profundidade (Depth-first)

Não: falha em árvores de profundidade infinita. Nesse caso, pode-se arbitrar um limite de profundidade L: Depth-limited search

O(bm): muito ruim se m >> d (m profundidade máxima, d profundidade da solução)

O(b.m), i.e., função de crescimento linear

Não: deve ser evitada em árvores muito profundas ou profundidade infinita

Page 40: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca de Aprofundamento Iterativo

Variação da Busca em Profundidade, que utiliza um limite de profundidade L, que inicia em 0 e vai sendo incrementado de 1, a cada iteração.

A

A

B C

A

B C

D E D E

A

B C

D E

A

B C

D E D E

AL = 0

AL = 1 A

B C

A

B C

AL = 2 A

B C

A

B C

D E

A

B C

D E

A

B C

D E D E

Page 41: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Completa?

Tempo?

Espaço?

Ótima?

Desempenho da Busca por Aprofundamento Iterativo

Sim, desde que b (fator de ramificação) seja finito

O(bd) (b fator de ramificação, d profundidade do nó objetivado)

O(b.d) (b fator de ramificação, d profundidade do nó objetivado)

Em geral, não. Sim quando o custo é constante a cada passo

Em geral, é o método de Busca Cega preferido para grandes espaçosde busca e quando a profundidade da solução é desconhecida

Page 42: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca Bidirecional Princípio básico - dois agentes de busca agindo em paralelo,

onde a cada expansão de nós verifica-se a existência de interseção entre as respectivas fronteiras de suas árvores de busca.

A B

Page 43: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Busca Bidirecional Motivação: (bd/2 + bd/2) << bd

A B

Page 44: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Motivação: (bd/2 + bd/2) << bd

Busca Bidirecional

A B

Infelizmente, nem sempre é aplicável!

Page 45: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Análise Comparativa das Estratégias de Busca Cega

Critério Largura CustoUniforme

Profun-Didade

Aprofund.Iterativo

Bidirecional(se aplicável)

Completa? Sim* Sim* Não Sim* Sim*

Tempo bd+1 bd* bm bd bd/2

Espaço bd+1 bd* b.m b.d bd/2

Ótima? Sim* Sim Não Sim* Sim*

Page 46: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Repetição de Estados na Busca

A

B

C

D

Soluções possíveis (Custo x Eficácia)1. Não retornar ao estado “pai”2. Não retornar a um ancestral3. Não gerar qualquer estado que já

tenha sido criado antes (em qualquer ramo)

requer que todos os estados gerados permaneçam na memória: custo O(bd)

pode ser implementado mais eficientemente com hash tables

quando encontra nó igual tem de escolher o melhor (menor custo de caminho até então)

A

B B

C CC C

Page 47: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Problemas com informação Parcial

Sensorless or conformant problem (ambiente inacessíveis) Agente não sabe seu estado inicial (percepção deficiente) Deve raciocinar sobre os conjuntos de estados Solução: seqüência de ações (via busca)

Problema de contingência Efeito das ações não-determinístico e/ou mundo parcialmente

observável => novas percepções depois de ação ex. aspirador que suja ao sugar e/ou só percebe sujeira localmente

Solução: árvore de decisão (via planejamento, agente deliberativo) Problema exploratório (on-line)

Espaço de estados desconhecido ex. dirigir sem mapa

Solução.... via aprendizagem por reforço (agente indutivo situado)

Page 48: 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

26/05/2003 Disciplina: MCI-1 / Cin-UFPE

Problemas com informação Parcial

Estado simples Início: 5 Solução: [dir, suga]

Conformant problem Início: {1,2,3,4,5,6,7,8} Dica: direita => {2,4,6,8} Solução: [dir, suga, esq, suga]

Problema de contingência Início: [lado esq, sujo] = {1,3} Solução? Sugar => {5,7}, Dir =>

{6,8}, Sugar no 6 => 8 mas sugar no 8 => 6

Solução: [sugar, dir, se sujo sugar] Solução geral: [dir, se sujo suga, esq,

se sujo suga] Problema exploratório

....


Recommended