在游戏中寻找食物分配最佳路线的算法

Question

我在设计一款城市 build 游戏时遇到了问题。

想象一下 Sierra 的 Caesar III 游戏机制:您有许多城区，每个城区有一个市场。远处有几个粮仓用有向加权图相连。区别:人(这里是汽车)是造成交通拥堵的单位(这里是图表权重)。

注:在凯撒游戏系列中，人们收获粮食并储存在几个大粮仓中，而许多市场(小商店)从粮仓中取出粮食并运送给市民。

任务:告诉每个地区他们应该从哪里获取食物，同时花费最少的时间并最大程度地减少城市道路上的拥堵。

map 示例

假设黄色区域相应需要7、7、4个苹果。蓝色粮仓相应地有 7 个和 11 个苹果。

假设边的权重与其长度成正比。然后，解决方案应该类似于边缘上指示的灰色数字。例如，第一个地区从第一个粮仓获得 4 个苹果，从第二个粮仓获得 3 个苹果，而最后一个地区仅从第二个粮仓获得 4 个苹果。

在这里，垂直道路首先被占用到最大，然后剩余的 worker 被送到对角路径。

问题

我应该使用哪种实用且速度非常快的算法？我正在看一些描述拥塞游戏的论文(拥塞游戏:竞争中的优化等)，但无法了解全局。

Answer 1

您想查看 Max-flow问题。在这种情况下，它似乎是一个二分图，这应该使事情更容易可视化。