我在这里的前一篇文章之后重新发布了这篇文章，并提供了更多详细信息。
问题：问题包括一个掠夺者，他必须前往分布在地图上的不同城市。起始位置是已知的。每个城市都有与之相关的固定战利品。掠夺者的目的是穿越各种性质的地形。根据地形的性质，我的意思是每对城市之间的旅行成本各不相同。他必须最大化获得的战利品。
我们所做的：
我们生成了一个邻接矩阵（每个节点的战利品路径成本），然后采用启发式分析。它给出了一些合理的输出。
现在，现在的问题是，每个城市都有很少或更多的车辆，可以（通过支付）购买，可以用来旅行。车辆实际做的是降低路径成本。一旦购买了一辆车，它会一直持续到购买下一辆车的时间。是否购买车辆以及如何购买车辆由您自行决定。
我现在需要帮助。如何将车辆的概念融入我们已有的东西中？另外，任何可以帮助我们最大化利润的进一步想法。如果需要，我可以发布代码。谢谢！
一种方法是让一个有向边承担车辆成本，以降低成本。如果你愿意的话，你甚至可以做到这一点，减少比只是一个百分比更好。
不利的一面是，这可能会大大增加图表的大小（与您拥有不同车辆的副本数量以及它们之间的链接一样多），并且如果您的启发式不是最佳的，您可能必须对其进行修改以使其考虑新的优势积极。
听起来好像波束搜索可以解决这个问题。束搜索使用启发式函数H和参数k并且工作方式如下：
将集合S初始化为初始游戏位置。
将T设置为空集。
对于 S 中的每个游戏位置，在掠夺者移动后生成S的所有可能的后继位置。（一个动作是抢劫、购买车辆、移动到相邻的城市，或者掠夺者可以做的任何其他事情。）将每个这样的后继位置添加到集合T中。
对于T中的每个位置p，计算H ( p ) 以获得启发式函数H。（启发式函数可以考虑战利品的数量、车辆的拥有量、剩余未抢劫城市的数量以及您认为相关且易于计算的任何其他内容。）
如果您已用完搜索时间，请返回T中得分最高的位置。
否则，将S设置为T中得分最高的k个位置，然后返回步骤 2。
如果您以具有k个元素的堆的形式存储T ，则该算法运行良好。