algorithm - 掠夺者困境算法

Question

我将在之前的一个之后重新发布 here更多详情。

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

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

现在，问题现在是每个城市里的车辆很少或更多，可以(通过支付)购买并可以用来旅行。车辆的实际作用是降低路径成本。购买车辆后，它会一直保留到购买下一辆车的时间。买不买以及怎么买，都由upto决定。

此时我需要帮助。如何将车辆的想法融入我们已有的东西中？另外，任何可能帮助我们实现利润最大化的进一步想法。如果需要，我可以发布代码。谢谢!

Answer 1

实现此目的的一种方法是让一条有向边承担车辆的成本，使其朝向具有降低成本的复制图。如果您愿意，您甚至可以将减少幅度缩小到比百分比更精细的程度。

不利的一面是，这可能会大大增加图形的大小(与您拥有不同车辆的副本一样多，加上它们之间的链接)，如果您的启发式算法不是最优的，您可能必须对其进行修改它积极地考虑新优势。