文件名称：动态规划 初一
文件大小：196KB
文件格式：DOC
更新时间：2021-02-02 03:04:39
动态规划
假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。 可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树，简称为最小生成树问题。一棵生成树的代价就是树上各边的代价之和。 构造最小生成树可以有多种算法，下面我们介绍普里姆算法（PRIM）和克鲁斯卡尔算法（KRUSKAL）。