Scotland Yard problema adaptado

stefanopt

Suspenso
Boas malta. Tenho que escrever um programa para um agente de IA que jogue o jogo Scotland Yard.
O agente joga com 3 detectives, e a posição do ladrão é conhecida e não muda, ou seja, o problema passa a ser um problema de caminho mais curto, com a restrição no número de bilhetes que os detectives podem usar.
Posto isto, usar um algoritmo greedy que minimize a distância entre o ladrão e o agente, não encontra a solução óptima, pois o gajo pode gastar os bilhetes de maneira não eficiente.
O que eu quero dizer com isto é, os detectives podem andar sempre para o estado em que estariam mais perto do agente, mas nunca lá chegar, porque têm muitos movimentos pelo caminho e poucos bilhetes.
Alguma dica?
 
Última edição:
Back
Topo