BCC740 Inteligencia Artficial - Questionario 2

Prévia do material em texto

BCC740 – IA em Controle e Automação 
Prof. Álvaro Guarda
Mariana de Souza Sanchez
LISTA DE EXERCÍCIOS (Primeira Prova)
Resolução de Problemas
O que são métodos genéricos de resolução de problemas?
	
	A resolução de problemas consiste no uso de métodos genéricos de uma forma ordenada, para encontrar soluções de problemas específicos. Algumas técnicas para resolução de problemas desenvolvidas e utilizadas na inteligência artificial, ciência da computação, engenharia, matemática, medicina etc. estão relacionadas com processos mentais de resolução de problemas estudados no campo da psicologia.
Compare os métodos genéricos de resolução de problemas com os sistemas baseado em conhecimento.
Tudo o que se sabe sobre o sistema deve ser explicitamente representado no Sistema Baseado em Conhecimento.
Deve ser usada por um agente capaz de interpretá-la (mecanismo de inferência)
Os problemas resolvidos são aqueles sobre os quais não é conhecido um procedimento determinístico que garanta uma resolução efetiva (limitações de tempo e recurso)
Um SBC usa conhecimento específico do domínio para contornar:
	Sistemas Convencionais 
	Sistemas Baseados em Conhecimento
	Estrutura de Dados 
	Representação de Conhecimento
	Dados e relações entre dados
	Conceitos, relação entre conceitos e regras
	Tipicamente usam algoritmos determinísticos
	Busca heurística
	Conhecimento embutido no código do programa
	Conhecimento representado explicitamente e separado do programa que o manipula e interpreta
	Explicação do raciocínio é difícil
	Podem e devem explicar seu raciocínio
Compare “busca em espaço de estados” e “busca por redução de problemas”.
	Algoritmos de Busca são técnicas de Inteligência Artificial aplicadas a problemas de alta complexidade teórica que não são resolvidos com técnicas de programação convencionais, principalmente as de natureza puramente numérica.
	Busca de uma solução é feita através da procura de um caminho no espaço de estados que leva do estado inicial para o estado final. Os métodos cegos fazem uma pesquisa sistemática do espaço de estados, porém não utilizam nenhum conhecimento para guiar a busca. Os dois principais métodos cegos são a “busca em profundidade” e a “busca em extensão”.
	A ação de percorrer o espaço de estados é feita de acordo com uma estratégia de controle que seleciona um estado e um operador que será aplicado ao estado para gerar os estados subseqüentes. A aplicação dos operadores nos estados iniciais e intermediários é feita até que se chegue a um estado objetivo. Este processo, à medida que vai sendo executado, vai gerando a árvore de busca.
Como um problema é representado como sendo uma “busca em espaço de estados”?
	Busca no espaço de estados é uma das tecnicas mais utilizadas para resolução de
problemas em Inteligencia Artificial. A ideia consiste em supor a existencia de um agente capaz de executar ações que modificam o estado corrente de seu mundo. 
	Assim, dados um estado inicial representando a configuração corrente do mundo do agente, um conjunto de ações que o agente é capaz de executar e uma descrição do estado meta que se deseja atingir, a solução do problema consiste numa sequencia de ações que, quando executada pelo agente, transforma o estado inicial num estado meta.
O que é uma solução em “busca em espaço de estados”?
	Encontrar uma solução equivale a achar um caminho no espaço de estados que, partindo do estado inicial, chega ao estado final. A interpretação da solução no problema do mundo dos blocos é uma seqüência de movimentos de blocos, ou seja, um plano para re-arranjar a pilha de blocos de acordo com a definição do problema.
Como um problema é representado como sendo uma “busca por redução de problemas”?
	O espaço de busca é representado graficamente por um grafo E/OU. Neste grafo, os nodos contêm a descrição dos problemas (subproblemas) e os arcos indicam relações entre os problemas, isto é, como os problemas são decompostos. As folhas da árvore podem ser problemas primitivos ou nodos terminais (problemas insolúveis). Os nodos intermediários, sucessores de um determinado nodo, são do tipo OU, indicando que os nodos sucessores são problemas alternativos, ou do tipo E, indicando que os nodos sucessores são problemas conjuntivos.
	A busca é a construção sistemática do grafo E/OU através da aplicação das operações que vão decompondo os problemas.
O que é uma solução em “busca por redução de problemas”?
Na resolução de problemas utilizando como enfoque a busca por redução de problemas, a idéia utilizada é a da decomposição de problemas em subproblemas com complexidade menor que a do problema original. A modelagem do problema é feita através da definição dos seguintes elementos:
· Descrição do problema inicial.
· Conjunto de operações de transformação de problemas.
· Conjunto de problemas primitivos (problemas que têm solução imediata, conhecida). 
A solução é um conjunto de Problemas Primitivos encontrados a partir da aplicação das operações no problema inicial e nos subproblemas já gerados.
Represente o problema “Torres de Hanoi” como sendo uma busca em espaço de estados. 
Represente o problema “Torres de Hanoi” como sendo uma busca por redução de problemas.
Quais são os principais métodos cegos de busca? Porque são chamados “métodos cegos”?
Busca às cegas - (Blind Search ou Uniformed Search Uniformed Search)
Uma estratégia de busca é dita "CEGA" se ela não leva em conta informações específicas sobre o problema a ser resolvido.
Existem basicamente duas estratégias cegas para a construção e pesquisa em uma árvore de busca: Busca em Largura e Busca em Profundidade.
Compare a busca em profundidade e em extensão.
Pesquisa em largura
Consiste em construir uma árvore de estados a partir do estado inicial, aplicando a cada momento, todas as regras possíveis aos estados do nível mais baixo, gerando todos os estados sucessores de cada um destes estados. Assim, cada nível da árvore é completamente construído antes que qualquer nodo do próximo nível seja adicionado à árvore.
Estratégia: Todos os nós de menor profundidade são expandidos primeiro
Pesquisa muito sistemática
Normalmente demora muito tempo e sobretudo ocupa muito espaço
A principal vantagem do algoritmo de busca em largura é que este encontra o MENOR caminho do nodo inicial até o nodo final mais próximo.
	
