西安市经开区公共自行车服务系统优化方案设计

1、摘 要本文研究的是西安市经开区公共自行车的分配和调度优化问题，通过合理的分配方案和调度方案，以满足所有租赁点对自行车的数量需求及调度花费时间最少的要求。建立01规划模型，自行车分配调度模型，以及租赁网点设置模型，通过最小生成树算法和启发式搜索等求解，较好的实现了自行车服务系统的优化。对于第一问，依据租赁点的需求和约束条件分配自行车；根据经纬度和floyd算法求出各租赁点之间的距离，引入01变量表示租赁点间是否发生调度，采用最小生成树算法，经过租赁点的时间及装卸自行车的时间为权重，通过matlab编程用避圈法求解最小生成树，求得的路径就是最佳行车路线，每辆车调度一次平均用时135分钟，完成一天的

2、调度总时间为806分钟。 对于第二问，约束为投入经费总数和租赁点自行车需求，目标是设置的租赁点能够覆盖更大的面积，而且整个调度花费时间较少，用excel将备选租赁点需求量由大到小排序，选取自行车需求较多且三个时间段需求相差小的网点，应用动态规划算法，设新增租赁点数为k,代入经费约束即可得到k值不大于28，通过调整新增租赁点采用启发式搜索求新增网点和车辆的合适分配方案，编程得出新增网点为26个，自行车总数697辆 。对于第三问，通过增加调度车来减少调度时间，采用租赁点分区的思想，每辆调度车只在一个分区内调度，提高调度的效率。设新增调度车p辆，根据问题二的分配结果用问题一的模型计算调度花费的时间，

3、各分区内都采用最小生成树算法求解最优调度路线，改变p值和分区，直到所有分区都能满足150分钟内调度完毕，即为新增调度车数。关键词： floyd算法 最小生成树 启发式搜索 0-1变量 matlab编程 西安市经开区公共自行车服务系统优化方案设计目录一、 问题的背景与重述21.1问题背景21.2 问题重述2二、 问题分析32.1问题一分析32.2 问题二分析32.3问题三分析3三 、问题的基本假设4四、符号规定4五、模型的建立与求解5问题一的模型：5问题二的模型7问题三的模型：10六、模型的分析和检验：136.1. 模型的检验136.2. 模型的优点146.3. 模型的缺点14七、模型的推广15

4、八、参考文献15九、附录：15一、 问题的背景与重述1.1问题背景近年来，我国各级城市的机动车数持续增长引发了道路拥堵、空气污染等问题，而租借公共自行车服务系统能够从一定程度上缓解这一现象。然而，居民居住地和交通站点通常都有一段距离，这段不远的距离以及现实存在的公共交通拥挤现象则使居民乘坐公共交通的意愿降低，公共自行车服务系统已被证明能够从一定程度上解决这一问题。将租赁点设置在合适的位置，可以覆盖更多的面积提高效率，避免资源浪费，根据租赁点自行车的需求量和使用频率，合理的分配自行车，并通过调度专用车在使用高峰期阶段进行合理调度，尽量使调度过程花费短的时间，且不能影响自行车的租用，最大程度地满足

5、居民对车辆的需求，提高车辆利用率。1.2 问题重述西安市经开区公共自行车服务系统已建成租赁点30个，自行车总量达到850辆。现已知前期的30个租赁点位置，每个租赁点能够放置的车辆数目不能超过40辆，且通常车辆总数至少应超出需求量的10%。将实时观测到的数据归结到3个车辆使用需求最多的时间段（可认为每天的需求量不变）居民可在任意一个租赁点还车，在某个租赁点还车的概率与租车点和还车点的距离成反比，且假设居民的骑行距离不超过2km；假设车辆调度只在车辆需要最多的时间段进行，目前西安经开区用于运送公共自行车的调度车有2辆，每辆每次可运50辆自行车，调度车平均时速30km/h，每辆自行车装（或卸）平均耗

