Inteligência Artificial Prova 1 - 2011/2 (*) Questão 1 O algoritmo A* cruza o grafo seguindo o menor caminho conhecido mantendo uma fila de prioridades. Se a qualquer momento ele encontrar um caminho de menor custo do que ele já está seguindo, então o caminho de maior custo é abandonado. Esta sistemática continua até que a solução seja alcançada. O IDA* é uma variante do A* e que usa uma iteração em profundidade para consumir menos memória, e com isso não irá memorizar o menor caminho atual e os custos dos nós visitados, mas irá lembrar somente um caminho por vez. Para a figura 1 e considerando que o custo heurístico estimado é o que está enumerado dentro do nó, o algoritmo A* comparta-se da seguinte maneira para traçar um caminho de A a F com '*' como o caminho escolhido: f(B) = 2 - 7 = -5 f(G) = 3 + 10 = 13 * f(C) = -3 - 8 = -11 f(BE) = -5 + 4 - 3 = -4 f(BD) = -5 + 3 - 6 = -9 * f(CD) = -11 + 0 - 6 = -17 * f(CE) = -11 - 3 - 3 = -17 f(BEF) = -4 + 0 + 0 = -4 f(BDF) = -9 - 5 + 0 = -14 * f(CDF) = -17 - 5 + 0 = -22 -> caminho de menor custo f(CEF) = -17 + 0 + 0 = -17 Já o IDA*, para o mesmo caso, comparta-se assim: f(B) = 2 - 7 = -5 f(G) = 3 + 10 = 13 * f(C) = -3 - 8 = -11 f(CD) = -11 + 0 - 6 = -17 * f(CE) = -11 - 3 - 3 = -17 -> política para escolher o último calculado * f(CEF) = -17 + 0 + 0 = -17 -> caminho escolhido e que não necessariamente é o de menor custo (*) Questão 2 a) Não. O número elementar de salas sujas não é compatível com a semi-inteligência do computador e com a sua prioridade de verificação de salas sujas. No exemplo apresentado, o valor de h1 é 2C, mas o custo real de resolução do problema é 12C + 2L. Esta afirmação considera que o aspirador deve visitar uma sala para concluir que ela está ou não está suja, e que ele sempre irá se mover nas direções priorizadas N, L, S, O. b) Uma função mais apropriada h2 pode ser definida: h2(n): mC + nL + dC m = Número de movimentos do aspirador até o máximo de 9 n = Número de salas sujas d = Distância manhattan do estado inicial para o final do aspirador c) Estado Posição Custo h1 h2 1 1,1 0 0 2 2 0,1 1 0 3 3 0,0 2 0 4 4 0,1 3 0 5 5 0,2 4 0 6 6 1,2 5 0 7 7 2,2 6 0 8 9 2,1 8 1 10 10 2,0 10 2 12 .. ... .. . .. 14 0,2 14 2 12 (*) Questão 3 Ver Questão 1. (*) Questão 4 Fronteiras: A: 3 (B,D,E) B: 4 (A,C,D,E) C: 4 (B,D,E,F) D: 5 (A,B,C,E,F) E: 5 (A,B,C,D,F) F: 3 (C,D,E) a) É possível colorir o mapa com esta estratégia. Os países Dlândia e Elândia reservam uma cor cada um para si, já que possuem fronteira com todos os outros países. Segue resolução: A B C D E F {a,b,l,v} {a,b,l,v} {a,b,l,v} {a,b,l,v} {a,b,l,v} {a,b,l,v} {b,l,v} {b,l,v} {b,l,v} {b,l,v} a* {b,l,v} {l,v} {l,v} {l,v} b* a {l,v} {l,v} {v} l* b a {v} {l} v* l b a {v} l* v l b a {v} l v l b a v* b) Os países Clândia, Dlândia e Elândia são os que possuem mais fronteiras, e acabam restringindo as opções dos outros países. Mesmo assim é possível colorir o mapa na ordem enunciada. Segue resolução: A B C D E F {a,v} {v} a* b* l* {v} {a} v* a b l {v} a* v a b l {v} a v a b l v* c) A cor azul em Clândia favorece a escolha de mais cores nos países restantes. Se fosse escolhido laranja, por exemplo, Dlândia e Elândia não poderiam ser coloridos, pois restaria a ambos somente o vermelho, o que não é permitido para um esquema de coloração de mapas. Segue resolução: A B C D E F a* b* {a,l,v} {l,v} {l,v} {a,b,l,v} a b a* {l,v} {l,v} {b,l,v} a b a l* {v} {b,v} a b a l v* {b} a b a l v b*