Módulo III - Espaço de Estados

Prévia do material em texto

29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 1/2
Espaço de Estados ­ Definição
A resolução de problemas inicia em construir e pesquisar o Espaço de estados do problema;
ES é uma forma de representar conhecimento sob um domínio específico de problemas;
ES: é o conjunto de todos os estados pesquisados a partir de um estado inicial.
ES forma um grafo onde os nós são estados e os arcos entre os nós são ações (Executando as ações, há transição de um estado para o outro);
O caminho (path) do espaço de estados é a sequencia de estados que são conectados por uma sequencia de ações.
Exemplo: Espaço de estados por meio de grafos
A figura abaixo demonstra um grafo acerca de um dominio específico de conhecimento. A partir desta, é possivel construir uma uma representação deste conhecimento.
 
Mapa Simplificado das rodovias da Romenia
Fonte: RUSSEL Stuart; NORVING Peter. Artifical Intelligence: A modern   Approach. 2.Edition. New Jersey: Prentice Hall, 2003. Pg. 63.
 Abaixo é possivel observar uma represerntação do conhecimento do problema acima. A representação do conhecimento deve ser expressiva para facilitar seu uso em uma
codificação (através de uma linguagem de programação: Prolog, List, Java, C++ ou outras).
 
 
 
 
(oradea,zerind),(oradea,siniu), (siniu,fagaras), (fagaras,bucharest)
(zerind,oradea), (siniu,oradea), (zerind,arad), (arad,sibiu), (arad,timissoara), (timissoara,lugoj), (lugoj,mehadia)
(drobeta,craiova), (craiova,rimnicu_Vilcea), (craiova,pitesti), (pitesti,bucahrest)
(bucharest,giurgiu), (bucharest,urziceni), (urziceni,hirsova), (urziceni,vaslui)
(hirsova,eferie), (vaslui,iasi), (iasi,neamt), (rimnicu_Vilcea,pitesti)
 Resolução de Problemas 
Resolução de problemas (problem­solving) pode ser construido por agentes de software a partir de uma descrição formar de problemas que decidem o que fazer para encontrar uma
sequencia de ações baseadas em técnicas de buscas que leva de um estado inicial aos estados objetivos em um Espaço de estados;
Resolução de Problemas = Descrição formal do problema + Escolha da Estratégia de busca (ou politica de busca);
Ex: Um agente de resolução de problemas possui como espaço de estados o mapa da Romenia, conforme visto no conteudo anterior. Assim, o agente pode ir de ARAD até
BUSCHAREST analisando diferentes sequencias possiveis de ações que leva para os estados de valores conhecimentos, com o intuito de escolher a melhor sequencia, ou seja,
realiza uma pesquisa (ou busca) no espaço de estados.
Um algoritmo de pesquisa em um Espaço de estados captura um problema como uma entrada e retorno a solução na forma de uma sequencia de ações.
Para resolver problemas com o uso de espaço de estados é preciso definir buscas em uma Árvore Binária de Pesquisa (Binary Search Tree);
Pesquisa (Busca) no Espaço de Estados
Busca é um mecanismo geral de pesquisa em árvore;
Uma busca inicia­se na escolha de um estado inicial. Após aplica uma sequencia de ações com o intuito de se construir um ramo na árvore que conduz a um estado objetivo;
Existe diversas buscas no espaço de estados, mas as buscas classicas são: Largura (Breadth­First Search) e a Profundidade (Depth­First Search);
Profundidade e Largura são conhecidas como buscas cegas, pois não são guiadas por conhecimento.
 
 
 
 
 
 
 
 
 
 
 
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 2/2
 
 
Exercício 1:
Espaço de estados pode representar as "regras do jogo" para um dado problema. Porém sua representação pode mudar sendo dependente de:
A ­ Uma linguagem de programação 
B ­ Um Interface gráfica 
C ­ Regras de um banco de dados 
D ­ Lógicas para a resolução de problemas formais 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 2:
Tendo como base o grafo abaixo, como poderia ser a representação do conhecimento indo de ARAD (é o estado inicial) para ORADEA (estado objetivo), levando em
consideração a informação: kilometragem?
Mapa Simplificado das rodovias da Romenia
Fonte: RUSSEL Stuart; NORVING Peter. Artifical Intelligence: A modern   Approach. 2.Edition. New Jersey: Prentice Hall, 2003. Pg. 63.
 
A ­ (arad, zerind, 146) (zerind, arad, 146) 
B ­ (zerind, zerind, 71) (arad, zerind, 75) 
C ­ (arad, zerind) (zerind, arad) 
D ­ (arad, zerind, 71) (zerind, arad, 75) 
E ­ (arad, zerind, 75) (zerind, arad, 71) 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 3:
A representação do conhecimento por espaço de estados é um modelo que pode ser implementado por uma estrutura de dados. Escolha a alternativa correta para informar
qual estrutura de dados utilizada.
A ­ Tabela Hash 
B ­ Árvore Binária 
C ­ Pilha e Fila 
D ­ Orientação a Objetos 
E ­ NDA 
Comentários:
Essa disciplina não é ED ou você não fez comentários