发布时间 : 星期一 文章基于算法本科最新毕业论文更新完毕开始阅读6a4eaa660166f5335a8102d276a20029bd64638e
3.3最小生成树问题(Prim算法、Kruskal算法)
问题描述：设图G=(V，E)是一简单连通图，|V|=n，|E|=m，每条边ei都给以权wi，wi假定是边ei的长度（其他的也可以），i=1，2，3，?，m。求图G的总长度最短的树。
3.3.1 Kruskal算法
编码原理：首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接两个不同的连通分支：当查看到第k条边(v，w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2中的顶点时，就用边(v，w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。此时，这个连通分支就是G的一棵最小生成树。
Kruskal算法的基本思想是：首先将赋权图G的边按权的升序排列，不失一般性为：e1，e2，?，em。其中Wi≤Wi+1，然后在不构成回路的条件下择优取进权最小的边。
其流程如下：
（1）对属于E的边进行排序得e1≤e2≤?≤em。 （2）初始化操作w←0，T←￠，k←0，t0； （3）若t=n-1，则转(6)，否则转(4) （4）若构成一回路，则作[k←k+1，转(4)] （5）T←，w←w+wR，t←t+1，k←k+1，转(3) （6）输出T，w停止
下面我们对这个算法的合理性进行证明：
设在最小树中，有边 优点：当输入的连通带权图有e条边时，则将这些边依其权组成优先队列需要O(e)时间，在上述算法的while循环中，DeleteMin运算需要O(loge)时间，因此关于优先队列所作运算的时间为O(eloge)。实现UnionFind所需的时间为O(eloge)或 O(elog*e)。所以Kruskal算法所需的计算时间为O(eloge)。 缺点：当e=Ω(n2)时，Kruskal算法比Prim算法差，但当e=O(n2)时，Kruskal算法却比Prim算法好得多。Kruskal算法的时间主要取决于边数。它较适合于稠密图。 3.3.2 Prim算法 Kruskal算法采取在不构成回路的条件下，优先选择长度最短的边作为最小树的边，而Prim则是采取了另一种贪心策略。 编码原理：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jv-s，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 已知图G=(V，E)，V={v1，v2，v3，?，vn}，D=(dij)n*n是图G的矩阵，若 Prim算法的基本思想是：从某一顶点（设为v1）开始，令S←{v1}，求与S中点与S中点v1距离最短的点，即从矩阵D的第一行元素中找到最小的元素，设为dij，则令S←S∪{vj}，继续求vs中点与s的距离最短的点，设为vk，则令S←S∪{vk}，继续以上的步骤，直到n个顶点用n-1条边连接起来为止。 流程如下： （1）初始化操作：T←￠，q(1)←-1，i从2到n作[p(i)←1，q(i)←di1]， k←1； （2）若k≥n，则作[输出T，结束] 否则作[min←∞，j从2到n作 [若0 [min←q(i)。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。 4.2 贪心选择策略 假设原问题为T，而我们已经知道了某个最优服务系列，即最优解为A={t(1)，t(2)，?．t(n)}(其中t(i)为第i个用户需要的服务时间)，则每个用户等待时间为： T(1)=t(1)；T(2)=t(1)+t(2)；...T(n)：t(1)+t(2)+t(3)+??t(n)； 那么总等待时问，即最优值为： TA=n*t(1)+(n-1)*t(2)+?+(n+1-j)*t(i)+?2*t(n-1)+t(n)； 由于平均等待时间是n个顾客等待时间的总和除以n，故本题实际上就是求使顾客 等待时间的总和最小的服务次序。 本问题采用贪心算法求解，贪心策略如下：对服务时间最短的顾客先服务的贪心选择策略。首先对需要服务时间最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n-1个顾客服务的新问题T’。新问题和原问题相同，只是问题规模由n减小为n-1。基于此种选择策略，对新问题T’，选择n-1顾客中选择服务时间最短的先进行服务，如此进行下去，直至所有服务都完成为止。 4.3 问题的贪心选择性质 先来证明该问题具有贪心选择性质，即最优服务A中t(1)满足条件：t(1)<=t(i)(2 用反证法来证明：假设t(1)不是最小的，不妨设t(1)>t(i)(i>1)。 设另一服务序列B=（t(i)，t(2)，?，t(1)?，t(n)） 那么TA-TB=n*[t(1)-t(i)]+(n+1-i)[t(i)-t(1)]=(1-i)*[t(i)-t(1)]>0 即TA>TB，这与A是最优服务相矛盾。 故最优服务次序问题满足贪心选择性质。 4.4 问题的最优子结构性质 在进行了贪心选择后，原问题T就变成了如何安排剩余的n-1个顾客的服务次序的问题T’，是原问题的子问题。 若A是原问题T的最优解，则A’={t(2)，?t(i)?t(n))是服务次序问题子问题T’的最优解。 证明：假设A’不是子问题T’的最优解，其子问题的最优解为B’，则有TB’ 从以上贪心选择及最优子结构性质的证明，可知对最优服务次序问题用贪心算法可求得最优解。 根据以上证明，最优服务次序问题可以用最短服务时间优先的贪心选择可以达到最优解。故只需对所有服务先按服务时间从小到大进行排序，然后按照排序结果依次进行服务即可。平均等待时间即为TAn。 4.5 算法结果分析 程序主要是花费在对各顾客所需服务时间的排序和贪心算法，即计算平均服务时间 上面。其中，贪心算法部分只有一重循环影响时间复杂度，其时间复杂度为O(n)：而排序在这里采用希尔(Shel1)排序，其时间复杂度为O(nlogn)。因此，综合来看算法的时间复杂度为O(nlogn)。