Espaço de Estados

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Espaço de Estados
Prof. Pedro Luiz Santos Serra
1
Pauta
Definição
Representação
Denotação (Semântica)
Computação
Sintaxe e Semântica
Notação
Busca de Espaço de Estados
Grafo
Exemplos Didáticos e Aplicados
Exercícios
2
Prof. Pedro Luiz Santos Serra
2
Definição
Expressões bem formadas empregando cálculo de predicados permite
Um meio de descrever objetos e relações em um domínio de problema
O estabelecimento de regras de inferência
Inferir conhecimento baseado nessas definições
3
Prof. Pedro Luiz Santos Serra
3
Definição
O projeto e implementação de algoritmos de busca (sistemas especialistas) requer um profundo conhecimento de seu comportamento. Questões devem ser respondidas incluem:
Será encontrada uma solução?
O sistema sempre terminará sua execução? (Loop infinito ?)
Nomes de recursos/produtos?
Ao encontrar uma solução, ela será ótima ?
Qual é a complexidade do processo em termos de tempo e memória ?
Como pode o interpretador reduzir eficientemente a complexidade de busca ?
Como pode-se um interpretador ser projetado para utilizar com eficiência uma linguagem representativa ?
A teoria de busca com Espaço de Estados é nossa ferramenta primária para responder estas questões.
4
Prof. Pedro Luiz Santos Serra
4
Um mapa de estrada, um modelo de desenho de computador de um produto, o layout de um sistema digital são exemplos de descrições de objetos empregando diferentes representações.
As convenções utilizadas para construção e interpretações de mapas de estradas constituem uma representação.
Prof. Pedro Luiz Santos Serra
5
Representação
A representação envolve três componentes que têm relações particulares uns com os outros. Este relacionamento pode ser expresso:
Representação = notação + denotação + computação.
Prof. Pedro Luiz Santos Serra
6
Sintaxe e Semântica
Convenções de notação apropriadas para descrever as idéias ou realidade percebida
Estas convenções são chamadas de sintaxe com relação à certa representação
A sintaxe:
Especifica os objetos do discurso e uma linguagem para relacioná-las uns com os outros.
Definição: parte da gramática que estuda a disposição das palavras na frase e a das frases no discurso, bem como a relação lógica das frases entre sí (Aurélio).
Prof. Pedro Luiz Santos Serra
7
Notação (Sintaxe)
Termo usado para convenções.
Em um mapa, a denotação corresponde à interpretação das marcações de cidades e estradas.
Definição: estudo das mudanças ou translações sofridas, no tempo e no espaço, pela significação das palavras (Aurélio).
Prof. Pedro Luiz Santos Serra
8
Denotação (Semântica)
Um modelo computacional especifíca as relações e manipulações entre objetos conforme as convenções semânticas.
Prof. Pedro Luiz Santos Serra
9
Computação
Representação de Euler (grafos)
A teoria dos grafos é uma importante ferramenta para representação do Espaço de Estados e a relação, fiel, entre seus elementos.
 Problema das pontes de Königsberg (Euler).
10
Prof. Pedro Luiz Santos Serra
10
Definição
O problema consiste:
Obtenção de um único caminho sem repetição em que uma pessoa passe por todas as ilhas e margens.
11
Prof. Pedro Luiz Santos Serra
connect(i1,i2,b1)	connect(i2,i1,b1)
connect(rb1,i1,b2)	connect(i1,rb1,b2)
connect(i1,i2,b1)	connect(i2,i1,b1)
connect(i1,i2,b1)	connect(i2,i1,b1)
connect(i1,i2,b1)	connect(i2,i1,b1)
connect(i1,i2,b1)	connect(i2,i1,b1)
connect(i1,i2,b1)	connect(i2,i1,b1)
11
Prof. Pedro Luiz Santos Serra
12
Representação da Árvore de Possibilidades
Suponha que um homem de vendas tenha que visitar cinco cidades e depois voltar para casa.
A meta do problema é encontrar o caminho mais curto para a viajem, visitando cada cidade e depois retornando a cidade inicial.
Os nós são as cidades.
Os arcos são marcados com pesos que representam o custo de viajar por aquele arco. Este custo é uma representação da distância necessária de viajem de carro.
Consideremos que o homem de vendas viva na cidade A e tenha que retornar alí.
Prof. Pedro Luiz Santos Serra
13
Problema do homem de vendas
Prof. Pedro Luiz Santos Serra
14
Problema do Homem de Vendas
Grafo:
Conjunto de nós
Conjunto de arcos ou ligações entre pares de nós
No modelo de espaço de estados, os nós representam estados na resolução do problema
Arcos representam transições entre os estados
Inferências lógicas
Movimentos legais em um jogo
Regras em aplicação podem ser representadas por arcos (“se ... então ... “)
Prof. Pedro Luiz Santos Serra
15
Busca de espaço de Estados
Exemplos
16
Prof. Pedro Luiz Santos Serra
16
Exemplos
17
Prof. Pedro Luiz Santos Serra
17
Prof. Pedro Luiz Santos Serra
18
Exemplos
Prof. Pedro Luiz Santos Serra
19
Prof. Pedro Luiz Santos Serra
20
Formulação de um Problema