我正在设计一个城市建设游戏并遇到了一个问题。
想象一下 Sierra 的Caesar III游戏机制：您有许多城区，每个城区都有一个市场。距离上有几个粮仓与有向加权图相连。区别：人（这里是汽车）是形成交通拥堵的单位（这里是图权重）。
注：在凯撒系列游戏中，人们收割粮食并将其储存在几个大粮仓中，而许多市场（小商店）从粮仓中取出食物并运送给市民。
任务：告诉每个地区他们应该从哪里获取食物，同时花费最少的时间并尽量减少城市道路上的拥堵。
假设黄色区域相应地需要 7、7 和 4 个苹果。相应地，蓝色粮仓有 7 个和 11 个苹果。
假设边权重与其长度成正比。然后，解决方案应该类似于边缘上指示的灰色数字。例如，第一个区从第一个粮仓获得 4 个苹果，从第二个粮仓获得 3 个苹果，而最后一个区从第二个粮仓获得 4 个苹果。
在这里，垂直道路首先被占用到最大，然后剩余的工人被送到对角线路径。
我应该使用什么实用且非常快速的算法？我正在查看一些描述拥塞游戏的论文（拥塞游戏：竞争优化等），但无法了解全局。
您想研究最大流量问题。在这种情况下，它似乎是一个二分图，它应该使事情更容易可视化。
这是一个多源多汇最大流量问题，如链接中所述，通过创建超级源和超级汇可以轻松地将其转换为简单的最大流量问题。最大流量问题有许多有效的解决方案。
您可以做的一件事，就是解决另一个答案中讨论的增量更新问题，并且对计算机来说也可能更便宜，那就是忘记全局最优解决方案。让每个村民参与蚁群优化之类的活动。
考虑通过允许最右边黄色节点上的人抬高从右侧蓝色节点购买资源，这将鼓励一些来自右下角黄色节点的人采取稍长的步行到左侧蓝色节点。
我同意 Larry 和 mathmike 的观点，看起来这个问题确实是网络流的专门化。
另一方面，如果您的最终算法为每个市场找到其资源（粮仓）的生成树，首先根据最短路径贪婪地消耗这些资源，然后移动到下一个资源堆，那么问题可能会变得更容易。
考虑一下首先使用最大容量的道路（最大限度地提高道路效率）而不是试图尽量减少拥堵可能会有所帮助。
这就是问题的根源——通常，在图形问题中更容易找到接近最优的解决方案，就游戏开发而言，接近最优可能就足够了。
编辑：还想指出，mathmike 与维基百科的链接也谈到了顶点容量的最大流量问题，其中每个粮仓都可以被认为是容量有限的顶点。
你必须注意的是，你的游戏是连续的。如果你在时间 t 有一个解 X，并且发生了一些小的变化（例如：玩家建造了另一条道路，或者一个城市获得了更多人口），那么 Max Flow 算法给你的解可能会发生巨大变化，但是你' d 可能希望 t+1 处的解与 X 相似。在每个时间步完全不同的解是不现实的（在地图的南端新建 1 条道路，并自动重新计算所有路线）。
我会使用一些算法来计算初始解决方案（或者当发生重大变化时，比如地震摧毁了 25% 的道路），但大多数时候只会逐步更新它：意思是，在解决方案上定义某种形式的有效转换（例如，1 个城市尝试从与现在不同的粮仓获取 1 个食品单位）-您尝试更新（模拟预期的拥堵），如果更新的解决方案优于现有的解决方案，则保留更新的解决方案。在每个游戏回合或某个时间单位后运行此步骤 N 次。
它在计算上既高效（不需要每秒运行完整的 Max Flow），也会让您在行为上做出更真实、更平滑的变化。
拥有一个动态模型可能会更有趣，它可以对行为进行建模，从而产生一个合理的解决方案，而不是找到一个驱动行为的理想解决方案。假设您单独计划每次旅行。如果你是一名司机，你需要从 A 点到 B 点，你会怎么去那里？您可能会考虑以下几点：
我知道此时的典型交通状况，我会尝试在通常繁忙的道路周围寻找方法。您可以将此建模为不同时间的平均流量值，因为驾驶者不一定拥有有关当前流量的完美信息，但可能会随着时间的推移学习和识别趋势。
我不喜欢漫长而混乱的路线，有很多转弯。在计划旅行时，您可能会惩罚那些有很多优势的人。
如果您的模型中包含限速和红绿灯，我想避免长时间的低限速和/或大量红绿灯。我更喜欢高速公路或高速公路进行长途旅行，即使它们有更多的交通。
从行为上考虑问题而不是纯粹的优化可能会演变出其他有趣的动态。在现实生活中，交通很少会收敛到最佳解决方案，因此交通工程面临的很大一部分挑战是提出激励、惩罚和设计，以鼓励从驾驶员决策中发挥的自然动态中获得更好的解决方案。