我目前正在优化电网规划，但MST并不能很好地解决问题，因为如果与主电网的连接位于径向点，则所有电力都必须流过一个边缘，并且会经过很长的“电气距离”到每个消费点。
我正在研究的问题可能是最小化MW*distance或有功功率力矩，但这会产生非线性问题。
所以我想找到一个最小生成树（不是最优的，只是最有效的），它可以最小化到树根的最大电距离（通过图形的距离）。
通过这种方式，我只需要购买更长更细的电缆，这对于更短的粗电缆来说是一种更便宜的解决方案。
问问题
1025 次
3 回答
6
在这种情况下，您不需要最小生成树。您需要一个最短路径树，它是一种生成树，可以最小化从图中每个点到源节点的距离。可以修改任何标准的最短路径算法以生成最短路径树。例如，Dijkstra 算法的标准实现可以生成这样的树。
也就是说……最短路径树不能保证便宜，并且可以构建最短路径树比相应的最小生成树更昂贵的图。换句话说，与最小生成树相比，构建最短路径树可能需要付出更多的钱。
已经对寻找生成树的算法进行了一些研究，这些算法是 MST（最小总权重）和最短路径树（到每个节点的最小距离）之间的良好折衷，但不幸的是我不记得我的头顶在哪里去寻找这个。
希望这可以帮助！
于 2013-06-26T20:06:31.060 回答
1
这看起来只是带有一些额外条件的最小生成树。像 Prim's 这样的东西会起作用。
给每个节点一个权重，以说明每个点的消耗。您应该最终在中心节点和具有最短长度的每个外围节点之间建立连接，同时避免通过太多不同的节点发送电力。
于 2013-06-26T19:49:24.387 回答
1
我目前正在阅读有关 Dijkstra 算法的信息。在“最短路径树”下。也许这可以解决问题。
于 2013-06-26T20:08:19.433 回答