Ajuda com Heuristica de Grafos

[Josenilo]

Galera estou com dificuldade de formular uma heurística baseada em grafos para que possa solucionar este problema :

 

Zorc, o maior guerreiro do Mundo de Zambis, está recrutando seu exército para a grande

batalha final contra o exército do Mundo de Xulambs. Ele saiu caminhando pelo seu mundo

atrás de guerreiros de diferentes povos de seu mundo. A batalha ocorrerá no Mundo Xulambs

e, portanto, Zorc transportará seu exército por meio de uma nave que suporta um peso máximo

de W quilogramas. Para cada povo i que Zorc visita, os soldados possuem um peso wi (supondo

que todos os soldados do mesmo povo possuem o mesmo peso) e uma habilidade de guerra de hi

(supondo que todos os soldados do mesmo povo possuem a mesma habilidade).

O recrutamento dos soldados deve ser feita caminhando pelo Mundo de Zambis. Existem P

povos diferentes e cada povo pi tem soldados de peso wi e habilidade hi em quantidade ilimitada.

Zorc é livre para recrutar quantos soldados quiser, desde que eles caibam na nave de transporte.

Como o terreno do Mundo de Zambis é acidentado, não é possível ir de qualquer povo para qualquer

povo. De fato, para cada povo pi há um conjunto de povos P(pi) que podem ser alcançados a

partir dele. Tão pouco é possível recrutar soldados para todo sempre. Cada passagem de uma

povo i para uma povo j requer que se percorra uma distância dij metros e o como o momento da

guerra se aproxima, Zorc não pode andar por mais que D metros no total.

Você precisa auxiliar Zorc a encontrar o caminho que maximiza a habilidade total dos soldados

que serão recrutados! Para este trabalho, você deverá apresentar uma solução que utilize o

paradigma de programação dinâmica e uma solução que utiliza alguma heurística.

 

Queria uma ajuda só na ideia  da heurística mesmo, qualquer ideia é bem vinda. Obrigado