6、时1min；假设建设一个租赁服务网点需要50000元，在使用周期内，购买、养护一辆自行车需要1000元。（1）根据目前经开区网点自行车需求情况等信息，若要求调度平均耗时尽量少，针对已有的30个租赁点来决定最优车辆分配方案、调度方案，并给出完成调度所耗费的时间。（2）假设经开区公共自行车服务系统三期建设准备投入建设经费200万元，据此建立数学模型，确定新增租赁点数目、位置以及合适的放置车辆数目。（3）针对问题（2），进一步研究，如果要求在150min内完成调度，是否需要增加调度车辆（购置调度车辆费用由其它项目经费解决，不包含在三期建设提供的200万元经费中间）？并写出该情形下的自行车调度方案。二

7、、 问题分析2.1问题一分析通过对本问题的分析，根据结论要保证调度平均耗时最少，则在每个时间段内调度车行驶时间和装卸自行车总时间要最少，先求解出租赁点之间的实际车行距离和居民还车的概率，也相继可以确定居民还车数目，根据每个租赁点的需求数,通过建立相应的数学模型,进而可得调度车在每一个租赁点的调度时间。因此可以根据已知的道路连通图，首先通过floyd算法算出任意两个租赁点间的距离，其次以时间为权重建立最小生成树模型，找出能使调度车耗时最少的行驶路线和调度车的分配方案。2.2 问题二分析这个问题可以在第一个问题的基础上解答，目标都是使得整个调度花费时间最短。新增网点和自行车必须满足经费约束，为使设

8、置方案最合理应将网点设在需求量较多的地方，将需求量排序后筛选出备选网点，按照网点需求将所有自行车分配，使得既满足需求又能让调度时间最短。同问题一一样首先用matlab编程求出所有网点间距离，利用启发式搜索的算法，依次改变备选的新增网点，直到找出花费最短时间的路径。2.3问题三分析该问通过增加调度车的数量来减少调度时间，调度是在问题二分配的结果上进行，因此采用最小生成树算法寻找最快调度方案，可以将网点进行分区（相距近的网点为一个分区）来提高调度效率降低时间复杂度，假设需要增加p辆调度车，每辆调度车只在一个分区行驶且相互独立，应用问题二的模型计算各自的调度时间，改变p值直到最大值不大于150分钟，

9、即为新增调度车。三 、问题的基本假设 1.调度车始终按照30km/h的平均速度行驶；2.居民的骑行距离不超过2km；3.三个时间段需求量的平均值具有可靠性，能够满足需要；4.问题的求解只需考虑时间、费用和数量因素；5调度车在网点间的行驶距离可以按照经纬度计算。四、符号规定 装卸车在第i个租赁点装卸的自行车数；：第i个租赁点在调度后的自行车数；：第i个租赁点在租完还完后的自行车数；：租赁点i需要的自行车数； 新增的租赁点点数； 增加的自行车数； 增加的调度车数；：租赁点i与租赁点j之间的距离；五、模型的建立与求解根据以上的分析，可将原问题转化为:自行车分配和调度车路线的优化问题。问题一的模型：在

10、问题一中，我们考虑编号130的租赁点，首先，由假设可根据7:008:00之间各个租赁点的自行车需求量，将850辆自行车按照需求比例分给各网点，通过对分配结果的分析，并结合题中的约束条件，对分配情况进行调整，然后重复分配分析调整，从而得到第一个时间段的最优的分配方案，即各个租赁点的b，结果如下： 网点编号 123456789101112131415车辆数 20283939233818393125253991639网点编号 161718192021222324252627282930车辆数 232831342820402040252840221825我们用0-1变量来表示租赁点i与租赁点j是否有自

11、行车的调度,即目标函数为寻找一条从起始点开始到各个节点生成的最优树，要求各条线路的权值（权值即为两个租赁点间所用的时间和装卸自行车用的时间）和最小，附录中列出了30个点之间的距离，我们可以把它看成一个赋有权值的图g，先要求出图g的最小生成树，使树上各边的总权和达到最小。然后基于最小生成树生成一个可行的最短行车路径。即：s.t模型的求解具体过程如下：步骤1：利用题目中给出的各租赁点的经纬度数据，matlab编程得到任意两个租赁点之间的距离，然后根据还车的概率与租车点和还车点的距离成反比，即可以得到各个租赁点还入的自行车数。步骤2：求解最小生成树的方法有破圈法、避圈法、dijkstra算法等。这里

