lista 4 - exercício de IA - Buscas

Prévia do material em texto

Universidade Federal do Pará
Instituto de Ciências Exatas e Naturais
Faculdade de Computação
Disciplina: Inteligência Artificial
Professor: Reginaldo Santos
1. Considere a árvore a seguir e responda as seguintes questões:
a) Qual a ordem de visita caso seja aplicado a busca em largura?
b) Qual a ordem de visita caso seja aplicado a busca em profundidade?
Obs.: Começar a busca pelo vértice C.
2. Considere o grafo abaixo e faça o que se pede.
a) Aplique a BUSCA-EM-GRAFO (consultar slides da aula sobre agentes de resolução de
problemas) e encontre a sequência de ações que deve ser executada para sair do estado
inicial Marambaia e alcançar o objetivo objetivo Guamá. Use a ordem alfabética para
selecionar os bairros que estão na borda. Ex.: Expandir(Marambaia) = {Castanheira,
Sacramenta, Telégrafo}. Nesse caso, o bairro Castanheira seria selecionado.
b) Aplique a busca de custo uniforme saindo do bairro da Marambaia e chegando ao bairro
do Guamá. Qual o caminho e o custo total encontrados?
c) Faça uma análise sobre as diferenças encontradas nas sequências de ações e custos totais
entre os itens a e b. Quais são os principais fatores que causaram as disparidades nos
resultados encontrado?
Universidade Federal do Pará
Instituto de Ciências Exatas e Naturais
Faculdade de Computação
Disciplina: Inteligência Artificial
Professor: Reginaldo Santos
3. O problema de missionários e canibais é normalmente enunciado como a seguir. Três
missionários e três canibais estão em um lado de um rio, juntamente com um barco que pode
levar uma ou duas pessoas por vez. Descubra um meio de fazer todos atravessarem o rio
sem deixar que um grupo de missionários de um lado fique em número menor que o número
de canibais nesse mesmo lado do rio. Esse problema é famoso em IA porque foi assunto do
primeiro artigo que abordou a formulação de problemas a partir de um ponto de vista
analítico (Amarel, 1968).
a) Formule o problema precisamente, fazendo apenas as especificações necessárias para
assegurar uma solução válida.
b) Assuma o estado inicial: os três missionários e os três canibais estão do mesmo lado do
rio. De acordo com o seu custo de caminho (definido no item anterior), encontre uma
sequência de ações que resolva o problema e apresente o custo total do caminho
encontrado. 
Universidade Federal do Pará
Instituto de Ciências Exatas e Naturais
Faculdade de Computação
Disciplina: Inteligência Artificial
Professor: Reginaldo Santos
c) Por que você imagina que as pessoas têm dificuldades para resolver esse quebra-cabeça,
considerando que o espaço de estados é tão simples?
4. Considere o seguinte grafo “dirigido” (mapa). O nó A representa o estado inicial e o nó G
representa o objetivo a ser alcançado. As ações permitidas são representadas pelos arcos de
cada nó (por exemplo, do nó C só é possível ir para os nós B, D e E). O custo do caminho
de um nó para outro está indicado pelo número associado a cada arco (por exemplo, o custo
de ir de B para D é 38). O custo estimado (função heurística) de cada nó em relação ao nó
objetivo está indicado pelo número dentro de cada círculo representando o nó (por exemplo,
o custo estimado de sair de B para chegar em G é de 26). Aplique cada um dos algoritmos de
busca seguintes e apresente a ordem com que os vértices foram visitados.
a) Busca de custo uniforme (apenas g)
b) Busca gulosa (apenas h)
c) A* (g + h)