电网中最少传输的最佳图算法
Best graph algorithm for least transfer in an electric grid
我得到了一系列城市，每个城市都产生一定量的电力并且需要一定量的电力。每个城市最多有8个相邻城市，我尽量减少中转次数。
如果 A->B 10 能量，转移的总成本是 10。
如果 A->B->C 10 能量（A 到 C 通过 B），总转移成本为 20。
我考虑过在每个需要能量的点上使用 Djikstra，并在找到足够的能量时结束对该点的搜索，但想到了几个陷阱。
我想知道我还能考虑哪些可能有用的东西？
我还考虑过研究 Floyd-Warshall 算法和 Hagerup（在维基百科上阅读了一些关于它们的信息，它们似乎可能可行）
谢谢
一旦你有足够的能量就结束搜索并不能保证找到最短路径，但是让 Dijkstra 运行 完全为每个耗电点完成，并且可能仍然是合理的在计算上取决于网络的大小。
Lookup A* 算法改进了 dijkstra 的启发式算法，可能会消除一些陷阱。
我真的想不出任何其他算法。
其实我觉得A*应该没问题
你的问题很容易简化为众所周知的minimum-cost flow problem:
The minimum-cost flow problem (MCFP) is to find the cheapest possible
way of sending a certain amount of flow through a flow network.
这种减少可以通过以下方式完成。将虚拟 "source" 和 "sink" 顶点添加到图形中，将有向边从源添加到每个原始顶点，其容量等于该顶点的生产率，从每个原始顶点添加一条有向边到具有容量的下沉等于该顶点的消耗率。根据需要在原始边上设置容量和成本，并在生成的网络上解决最大流最小成本问题。
我也怀疑 Dijkstra 算法或任何最短路径算法是否有任何用处，因为它们只关心来自特定城市的一个单位电力的路径，并且没有考虑 "interference" 不同城市发电的影响。例如，如果您有两个城市（A 和 B）产生 1 个单位的能量，另外一个靠近 A 和 B 的城市（C）消耗 1 个单位的能量，另一个城市（D）消耗 1 个单位的能量能量，那么你将不得不将能量从 A 或 B 路由到 D，但没有最短路径算法可以为你提供这个。
我得到了一系列城市，每个城市都产生一定量的电力并且需要一定量的电力。每个城市最多有8个相邻城市，我尽量减少中转次数。 如果 A->B 10 能量，转移的总成本是 10。 如果 A->B->C 10 能量（A 到 C 通过 B），总转移成本为 20。 我考虑过在每个需要能量的点上使用 Djikstra，并在找到足够的能量时结束对该点的搜索，但想到了几个陷阱。 我想知道我还能考虑哪些可能有用的东西？ 我还考虑过研究 Floyd-Warshall 算法和 Hagerup（在维基百科上阅读了一些关于它们的信息，它们似乎可能可行）
谢谢
一旦你有足够的能量就结束搜索并不能保证找到最短路径，但是让 Dijkstra 运行 完全为每个耗电点完成，并且可能仍然是合理的在计算上取决于网络的大小。
Lookup A* 算法改进了 dijkstra 的启发式算法，可能会消除一些陷阱。 我真的想不出任何其他算法。
其实我觉得A*应该没问题
你的问题很容易简化为众所周知的minimum-cost flow problem:
The minimum-cost flow problem (MCFP) is to find the cheapest possible way of sending a certain amount of flow through a flow network.
这种减少可以通过以下方式完成。将虚拟 "source" 和 "sink" 顶点添加到图形中，将有向边从源添加到每个原始顶点，其容量等于该顶点的生产率，从每个原始顶点添加一条有向边到具有容量的下沉等于该顶点的消耗率。根据需要在原始边上设置容量和成本，并在生成的网络上解决最大流最小成本问题。
我也怀疑 Dijkstra 算法或任何最短路径算法是否有任何用处，因为它们只关心来自特定城市的一个单位电力的路径，并且没有考虑 "interference" 不同城市发电的影响。例如，如果您有两个城市（A 和 B）产生 1 个单位的能量，另外一个靠近 A 和 B 的城市（C）消耗 1 个单位的能量，另一个城市（D）消耗 1 个单位的能量能量，那么你将不得不将能量从 A 或 B 路由到 D，但没有最短路径算法可以为你提供这个。