12、我们用避圈法求解，避圈法是指将图g中的边按照权数大小逐条考察，按不构成圈的原则加入到t（树）中，直到为止，即t的边数=g的顶点数-1为止。避圈法的算法是：1.把g的边按权的大小整理成，令.2.若含圈，则转3，否则转4.3令，若则转2；否则停止，g不存在最小生成树。4.令，。5.若，结束，是最小生成树；否则转3.根据避圈法的原理，matlab编程得到的结果如下：t2 t1136781013151721222430136781013151721222430（图中打钩的表示两个网点之间有自行车的调度）步骤3：由于0-1整数规划法中决策变量为整数，我们利用lingo优化软件分析求解此规划问题，根据问题

13、一模型的建立中目标函数及约束条件编写lingo程序如下：sets: sk/1.30/:s,x; si/1.30/:a; sik(si,sk):c,l;endsetsmin=sum(sk:2s*x)+sum(sik:a);for(si(i): sum(sk(i):l(j,i)=1);for(sik(i,j):l(i,j)=w(i);for(sk:bin(s);for(sik:bin(x);data: s,c,x=ole(c:success.xls,s,_c,x); ole(c:success.xls,s,_c,x)=s,c,x;enddataend将matlab编程得到的结果结合实际情况，采用最

14、小生成树的算法，调度方案车一 ： 27102893078236417 3214 车二： 111213 115162919520212625平均调度一次花费时间为:车一时间:137分钟车二时间：134分钟 问题二的模型目标：新增租赁点能够覆盖更大的面积满足需求量大的网点且整个调度过程花费时间最短，即mint，maxb约束：新增的租赁点和自行车所花费用小于投入建设经费200万元。所以得到如下模型：s.t模型的求解该模型的直接求解在短时间是非常困难的，所以我们在问题一的基础上加以改进，采用启发式搜索算法。此算法的步骤如下。步骤一： 将备选的网点的自行车需求数量按照从高到低的进行有序排列，形成703的

15、矩阵，每行表示该网点在各时间段需要的自行车。步骤二：按照需求量的大小进行选择新增的网点，新增自行车即为所选网点的自行车总和，代入投入经费的约束条件，选取符合条件的假设新增网点，用问题一所的模型分配自行车。步骤三：应用问题一的模型，根据经纬度把新增的网点与原网点间距离用folyd算法和matlab编程计算出来。步骤四：用最小生成树法寻找调度花费时间最短的路径，改变假设的新增网点，重复上述步骤，直到找出花费时间最短的最优的路径。备选租赁网点自行车需求量排序：网点编号7:008:30车辆需求数11:0012:30车辆需求数17:3019:00车辆需求数564040403140278693921235

16、038373277333628603332374933183591322220413212127132121094268988253335812523146324283343241716722339344723363290233237842129336821121473203736761927298018362245182623671888341722264817128641786441614143615372259152324571518145115131461157135214910根据附件2中的数据可知，经开区每个酒店附近日均人流量1500人，公共场所日均人流量一万人，十字路口3000人

17、，地铁出口2万人，社区2000人，在结合题目附录所给的各个租赁点需求量，结合前期建设的30个租赁点，保证每15人一辆自行车，在考虑到调度最优，结合问题一最小生成树算法所得到的最优路径，运用matlab进一步分析可得到每个租赁点具体分配车方案：租赁点自行车数量56403140693950387733603349339132413271329426882581256324432472234723902384216821732076198018451867183417所以，综上所述，共新建自行车租赁点26个，新增自行车697辆，共需花费199.7万元。每辆车平均一次调度花费的时间为：208分钟。问题

18、三的模型：目标：在新增网点后使整个调度在150分钟完成；约束：每辆调度车每次运送的自行车不大于50辆；所以得到模型： s.t模型求解步骤一：根据问题二的结果确定了新增网点的位置，首先用excel进行数据的分析处理，并按照网点间距离大小进行了分类，在处理数据的过程中，我们使用了一些技巧：用名称替换的方法把网点名用序号代替。步骤二：采用最小生成树算法寻找最快调度方案，可以将网点进行分区（相距近的网点为一个分区）来提高调度效率降低时间复杂度，假设需要增加p辆调度车，每辆调度车只在一个分区行驶且各分区相互独立，应用问题一的模型计算各分区的调度时间。步骤三：改变p值重复上述步骤，直到所有分区的调度时间最

19、大值不大于150分钟。网点分区图为：用matlab编程得到的调度方案为：调度车编号1234起点1454836终点20317452调度时间136142138129调度方案为即行车路线为：六、模型的分析和检验：6.1. 模型的检验这三个问题的模型检验均要通过实际的分配调度实现，我们在三个问题中分别应用了不同的算法和软件进行了模型的检验，在问题一中应用floyd算法和matlab程序对该问题进行了求解和检验，在问题二中运用了启发式搜索算法原理对问题进行了检验，在问题三中利用最小生成树算法进行求解和检验以实现上述三个问题的最优性。我们利用模型一得到的自行车分配方案，将各网点的需求量与实际分配量相比较，

20、各网点都能够满足需求，代入约束条件后，符合要求，并且得到的配送路线花费的时间能够使租赁系统正常运行，所以认为模型一比较可靠。模型一自行车的分配需求情况由图可以看出分配值均大于需求值的10%，所有的租赁点都能满足需求，所以，模型是合理的。模型二的新增网点的需求量情况：从图中可以看出三条曲线波动幅度较小，即发生调度的概率较小，而且网点都设置在需求量较大的地方，因此模型二较合理。6.2. 模型的优点优点：最小生成树算法应用比较成熟，模型中将行车时间和装卸时间视为权值，编程通过计算机计算实现，因此可以快速的得出精确的结果。问题1：算法稳定成熟，程序容易实现，结果精确。问题2：具有反馈过程，可以不断的优

21、化调度方案。问题3： 租赁点分区的方法减小了时间的复杂度，是求解过程简单。6.3. 模型的缺点模型求解过程中，获得的各个网点间的距离是根据经纬度计算得到的弧长距离，而实际调度车的路线与街道分布情况一致，这样就会导致求得的调度时间与实际有偏差，因此可根据街道的分布情况计算距离。假设调度始终发生在租车还车之后进行，而实际生活中，两者一般都是同时发生的，所以应该使调度依据实际需要进行来完善模型。七、模型的推广在整个解题过程中，我们都是在理论结合实际的前提下作出各种假设和量化，网点间距离仅根据经纬度计算与实际情况不符，只有确定了街道的实际距离才能精确地计算出调度时间。模型一借助最小生成树法建立，它同样

22、可以推广到其它的运输优化方案和资源配置优化的问题中，但是分配调度模型也有其缺点，编程所得的路径为理想的情况与实际有一定的偏差。八、参考文献【1】肖华勇.实用数学建模与软件应用 西安：西北工业大学出版社 2008.11 【2】曹旭东 数学建模原理与方法 北京：高等教育出版社，2014.1【3】李学文，李炳照，王宏洲 数学建模优秀论文精选与点评. 北京：清华大学出版社 2011.9【4】陈光亭，裘哲勇 数学建模 北京市 高等教育出版社 2010.2九、附录：问题一中求解任意两个网点间距离的结果如下：12345678910111213141510.0 0.4 0.9 1.3 1.1 1.7 2.9

23、2.5 3.2 4.5 1.3 0.7 0.5 0.6 0.2 20.4 0.0 0.6 1.2 1.3 1.7 3.0 2.7 3.3 4.5 1.7 1.0 0.6 0.6 0.6 30.9 0.6 0.0 0.8 1.3 1.4 2.9 2.4 3.0 4.1 2.2 1.6 1.2 1.2 1.1 41.3 1.2 0.8 0.0 0.9 0.6 2.1 1.7 2.2 3.3 2.5 2.0 1.7 1.8 1.4 51.1 1.3 1.3 0.9 0.0 0.9 1.8 1.4 2.2 3.5 1.9 1.7 1.6 1.7 1.1 61.7 1.7 1.4 0.6 0.9 0.0

24、 1.5 1.1 1.6 2.8 2.8 2.4 2.2 2.3 1.8 72.9 3.0 2.9 2.1 1.8 1.5 0.0 0.4 0.7 2.0 3.5 3.4 3.4 3.5 2.9 82.5 2.7 2.4 1.7 1.4 1.1 0.4 0.0 0.8 2.1 3.2 3.1 3.0 3.1 2.5 93.2 3.3 3.0 2.2 2.2 1.6 0.7 0.8 0.0 1.3 4.0 3.9 3.7 3.8 3.2 104.5 4.5 4.1 3.3 3.5 2.8 2.0 2.1 1.3 0.0 5.3 5.1 4.9 5.0 4.5 111.3 1.7 2.2 2.5

25、1.9 2.8 3.5 3.2 4.0 5.3 0.0 0.8 1.2 1.3 1.2 120.7 1.0 1.6 2.0 1.7 2.4 3.4 3.1 3.9 5.1 0.8 0.0 0.4 0.5 0.7 130.5 0.6 1.2 1.7 1.6 2.2 3.4 3.0 3.7 4.9 1.2 0.4 0.0 0.2 0.5 140.6 0.6 1.2 1.8 1.7 2.3 3.5 3.1 3.8 5.0 1.3 0.5 0.2 0.0 0.6 150.2 0.6 1.1 1.4 1.1 1.8 2.9 2.5 3.2 4.5 1.2 0.7 0.5 0.6 0.0 160.3 0.

26、7 1.1 1.3 0.9 1.6 2.7 2.4 3.1 4.4 1.2 0.8 0.7 0.8 0.2 170.9 0.7 0.2 0.6 1.2 1.2 2.7 2.3 2.9 3.9 2.3 1.6 1.3 1.3 1.1 181.1 1.4 1.7 1.5 0.6 1.5 2.1 1.8 2.6 4.0 1.4 1.4 1.4 1.6 1.0 190.9 1.1 1.2 0.9 0.2 1.0 2.0 1.6 2.3 3.6 1.8 1.5 1.4 1.5 0.9 201.3 1.5 1.5 1.0 0.2 0.9 1.6 1.3 2.1 3.4 2.0 1.8 1.7 1.9 1.

27、2 211.7 1.9 1.8 1.2 0.6 0.9 1.2 0.9 1.7 3.0 2.3 2.2 2.1 2.3 1.6 222.0 1.9 1.4 0.7 1.3 0.4 1.7 1.3 1.7 2.6 3.1 2.7 2.4 2.5 2.0 232.1 2.2 1.8 1.1 1.2 0.4 1.2 0.7 1.2 2.3 3.1 2.8 2.6 2.7 2.2 243.0 2.9 2.5 1.8 2.3 1.4 1.9 1.6 1.4 1.8 4.2 3.8 3.5 3.5 3.1 252.7 2.9 2.9 2.4 1.6 1.9 1.0 1.1 1.7 2.9 2.9 3.1

28、3.1 3.2 2.6 262.6 2.8 2.8 2.1 1.5 1.6 0.7 0.8 1.4 2.7 2.9 3.0 3.0 3.2 2.5 272.6 2.8 2.7 2.0 1.5 1.5 0.5 0.5 1.2 2.5 3.1 3.1 3.0 3.2 2.5 284.2 4.3 4.0 3.2 3.1 2.6 1.4 1.7 1.0 0.9 4.9 4.8 4.7 4.8 4.2 290.6 0.8 1.0 1.0 0.5 1.2 2.3 1.9 2.7 3.9 1.6 1.2 1.1 1.2 0.6 303.2 3.3 3.1 2.3 2.1 1.7 0.4 0.7 0.4 1.

29、6 3.8 3.8 3.7 3.8 3.2 16171819202122232425262728293010.3 0.9 1.1 0.9 1.3 1.7 2.0 2.1 3.0 2.7 2.6 2.6 4.2 0.6 3.2 20.7 0.7 1.4 1.1 1.5 1.9 1.9 2.2 2.9 2.9 2.8 2.8 4.3 0.8 3.3 31.1 0.2 1.7 1.2 1.5 1.8 1.4 1.8 2.5 2.9 2.8 2.7 4.0 1.0 3.1 41.3 0.6 1.5 0.9 1.0 1.2 0.7 1.1 1.8 2.4 2.1 2.0 3.2 1.0 2.3 50.9

30、 1.2 0.6 0.2 0.2 0.6 1.3 1.2 2.3 1.6 1.5 1.5 3.1 0.5 2.1 61.6 1.2 1.5 1.0 0.9 0.9 0.4 0.4 1.4 1.9 1.6 1.5 2.6 1.2 1.7 72.7 2.7 2.1 2.0 1.6 1.2 1.7 1.2 1.9 1.0 0.7 0.5 1.4 2.3 0.4 82.4 2.3 1.8 1.6 1.3 0.9 1.3 0.7 1.6 1.1 0.8 0.5 1.7 1.9 0.7 93.1 2.9 2.6 2.3 2.1 1.7 1.7 1.2 1.4 1.7 1.4 1.2 1.0 2.7 0.4

31、 104.4 3.9 4.0 3.6 3.4 3.0 2.6 2.3 1.8 2.9 2.7 2.5 0.9 3.9 1.6 111.2 2.3 1.4 1.8 2.0 2.3 3.1 3.1 4.2 2.9 2.9 3.1 4.9 1.6 3.8 120.8 1.6 1.4 1.5 1.8 2.2 2.7 2.8 3.8 3.1 3.0 3.1 4.8 1.2 3.8 130.7 1.3 1.4 1.4 1.7 2.1 2.4 2.6 3.5 3.1 3.0 3.0 4.7 1.1 3.7 140.8 1.3 1.6 1.5 1.9 2.3 2.5 2.7 3.5 3.2 3.2 3.2 4

32、.8 1.2 3.8 150.2 1.1 1.0 0.9 1.2 1.6 2.0 2.2 3.1 2.6 2.5 2.5 4.2 0.6 3.2 160.0 1.1 0.8 0.7 1.1 1.5 1.9 2.0 3.0 2.4 2.3 2.4 4.1 0.4 3.0 171.1 0.0 1.6 1.1 1.4 1.7 1.3 1.7 2.3 2.8 2.6 2.5 3.8 1.0 2.9 180.8 1.6 0.0 0.6 0.6 0.9 1.9 1.8 2.9 1.6 1.6 1.7 3.5 0.7 2.4 190.7 1.1 0.6 0.0 0.3 0.7 1.4 1.3 2.4 1.8

33、 1.7 1.6 3.3 0.3 2.3 201.1 1.4 0.6 0.3 0.0 0.4 1.3 1.1 2.3 1.5 1.3 1.3 3.0 0.7 1.9 211.5 1.7 0.9 0.7 0.4 0.0 1.3 0.9 2.1 1.1 1.0 0.9 2.6 1.1 1.5 221.9 1.3 1.9 1.4 1.3 1.3 0.0 0.6 1.1 2.2 2.0 1.8 2.6 1.5 1.8 232.0 1.7 1.8 1.3 1.1 0.9 0.6 0.0 1.2 1.7 1.4 1.2 2.2 1.6 1.3 243.0 2.3 2.9 2.4 2.3 2.1 1.1 1

34、.2 0.0 2.7 2.4 2.1 2.1 2.6 1.7 252.4 2.8 1.6 1.8 1.5 1.1 2.2 1.7 2.7 0.0 0.3 0.6 2.3 2.1 1.3 262.3 2.6 1.6 1.7 1.3 1.0 2.0 1.4 2.4 0.3 0.0 0.3 2.1 2.0 1.0 272.4 2.5 1.7 1.6 1.3 0.9 1.8 1.2 2.1 0.6 0.3 0.0 1.9 2.0 0.8 284.1 3.8 3.5 3.3 3.0 2.6 2.6 2.2 2.1 2.3 2.1 1.9 0.0 3.6 1.1 290.4 1.0 0.7 0.3 0.7

35、 1.1 1.5 1.6 2.6 2.1 2.0 2.0 3.6 0.0 2.6 303.0 2.9 2.4 2.3 1.9 1.5 1.8 1.3 1.7 1.3 1.0 0.8 1.1 2.6 0.0 求网点距离的matlab程序代码：dx=ones(30,30);for k=1:1:30 for m=1:1:30 d=distance(w(k),j(k),w(m),j(m); pi=3.1415926; dx(k,m)=d*6371*1000*2*pi/360; endenddx最小生成树算法：1、最小生成树的定义：在一个具有几个顶点的连通图g中，如果存在子图g包含g中所有顶点和一部分边

36、，且不形成回路，则称g为图g的生成树，代价最小生成树则称为最小生成树。2、本文用prim算法实现了生成最小生成树，如下为prim算法：假设g(v，e)是有n个顶点的连通网络，用t=（u，te）表示要构造的最小生成树，其中u为顶点集合，te为边的集合。prim算法的具体步骤描述如下：(1) 初始化：令u= ，te= 。从v中取出一个顶点u0放入生成树的顶点集u中，作为第一个顶点，此时t=（u0， ）；(2) 从uu，vv-e的边（u，v）中找一条代价最小的边（u*，v*），将其放入te中，并将v*放入u中。(3) 重复步骤(2)，直至u=v为止。此时集合te中必有n-1条边，t即为所要构造的最小

37、生成树。上述过程的具体细节如算法见代码所示。3、经过试验测试可以求出此图的最小生成树为：。4、程序运行结果执行结果：5、结论（1）、该程序成功解决了“最小生成树问题”。（2）、根据算法分析出prim算法的复杂度与网的边数无关，适合边稠密网络的最小生成树，但时间复杂度大，程序运行较慢。（3）、kruskal算法仅与网中边数有关，适合于边稀疏网络的最小生成树，在时间复杂度方面小于prim算法，提高程序运行速度。6、程序代码（1）、prim算法：typedef struct /边的存储结构int fromvex,endvex; /边的起点和终点int length; /边的权值edge;edge t

38、n-1; /最小生成树float distnn; /连通网络的带权邻接矩阵void prim(int i) /i表示最小生成树所选取的第一个顶点下标int j,k,m,v,min,max=100000; float d;edge e;v=i; /将选定顶点送入中间变量vfor(j=0;j=v)tj.endvex=j+1;tj.length=distvj+1;elsetj.endvex=j;tj.length=distvj;for(k=0;k=n-1;k+) /求第k条边min=max;for(j=k;j=n-1;j+) /找出最短的边并将最短边的下标记录在m中if(tj.lengthmin)m

39、in=tj.length;m=j;e=tm; /将最短的边交换到tk单元tm=tk;tk=e;v=tk.endvex; /v中存放新找到的最短边在v-u中的顶点for(j=k+1;jn-1;j+) /修改所存储的最小边集d=distvtj.endvex;if(dtj.length)tj.length=d;tj.fromvex=v; /prim算法 2、程序清单：#include #define max_vertex_num 10#define infinity 1000typedef struct edge int weight;edge, edgematrixmax_vertex_numma

40、x_vertex_num;typedef struct mgraph edgematrix edges; int vexnum; int edgenum;mgraph;typedef struct int vertex; int lowcost;closedge;void initializemg(mgraph &g) g.edgenum = g.vexnum = 0; for(int i = 0; i max_vertex_num; +i) for(int j = 0; j max_vertex_num; +j) g.edgesij.weight = infinity;void creategraph(mgraph &g) int i, j; g.vexnum = 6; g.edgenum = 10; g.edges01.weight = g.edges10.weight = 1; g.edges02.weight = g.edges20.weight = 6; g.edges03.weight = g.edges30.weight = 9;g.edges05.weight = g.edges50.weight = 11;