是否存在最小深度生成树算法？

Question

我目前正在优化电网规划，但 MST 并不能很好地解决问题，因为如果与主电网的连接点是辐射状的，则所有电力都必须通过一个边缘流动，并且会经过较长的“电气距离”到达每个耗电点。

我所处理的问题是最小化 MW*distance 或有功功率矩，但这会产生非线性问题。

因此，我要找到一棵最小生成树（不是最优，只是最有效）来将图形中到树根的最大电气距离最小化。

通过这种方式，我只需购买更长、更细的电缆，这比购买更短、更粗的电缆更便宜。

- Gonzalo Ramírez Sagner

Answer 1

在这种情况下，您不需要最小生成树，而是需要一棵最短路径树，它是一棵覆盖图上所有节点并且从每个点到源节点的距离最短的树。任何标准的最短路径算法都可以被改进成产生最短路径树。例如，Dijkstra算法的标准实现就可以产生这样的一棵树。

话虽如此……最短路径树不保证便宜，有可能构造出来的图中，最短路径树比相应的最小生成树要昂贵得多。换句话说，建立最短路径树可能需要支付的代价会比建立最小生成树高得多。

目前已经对寻找生成树进行了一些研究，这些生成树是在最小生成树（总权重最小）和最短路径树（到每个节点的距离最短）之间做出了妥善的平衡。但很遗憾，我无法即时想到可以查找这些内容的地方。

希望这能帮到您！

- templatetypedef

---

谢谢！我将考虑最短路径树和最小生成树之间的混合。我会随时向你更新我的进展！ - Gonzalo Ramírez Sagner

Prim算法在边权w_e非退化的情况下是Dijkstra算法的极限情况，其中边权为exp(w_e * t)。 - David Eisenstat

不明白你写的是什么。Prim+加权成本+t->无穷大=Dijkstra？还是相反？ - Gonzalo Ramírez Sagner

当长边变得不成比例时，Dijkstra算法会收敛到Prim算法。 - David Eisenstat

Answer 2

这似乎只是带有额外条件的最小生成树。像 Prim 算法一样的算法可以解决问题。

对每个节点赋权以考虑每个点的消耗。您应该得到一个连接中心节点和每个外部节点的连接，其长度最短，同时避免通过太多不同的节点发送电力。

- user2525056

---

问题在于边缘的Powerflow会给边缘本身增加额外的权重，而这个成本是与所使用的地形函数有关的。权衡距离可能会奏效，但“如何权衡”才是关键。我目前正在尝试使用正常的MST作为起点，并进行一些3-5次更改（每次添加一条边，然后删除另一条边以保持树的径向属性），以使最径向节点的距离最小化。 - Gonzalo Ramírez Sagner