O PacMan gravitacional (PacManGrave) é uma pequena variação do Jogo do PacMan tradicional, que aqui é jogado num
cenário 10x3. O PacManGrave sempre que se move para uma casa com comida, esta é comida e desaparece. O objectivo
consiste em papar a comidinha toda. Os movimentos podem ser cima, baixo, direita e esquerda, sendo selecionados por
essa ordem. Os movimentos para cima são mais difíceis e têm um custo de 2, os movimentos horizontais para a esquerda e
para a direita custam o mesmo: 1, mas os movimentos para baixo não têm custo algum. É por isso que se chama PacMan
gravitacional.
Figura 6.1
Figura 6.2
Considerando como estado o conjunto formado pela posição do PacManGrave e número dos pedaços de comida por
comer, aplique os algoritmos seguintes para determinar uma solução para o problema, em que a situação inicial é a
indicada na Figura 6.1. Em cada alínea, indique de forma clara, justificando, o caminho encontrado até comer os 3
pedaços de comida. Pode fazê-lo com a indicação do percurso efectuado (através de uma única seta—veja o exemplo do
percurso óptimo na figura 6.2) ou apenas com a sequência de movimentos, usando as suas abreviaturas: c (cima), b (baixo),
d (direita) e e (esquerda). Assuma sempre que se evitam os ciclos e que os desempates são resolvidos pela ordem: c, b, d,
e. Note que o PacManGrave pode regressar a uma casa onde já esteve antes, mas só depois de ter comido mais alguma
coisa, senão estaremos perante um ciclo no percurso: é o caso do percurso óptimo na figura 6.2, que corresponde à
sequência de 13 movimentos ddddddebbdedd com custo 11. Pode utilizar as figuras com o estado inicial do jogo para
operações auxiliares e para desenhar o percurso final.
a) Procura em profundidade.
b) Trepa-colinas sem repetição de estados visitados tendo como heurística a distância de Manhatan até à comida mais
próxima + o número de pedaços de comida que falta comer menos um. Por exemplo, a função heurística para o estado
inicial (PacManGrave na posição (Linha=1,Coluna=1) e com 3 pedaços de comida por papar) dará 5 (distância ao pedaço
de comida mais próximo) + 3 (número de pedaços por comer) – 1, ou seja 7.
c) Tendo em conta a mesma heurística de b), existe a garantia que A* devolverá sempre o caminho óptimo, seja qual for o
estado inicial?