铺设管道

来自计算思维百科
跳转至: 导航搜索
铺设管道1.png

某新建小区要铺设煤气管道,管理人已经做出小区中需要接入的点和距离,右图中所示的A、B、C、D、O为小区中煤气管道的接入点和距离,为了节省人力物力,管理人想要找出最短的铺设路径。

解决方案 -—最小生成树法

最小生成树法是贪心法的体现,需要我们选择当前最优解开始,则我们可以找出上图中连接两点距离最短的一条边,然后再找到距离第二小的一条,若该边连接的顶点还没有连通,则选择该条边,否则寻找下一小距离的边。依此类推,最后可生成一棵最小生成树。如下图:则为铺设管道的最优路径。

铺设管道2.png

运用的计算思维

要在n个城市之间建立联系,则连通n个城市只需要n-1条线路,因此我们可以利用最小生成树的方法来找到连通方式。最小生成树的方法运用了计算思维中的优化思想。