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.