给一个电网,它是一组发电机,电线之间被拉伸。电线至少有一根电流发电机在电线的一端工作。找到与需要打开电源以提供最小数量的发电机当前到整个网络。
我们可以使用哪种算法来解决此问题?蛮力就像没有效果。在这里,我们可以提供任何语言的样本,因为通常我们正在搜索整个算法。
首先将问题建模为图形,节点是生成器,边是导线
接下来将图形转换为其折线图表示https://en.wikipedia.org/wiki/Line_graph
接下来在折线图https://en.wikipedia.org/wiki/Minimum_spanning_tree上运行最小生成树算法
MST中使用的边数就是答案