2

我在这里的前一篇文章之后重新发布了这篇文章,并提供了更多详细信息。

问题:问题包括一个掠夺者,他必须前往分布在地图上的不同城市。起始位置是已知的。每个城市都有与之相关的固定战利品。掠夺者的目的是穿越各种性质的地形。根据地形的性质,我的意思是每对城市之间的旅行成本各不相同。他必须最大化获得的战利品。


我们所做的: 我们生成了一个邻接矩阵(每个节点的战利品路径成本),然后采用启发式分析。它给出了一些合理的输出。

现在,现在的问题是,每个城市都有很少或更多的车辆,可以(通过支付)购买,可以用来旅行。车辆实际做的是降低路径成本。一旦购买了一辆车,它会一直持续到购买下一辆车的时间。是否购买车辆以及如何购买车辆由您自行决定。

我现在需要帮助。如何将车辆的概念融入我们已有的东西中?另外,任何可以帮助我们最大化利润的进一步想法。如果需要,我可以发布代码。谢谢!

4

2 回答 2

4

一种方法是让一个有向边承担车辆成本,以降低成本。如果你愿意的话,你甚至可以做到这一点,减少比只是一个百分比更好。

不利的一面是,这可能会大大增加图表的大小(与您拥有不同车辆的副本数量以及它们之间的链接一样多),并且如果您的启发式不是最佳的,您可能必须对其进行修改以使其考虑新的优势积极。

于 2013-01-14T13:44:20.603 回答
1

听起来好像波束搜索可以解决这个问题。束搜索使用启发式函数H和参数k并且工作方式如下:

  1. 将集合S初始化为初始游戏位置。

  2. T设置为空集。

  3. 对于 S 中的每个游戏位置,掠夺者移动后生成S的所有可能的后继位置。(一个动作是抢劫、购买车辆、移动到相邻的城市,或者掠夺者可以做的任何其他事情。)将每个这样的后继位置添加到集合T中。

  4. 对于T中的每个位置p,计算H ( p ) 以获得启发式函数H。(启发式函数可以考虑战利品的数量、车辆的拥有量、剩余未抢劫城市的数量以及您认为相关且易于计算的任何其他内容。)

  5. 如果您已用完搜索时间,请返回T中得分最高的位置。

  6. 否则,将S设置为T中得分最高的k个位置,然后返回步骤 2。

如果您以具有k个元素的的形式存储T ,则该算法运行良好。

于 2013-01-14T15:41:38.150 回答