Exercicio 2 Inteligencia Artificial

Questões:
1) Defina formalmente um problema, exemplificando o mesmo (não use o problema de diagnóstico).
Um problema é um objeto matemático P={D,R,q}, consistindo de dois conjuntos não vazios, D os dados e R os resultados possíveis, e de uma relação binária q que caracteriza uma solução satisfatória, associando a cada elemento do conjunto de dados a solução desejada.
Tomando como exemplo o problema do caixeiro viajante:
Conjunto D: Cidades e distancia entre elas
Conjunto R: Caminhos que passam por todas as cidades apenas uma vez
Solução satisfatória: Caminho que leva à menor soma de distancia percorrida.

2) Como se deve definir um problema como uma busca em espaço de estados?
É necessário definir o estado inicial; a função sucessor, ou ações que o agente pode executar; o teste de objetivo, para saber se o estado atual é o objetivo; e função de custo de caminho.

3) Explique as seguintes técnicas de busca:
a. Busca em Largura.
A busca em largura percorre a arvore “de cima para baixo”. O nó raiz é expandido primeiro, em seguida, todos os sucessores do nó raiz são expandidos, Depois os sucessores desses nós e assim por diante, e são verificados da esquerda para a direita.

b. Busca em Profundidade.
Explora cada caminho possível a partir do nó corrente antes de tentar outro caminho. Neste tipo de busca você vai pela esquerda até alcançar um nó terminal ou achar o objetivo;
Se alcançar um nó terminal, então você retrocede um nível, pega o caminho à direita e avança pela esquerda até achar um nó terminal ou um objetivo. Esse processo é repetido até achar o objetivo ou for atingido o último nó no espaço de solução.

4) Apresente uma árvore (espaço) de estados para o problema “Missionários e Canibais” até 4 níveis.

5) Mostre uma tentativa de solução para o problema dos Missionários e Canibais utilizando busca em largura.

6) Conceitue heurística.
Heurística é uma técnica que aumenta a eficiência do processo de busca, geralmente em detrimento da exploração de todas