工作总结与计划-西安交通大学计算机教学中心.ppt

* * * HPMS HPMS 活动9 The Muddy City ——最小生成树 西安交通大学 高效能建模与仿真研究小组 2011年10 本PPT的材料改编自csunplugged.org项目 Putting computers to work-Algorithms muddy city 方案1 方案2 An abstract representation of a (different) muddy city 主要内容 活动内容的描述 一般的解决方案 计算机解决方案——Prim和Kruskal算法 活动的进一步思考 参考文献 1. 活动内容的描述 活动背景 大家对圣人孔子都非常熟悉，而孔子周游列国的事迹也可谓是家喻户晓。孔子周游列国是从鲁国出发，大致走了卫国、宋国、齐国、郑国、晋国、陈国、蔡国、楚国等地。古代交通不发达，那么孔夫子如何能走访各国一次且仅一次，并且最终返回到起始点鲁国？我们可以用以下这个类似活动来回答上面的问题。 1. 活动内容的描述 活动流程 有一个城市，每当暴风雨过后道路都会变的很泥泞，因此市长决定对街道进行铺路，但不想花太多的钱。 因此指定了两个要求： （1）有足够的街道被铺好使得每个人都可以从他们的房子只经过铺好的路走到别人家房子，中间可经过别人家房子; （2）铺路的总费用应该最小。 1. 活动内容的描述 抽象的活动模型 右图是一个抽象的表 示方法。其中圆圈代 表房子，线表示泥泞 的路，而线旁边的数 字表示路的长度。通 常用这种抽象的表示 方法来阐明这种问题 的关系。 2. 一般的解决方案 贪婪算法 对于给定的网络G=(v,e,w)， 设T=(v`,e`)为G的一个子树， 首先选取权值最小的一条边e 加入T中，依次选择和该边顶 点相连的权值最小的边加入T 中，直至最后v`=v。 如上图所示红线就是按照该思路的一个结果集，但并不满足活动的要求2，即铺路的总费用最小。 3. 计算机的解决方案 Prim算法 设G=(V,E,W)?是一个含有?n?个顶点的连通图，则Prim算法构造最小生成树过程为: 从图中任意一个顶点开始，首先把这个顶点包括在子图T里，然后在那些其一个端点已在T里，另一个端点不是T里的边，找权最小的一条边，并把这条边和其不在T里的那个端点包括进T里 如此进行下去，每次往T里加一个顶点和一条权最小的边，直到所有顶点都包括进T里 3. 计算机的解决方案 Kruskal算法 按Kruskal算法构造最小生成树的过程为： 对G中的边按照其权值的非减次序排序，置子图T={} 依次来考虑图中的每一条边是否加入生成树T中。若当前被考虑的边与T中已经有的边不构成回路，将该边加入T中； 该边不加入T中。然后再考虑下一条边。直到所有的边都考虑完为止 3. 计算机的解决方案 Prim算法和Kruskal算法最优解图示 右图虚线部分所构成的线路即是按照Prim 算法和Kruskal 算法获得的最优解，即满足要求的最小生成树 3. 计算机的解决方案 Prim算法和Kruskal算法比较 Prim算法的时间复杂度为o(n2)，n为网中的顶点数，与网中的边数无关，因此，该算法适合求边稠密网的最小生成树。 Kruskal算法与Prim算法恰恰相反，它的时间复杂度为O(mlogm)，m为网中边的数目。因此，它相对于Prim算法而言，适合于求边稀疏的网的最小生成树 4. 活动的进一步思考 孔子周游列国问题 孔子周游列国问题，可以描述为： 孔子周游列国是从鲁国出发，大致走了卫国、宋国、齐国、郑国、晋国、陈国、蔡国、楚国、等地。古代交通不发达，那么孔夫子如何能走访各国一次且仅一次，并且最终返回到起始点鲁国？ 4. 活动的进一步思考 孔子周游列国问题 该问题属于NP-Complete问题，所以该问题的解法的大多为启发式解法。Bodin（1983）等人将此类问题的启发式解法分为两种： 途程建构法（Tour Construction Procedure） 途程改善法（Tour Improvement Procedure） 4. 活动的进一步思考 孔子周游列国问题解法 途程建构法（Tour Construction Procedure） 从距离矩阵中产生一个近似最佳解的途径，一开始寻找离开始最近的需求点为第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后，类似于贪婪算法。 4. 活动的进一步思考 孔子周游列国问题解法 途程改善法（Tour Improvement Procedure） 先给定一个可行途程，然后进行改善，直到不能改善为止。改善方法可以是： K-Opt(2/3 Opt)：把尚未加入路径的K条节线暂时取代