Inteligência Artificial.

Inteligência Artificial - Ciência da Computação - 4º/5º
Semestre
3ª Lista de Exercícios – Profa. Renata
Data da Entrega: 20/05/2014
1 – Refaça os exemplos vistos em sala para os algoritmos de busca A*
Iterativa (IDA*) e Melhor Primeiro Recursiva (RBFS).
2 - Explique a técnica Busca Subida da Encosta (Hill-Climbing). Quais são suas limitações?
3 - Dentre as propriedades da Busca Subida da Encosta assinale
Verdadeiro(V) ou Falso (F):
a) Busca local que só faz modificações que melhoram o estado atual. ( )
b) Não fica presa em Máximos Locais, Platôs e Arestas. ( )
c) Termina quando um pico é atingido (mesmo que não seja o máximo). ( )
d) Não olha à frente dos vizinhos imediatos do estado atual. ( )
e) Escolhe entre o conjunto de melhores sucessores se houver mais do que um. ( )
f) Escolhe aleatoriamente entre o conjunto de melhores sucessores se houver mais do que um. ( )
g) Seu sucesso depende muito do formato da superfície do espaço de estados -- com poucos máximos locais, o reinício aleatório encontra uma boa solução rapidamente. ()
4 – A figura a seguir representa uma árvore de jogadas possíveis de um jogo com dois jogadores, com o resultado da função de avaliação para os nósfolha apresentado entre parênteses. Considerando que a jogada inicial é de maximização, qual seria a jogada escolhida por um algoritmo MINIMAX?
Justifique colocando os valores para os níveis mais altos.

5 - O Problema do Caixeiro Viajante (PCV) é um problema que tenta determinar a menor rota para visitar n cidades (visitando cada uma pelo menos uma vez), retornando à cidade de origem. É um problema de otimização NP-Completo inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os gastos com transporte e/ou combustível. Considere um problema com 5 cidades, conforme se verifica na Figura:

Encontre uma solução para esse problema, utilizando