Inteligencia artificial unip

1. Busca não informada
Exercício 1.1
Considere o seguinte espaço de estados em que o estado inicial é o nó A e os estados finais são os nós F, I e J:
A
4
1
2 2
3
2
B C D
E F G
I
H
J
3
3 1
1
Admitindo que em caso de empate os sucessores são expandidos por ordem alfabética, desenhe a árvore gerada e descreva a ordem de expansão de uma busca com uma estratégia:
1. de profundidade,
2. de largura,
3. de custo uniforme (o custo de transição é o inteiro que está representado ao lado dos arcos),
4. de profundidade limitada com limite=3,
5. de profundidade iterativa.
Exercício 1.2
Um vendedor quer visitar as cidades do mapa sem passar duas vezes pela mesma cidade (e sem voltar à cidade de origem).
Lisboa
Faro
Porto VilaReal
Viseu
200
300
750
350
200
150
150
A cidade de partida é Lisboa. Em caso de empate entre dois nós escolha o nó por ordem alfabética.
1. Escolha uma formulação adequada para o problema.
2. Desenhe a árvore de busca gerada e detalhe a ordem de expansão de uma busca com uma estratégia:
(a) de profundidade,
(b) de largura,
(c) de custo uniforme,
(d) de profundidade limitada, escolhendo o limite apropriado,
(e) de profundidade iterativa.
Exercício 1.3
Considere o problema das vasilhas. Dispomos de duas vasilhas, com capacidades de 3 e 5 litros.
Inicialmente as vasilhas estão vazias e pretendemos medir uma certa quantidade de água. As ações que podemos executar são: encher totalmente cada uma das vasilhas; virar o conteúdo de uma vasilha na outra, até a primeira ficar vazia ou a segunda cheia; despejar fora todo o conteúdo de uma vasilha.
Para resolver este problema utilizando os algoritmos de busca estudados vamos usar a seguinte representação em Lisp para o estado do problema:
(defstruct estado
(v3 0) ; líquido existente na vasilha de 3 litros
(v5 0)) ; líquido existente na vasilha de 5 litros
As funções que implementam os operadores para este problema (encher-v3, encher-v5, v3-
>v5,