《暖气管道布设问题的最佳解决方案》由会员分享，可在线阅读，更多相关《暖气管道布设问题的最佳解决方案（10页珍藏版）》请在金锄头文库上搜索。
1、陕西师大计科院 2008 级算法设计与分析课程论文集暖气管道布设问题的最佳解决方案暖气管道布设问题的最佳解决方案沈思哲，王颖，王锐，刘东杰，陈元祝，夏驰（陕西师范大学计算机科学学院 08 级软件工程，西安，710062）摘摘 要：要：日常生活中暖气管道的布设问题通常用最小生成树算法求得最优解。本文给出了一个暖气管道布设的场景，采用 Prim 算法、Kruskal 算法和遗传算法三种算法解决该暖气管道布设问题，并通过实验仿真比较了三种算法的性能，得到了设暖气管道布设的最佳解决方案。关键词：关键词：最小生成树；Prim 算法；Kruskal 算法；邻接矩阵；贪心算法；遗传算法；交叉；变异；Heat
2、ing pipe layout question the best solutionShen Si-zhe ,Wang Ying ,Wang Rui ,Liu Dong-jie ,Chen Yuan-zhu ,Xia Chi（School of Computer Science ,Shanxi Normal University ,Xian ,710062）Abstract:Abstract: Daily life heating pipe layont problems usually use a minimum spanning tree algorithm and get the opt
3、imal solution. The paper gives a central heating conduit laid scene, using Prim algorithm, Kruskal algorithm and genetic algorithm to solve the three algorithm central heating conduit layont problem, and through experiment comparative simulation three kinds of performance of the algorithm, obtained
4、a heating pipe quasi-geoid with the best solution.Keywords:Keywords:Minimum Spanning Tree;Prime Algorithm,Kruskal algorithm,adjacency matrix;Greedy algorithm,Genetic Algorithm,chiasma,Mutation;1 1 引言引言在一个连通图 G 中，如果取它的全部顶点和一部分边构成一个子图 G ，并且边集中的边既将图中的所有顶点连通又不形成回路，则称子图 G是原图 G 的一棵生成树。对于一个连通网(即连通带权图) 来说，生
5、成树不同，每棵树的权( 即树中所有边上的权值和) 也可能不同，权最小的生成树称为图的最小生成树。在带权连通平面图中求最小生成树，是图论的基本问题之一。在实际工作中有很重要的意义。对该问题的比较典型算法是贪心算法和遗传算法。所以在本文中应用了最小生成树的 Prim 算法、Kruskal 算法和遗传算法来解决如何以最低的经济代价铺设暖气管道网的问题。2 2 问题概述问题概述某单位计划铺设暖气供水管道，以保证在任何两个房间之间都有通路，且铺设管道成本最小，可以用带权的无向图为这个问题建模。其中顶点表示房间，边表示房间之间可达的路径，边上的权表示对应管道的成本，通过找出一棵生成树，使得这棵树各边的权之
6、和为最小，就可以解决这个问题。下面我们以图 1 为例，分别采用 Prim，Kruskal 和遗传算法分析对比求得暖气管道布设问题的最优解。暖气管道布设问题的最佳解决方案ABCEDFG927 148563图图 1 暖气布设网络实例暖气布设网络实例3 3 求解最小生成树问题的常用算法求解最小生成树问题的常用算法贪心算法是一种改进了的分级处理算法，根据某个优化目标保证每一步都有局部最优解。贪心算法从局部出发，最终得到整体最优。它每次只考虑一步，每一步数据的选取都必须满足局部最优条件。从枚举剩下的数据与当前已经选取的数据组合获得的解中，提取能得到最优解的唯一一个数据，加入结果集合中，直到剩下的数据不能
7、加入为止；遗传算法借助于生物进化机制与遗传学原理，先随机产生一些个体，然后进行选择、交叉和变异操作模拟自然界中生物的进化过程。使个体的性能不断提高，逼近问题的最优解。它用于求解组合优化问题非常有效。寻找最小生成树实际也是组合优化问题，因此可以使用遗传算法解决。3.13.1 PrimPrim 算法算法以某个节点为初始点，选择与该节点相连且权值最小的边，将该边对应的节点加入已选的节点集合，然后选择与已选节点相连、未被使用且权值最小的边，若加入该边后不形成环路，则将其对应的点加入到已选节点集合中，直到所有节点都入选。Prim 算法构造最小生成树的过程如图 2 所示：ABCEDFG21ABCEDFG2
8、1ABCEDFG214图 2-1 图 2-2 图 2-3ABCEDFG2146ABCEDFG21463ABCEDFG214563图 2-4 图 2-5 图 2-6图图 2 最小生成树最小生成树-Prim 算法示意图算法示意图 设 A 为初始节点，选取与 A 相邻的权值最小的边 A-C，并将点 C 加入到目标生成树的点集合中如图 2-陕西师大计科院 2008 级算法设计与分析课程论文集1; 以目标生成树现有节点 A、C 为起始点，从未被利用的边中选取与 A、C 相邻且权值最小的边 C-D，并将 D 加入到目标生成树的点集合中，如图 2-2； 图 2-3、2-4、2-5、2-6 操作均同步骤，直到
9、目标生成树包含所有的节点，即得到了目标生成树，如图 2-6假设 N=（V，E）是一个连通网，节点数为 L（V） ，边数为 L（E） ，且 L（E）不能小于 L（V） ；T=（V，E） （EE）是目标生成树，U 是 V 的一个非空子集。任取一点 v 构成集合 V，然后不断地从 V-V中选取一点 vi 到 V中某点（如 v0）权最小的边（v0，vi）加入树 T 中，并令 V=V vi，直至 V=V。图图 3 最小生成树的普利姆算法执行步骤最小生成树的普利姆算法执行步骤由最小生成树的普利姆算法执行步骤分析可得 Prim 算法的时间复杂度为：O(n2)，其中 n 为节点个数。3.23.2 Kruska
10、lKruskal 算法算法按照边的大小排序，从小到大依次加入边，如果加入的边不构成环路，则将该边设为最小生成树的边。Kruskal 算法构造最小生成树的过程如图 3 所示：ABCEDFG1ABCEDFG21ABCEDFG213图 4-1 图 4-2 图 4-3ABCEDFG2143ABCEDFG21453ABCEDFG214563图 4-4 图 4-5 图 4-6图图 4 最小生成树最小生成树-Kruskal 算法示意图算法示意图Step1：设节点数为 vexnum，边数为 arcnum。以Step2：设循环初始值为 i=0,循环次数 n=G.vexnum；Step3：判断 iG.vexnum
11、-1 是否成立，若不成立则执行 Step6，否则继续向下执行；Step4：查找距离当前找到的节点集合最小距离的边 minedgek并记录当前节点 z=minedgei.endvex；重新选择下一次要比较的边，即距已有节点最近的边的集合；Step5：i=i+1,跳到 Step3；Step6：打印结果：PrintMinEdge(iGraph G,closedge minedge)；暖气管道布设问题的最佳解决方案 从以排序的边中选取权值最小的边 A-C，将其加入目标生成树中，如图 3-1； 从未被使用的边中选取权值最小且加入后不会形成回路的边 C-D，并将其加入目标生成树中，如图 3-2； 图 3-
12、3、3-4、3-5、3-6 操作同图 3-2.，直到加入的变数为 n-1(n 为节点数)，即生成了目标生成树，如图 3-6。假设 N=（V，E）是一个连通网，节点数为 L（V） ，边数为 L（E） ，且 L（E）不能小于 L（V） 。T=（V，E） （EE）是目标生成树，开始假设有 m 个点，n 条边，先在所有边中找出权最小的边，将它加入最小生成树中并输出，然后把此条边的权改为无穷大，相继添加不与已经选择的边形成简单回路的权最小的边，当选择了 n-1 条边时停止，则这 n-1 条边组成的即为最小生成树。3.2.3 初始图：图图 5 最小生成树克鲁斯卡尔算法执行步骤最小生成树克鲁斯卡尔算法执行步
13、骤由以上步骤分析可得：Kruskal 算法的时间复杂度为 O(eloge)，其中 e 为边数。3.33.3 遗传算法遗传算法遗传算法借助于生物进化机制与遗传学原理，先随机产生一些个体，然后进行交叉、变异和选择操作，模拟自然界中生物的进化过程，使个体的性能不断提高，逼近问题的最优解。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局化概率搜索算法，它通常应用于求解组合优化问题。寻找最小生成树实际也是组合优化问题， 因此使用遗传算法可以得到一个最优的解或者接近最优的解。遗传算法的基本过程是：首先采用某种编码方式(如二进制等)将解空间映射到编码空间，每个编码对应问题的一个解， 成为
14、染色体或个体。一般通过随机方法确定起始的一群个体，称为种群，在种群中根据适应值或某种机制选择个体， 使用各种遗传操作算子产生下一代如此进化下去，直到满足期望的终止条件。其中我们把第 t 代群体记做 P(t)。生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成。与之相对应，遗传算法中使用的就是所谓的遗传算子来作用于群体 P(t)中，进行遗传操作，从而得到新一代群体 P(t+1)。常用的遗传算子有交叉、变异和选择。编码即采用某种编码方式(如二进制等)将解空间映射到编码空间，每个编码对应问题的一个解， 成为染色体或个体。对于 MST 问题, 如何给树编码是遗传算法的关键。通常采用针对边的
15、0-1 编码和针对节点的 prufer 数编码两种编码方式。0-1 编码是以无向图中的所有边为编码变量，各个编码变量的取值为 0 或 1。设一无向图中共有 D 个定点, P 条边, 那么就可以用长度为 P 的二进制字符串表示该图的所有子图。字符串中对应位为 1 表示该边在子图中, 否则就不是子图的边。0-1 编码的方法直观、简单。但是用边编码会在遗传算法的初始种Step1：开始时设有 vexnum 个节点，arcnum 条边，用 min 记录每一次找到的最小边，它的初值为min=argc00即邻接矩阵中的第一个权值，循环次数 K=0；Step2：设循环次数为 vexnum-1；Step3：将 min 与余下路径的权值进行比较，若有某条路径的权值小于 min，则将它赋值给 min，记录它的下标 i，j，若它与已添加的边形成回路，则舍弃；否则将这条最小边打印出来，之后将它的权值设为无穷大；Step4：判断 Kvexnum-1 是否成立，若成立，则继续，否则跳到 Step6；Step5：k+,跳到 Step3；Step6：打印结果；陕西师大计科院 2008 级算法设计与分析课程论文集群的随机生成过程和交叉、变异过程中产生大量的不可行解, 从而求解效率不高。Prufer 编码是根据图的节点信息得到的 Prufer 数排列。根据 Cayley 定理