Pesquisa em profundidade
Procurar explorar completamente cada ramo da árvore antes de tentar o ramo vizinho.
Estratégia: Expandir sempre um dos nós mais profundos da árvore
Necessita pouca memória; bom para problemas com muitas soluções
Não pode ser usada para árvores com profundidade infinita, pode ficar presa em ramos errados.
Em alguns casos, é definida uma profundidade limite a qual transforma-se em Pesquisa com Profundidade Limitada
O algoritmo de busca em profundidade não encontra necessariamente a solução mais próxima, mas pode ser MAIS EFICIENTE se o problema possui um grade número de soluções ou se a maioria dos caminhos pode levar a uma solução.
Dê um exemplo de problema em que a “busca em extensão” funcionaria melhor que a “busca em profundidade”. Dê um exemplo de problema em que a “busca em profundidade” funcionaria melhor que a “busca em extensão”. Justifique os exemplos.
Escreva sobre busca heurística (definição, tipos de heurística, métodos, etc.).
	Os métodos de busca vistos anteriormente fornecem uma solução para o problema de achar um caminho até um nó meta. Em muitos casos, a utilização destes métodos é impraticável devido ao número muito elevado de nós a expandir antes de achar uma solução.
	Como existem limites práticos de valores de tempo e espaço de armazenamento disponível para uso na busca, devemos procurar métodos alternativos mais eficientes.
	Qualquer técnica usada para melhorar a busca depende de informações especiais acerca do problema em questão. Chamamos a este tipo de informação de Informação Heurística e os procedimentos de busca que a utilizam de Mëtodos de Busca Heurística.A informação que pode compor uma informação heurística é o Custo do Caminho. O CUSTO DO CAMINHO pode ser composto pelo somatório de dois outros custos: O custo do caminho do estado inicial até o estado atual que está sendo expandido; e uma estimativa do custo do caminho do estado atual até o estado meta. Uma boa heurística para a estratégia de busca no estado de espaços de um problema é a estratégia conhecida como Subida da Encosta, também denominada "subida da montanha" ou "hill climbing".
Seja a modelagem utilizando “busca em espaço de estados” de um problema qualquer: 
Estado Inicial: a		Estado Final: z
	Operações de transformação de estado:
Sintaxe: s( <nodo>, <nodo sucessor>, <custo>) 
onde <custo> é o custo da aplicação da 
operação 
s(a,b,3).
s(a,c,3).
s(a,d,4).
s(b,e,1).
s(b,f,3).
s(c,g,1).
s(c,h,1).
s(d,h,3).
s(e,z,1).
s(f,i,1).
s(g,z,1).
	Função heurística (função de custo): 
 f(x) = g(x) + h(x) 
 g(x) é o somatório dos valores <custo>, 
 relativos à aplicação das operações para ir 
 do estado inicial até o estado x.
 h(x) é definido como abaixo
h(b,8).
h(c,9).
h(d,3).
h(e,10).
h(f,7).
h(g,8).
h(h,2).
h(i,4).
Apresente uma árvore de busca completa para o problema.
Mostre uma tentativa de solução utilizando o método "pesquisa em profundidade com retrocesso", apresentando a árvore de busca parcial gerada na tentativa, com os nodos numerados na ordem em que são visitados.
Mostre uma tentativa de solução utilizando o método "pesquisa em extensão", apresentando a árvore de busca parcial gerada na tentativa, com os nodos numerados na ordem em que são visitados.
Mostre uma tentativa de solução utilizando o método "pesquisa pela melhor escolha", apresentando a árvore de busca parcial gerada na tentativa, com os nodos numerados na ordem em que são selecionados para expansão. Apresente os cálculos.
Mostre qual é a solução encontrada nos itens II, III e IV.
Escreva sobre “subida de encosta”.
	É a estratégia mais simples e popular. Baseada na Busca em Profundidade. É um método de busca local que usa a idéia de que o objetivo deve ser atingido com o menor número de passos.
	A idéia heurística que lhe dá suporte é a de que o número de passos para atingir um objetivo é inversamente proporcional ao tamanho destes passos.
	Há duas variações do método: a Subida de Encosta SIMPLES e a Subida de Encosta PELA TRILHA MAIS ÍNGREME.
Subida de encosta simples: vai examinando os sucessores do estado atual e segue para o primeiro estado que for maior que o atual.
Subida de encosta pela trilha mais íngreme: Examina todos os sucessores do estado atual e escolhe entre estes sucessores qual é o que está mais próximo da solução.
Escreva sobre “têmpera simulada”.
	Método de busca inspirado no processo de temperar metais: inicia com uma temperatura elevada, permitindo transições de alto nível de energia, depois, gradualmente, a temperatura é resfriada até alcançar um estado sólido, onde apenas transições de baixo nível de energia são permitidas. O objetivo é alcançar uma estrutura molecular com um mínimo de energia.
Escreva sobre “algoritmo genético”.
Compare os últimos 4 métodos.
Compare em termos de pesquisa no espaço de soluções os métodos “subida de encosta”, “têmpera simulada” e “algoritmo genético”.