1) Em 1950, na revista filosófica Mind, Alan Turing publicou um artigo chamado “Computing Machine and Intelligence”. Neste artigo, Turing apresentou, pela primeira vez, o que hoje é conhecido por Teste de Turing. Com este pretendia-se descobrir se uma máquina pode ou não pensar. O teste de Turing funciona da seguinte forma: um interrogador (humano) fará perguntas a duas entidades ocultas; uma delas é um humano e outra é um computador. A comunicação entre o interrogador e as entidades é feita de modo indireto, pelo teclado, por exemplo. O interrogador tentará, através do “diálogo“ realizado entre ele e as entidades, decidir qual dos dois é o humano. O computador será programado para se passar por humano, e o humano responderá de forma a confirmar a sua condição. Se no final do teste o interrogador não conseguir distinguir quem é o humano, então conclui-se que o computador pode pensar, segundo o teste de Turing. (texto explicativo extraído de: http://www.din.uem.br/~ia/maquinas/turing.htm, mas o capítulo 1 do livro de Russell e Norvig, recomendado para estudo antes do teste, também discute sobre esta questão) 2) as heurísticas admissíveis são (a) D(i,j) e (c) D(i,j)/2. A letra (b) poderá não ser admissível pois pode superestimar o custo da solução ótima, que está limitado por valores menores ou iguais à distância em linha reta entre as cidades. A heurística 2*D(i,j) pode facilmente superar este custo. 3) Algumas soluções possíveis, mas o importante era definir: - estado inicial (robô no meio do labirinto com coordenadas x,y) - estado final (robô fora do labirinto com coordenadas xf,yf, com x != xf ou y != yf) - operadores (rodar para a direção N, S, E ou W e andar n passos) - tamanho do espaço de busca: O(3^d), com d sendo o comprimento do caminho (mas aceitei outras soluções que também faziam sentido) 4) Ao utilizar custos negativos (veja bem que não é heurística, é custo associado às arestas), teremos que explorar todo o espaço de busca se quisermos encontrar o caminho de menor custo. Se os custos fossem positivos (como nos exemplos que vimos em aula), eles sempre cresciam e, desta forma, alguns caminhos da árvore de busca poderiam ser podados assim que ultrapassassem o custo de um ramo de menor custo já encontrado. (aceitei várias respostas que também faziam sentido, de acordo com as diversas interpretações de custo que deram, embora eu tenha mencionado custos associados aos caminhos....) 5) A solução desta questão está no meu conjunto complementar de slides na página da disciplina em: http://www.dcc.fc.up.pt/~ines/aulas/1213/SI/AIMA_ch3_L2-complement.ppt) 6) Espaço de estados: (árvore binária)ia 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 - busca em largura: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 - busca limitada em profundidade com limite 3: 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15 - busca iterativa em profundidade: i=0 1 i=1 1 2 3 i=2 1 2 4 5 3 6 7 i=3 ordem igual a da busca limitada em profundidade com limite 3 (acima) 7) Cidade g h f Lugoj 0 244 244 Timisoara 111 329 440 Mehadia 70 241 311 (vai escolher Mehadia, que, no momento, é o nó de menor custo f) Lugoj 70+70 244 384 (não estou a verificar estados repetidos) Drobeta 70+75 242 387 (vai escolher Lugoj, que, no momento, é o nó de menor custo f) Timisoara 70+70+111 329 580 Mehadia 70+70+70 241 451 (vai escolher Drobeta, que, no momento, é o nó de menor custo f) No final: o caminho vai conter Lugoj(g:0,h:244,f:244), Mehadia(g:70,h:241,f:311), Drobeta(g:145,h:242,f:387), Craiova(g:265,h:160,f:425), Pitesti(g:403,h:100,f:503), (neste momento, Timisoara tem custo menor do que Pitesti (440 < 503), mas seus filhos vão ser maiores do que Bucharest, que vai ser o próximo nó a ser expandido) Bucharest(g:504,h:0,f:504) 8) a jogada de maximização é 5 9) os nós podados são: k,q,m,g,n,o ERRATA: apenas os nós k,q,g,n,o são cortados. O nó "m" não pode ser cortado! 10, 11 e 12 foram corrigidas de acordo com o código fonte do primeiro trabalho. Não aceitei respostas que diziam que não havia necessidade de verificar estados repetidos e também respostas em que a busca gulosa não verificava estados repetidos.