Gon*_*ner 5 algorithm graph minimum-spanning-tree graph-algorithm
我目前正在优化电网规划并且MST不能很好地解决问题,因为如果与主电网的连接处于径向点,则所有电力必须流过一个边缘并且将经过长的"电气距离"到达每个消费点.
我正在考虑的问题可能是最小化MW*distance或有功功率时刻,但这会产生非线性问题.
所以我想要找到的是最小的生成树(不是最优的,最有效的),它最小化到树根的最大电距离(通过图的距离).
通过这种方式,我只需购买更长的更薄的电缆,这是更短的更粗电缆的更便宜的解决方案.
在这种情况下,您不需要最小生成树.您需要一个最短路径树,它是一个生成树,最小化从图中每个点到源节点的距离.可以修改任何标准最短路径算法以产生最短路径树.例如,Dijkstra算法的标准实现可以生成这样的树.
也就是说......最短路径树不能保证便宜,并且可以构建图表,其中最短路径树比相应的最小生成树贵得多.换句话说,您可能需要花费更多的钱来构建最短路径树而不是最小生成树.
已经有一些研究用于寻找生成树的算法,这些算法在MST(最小总重量)和最短路径树(每个节点的最小距离)之间有很好的折衷,但遗憾的是我不记得我的头顶在哪里寻找这个.
希望这可以帮助!
这看起来只是带有一些额外条件的最小生成树。像普里姆那样的东西会起作用。
为每个节点赋予权重以考虑每个点的消耗。最终，您应该在中心节点和每个外围节点之间建立一个长度最短的连接，同时避免通过太多不同的节点发送电力。