最短路径问题实验报告

1、徐州工程学院管理学院实验才艮告实验课程名称：最短路径问题实验地点：南主楼七楼机房经济管理实验中心2015年5月至2015年6月实验报告实验项目：B15201302实验学时：8学时实验日期：2015/5-2015/6实验要求：通过对求最短路径方法的梳理，运用其中一种方法解决一个实际问题实验内容：案例分析最短路径几种算法的比较蚁群算法蚁群算法的基本原理可大致描述如下。蚂蚁属于群居昆虫，个体行为极其简单，而群 体行为却相当复杂。相互协作的一群蚂蚁很容易找到从蚁穴到食物源的最短路径，而单 个蚂蚁则不能。人们通过大量的研究发现,蚂蚁之所以可以做到这一点，是因为蚂蚁个体 之间是通过在其所经过的路径上留下一

2、种可称之为信息素的物质来进行信息传递。蚂蚁 可以嗅到这种信息素，而且可以根据信息素的浓度来指导自己对前进方向的选择。同时, 该信息素会随着时间的推移逐渐挥发掉，于是路径的长短及该路径上通过的蚂蚁的多少 就对残余信息素的强度产生影响。反过来信息素的强弱又指导着其它蚂蚁的行动方向。 因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁 群体行为表现出的一种信息正反馈现象。蚂蚁个体之间就是通过这种信息交流达到快速 找到食物源或蚁穴的。蚁群算法就是受这种行为启发，以人工蚂蚁模拟真实蚂蚁行为来 求解组合优化问题，到目前为止，人们已经用它成功地解决了 TSP、JSP等许多组合优化

3、 问题。用基本蚁群算法（基于Ant quantity模型）求解最短路径问题的过程就是：将m只蚂 蚁放到起点s处，每只蚂蚁将根据一定的概率选择下一个与此交叉点直接相邻的交叉 点。蚂蚁k从s点出发，按照选择策略，从与s相关联的边的集合中，选择一条边。然后， 按照一定的方式更新这条边上的信息素浓度。接着再从这条边的另一节点T开始，从与 T相关联的边的集合中，选择另一条边。以此类推，直到搜索到终点D。于是，蚂蚁k得 到一个从s到D的解。直到所有的m只蚂蚁都搜索完毕后，得到m个解（包括重复的）。 继续迭代直到满足停止条件，停止条件为最大迭代次数。在所求得的所有解中，值最小的 解为所求的全局最优解,即最短

4、路径的长度。遗传算法遗传算法抽象于生物体的进化过程，是一种通过全面模拟自然选择和遗传机制，形 成具有“生成+检验”特征的搜索算法.遗传算法以编码空间代替问题的参数空间，以适 应度函数为评价依据，以编码群体为进化基础，以对群体中个体位串的遗传操作实现选 择和遗传机制，建立起一个迭代过程。在这一过程中,通过随机重组编码位串中重要的基 因，使新一代的位串集合优于老一代的位串集合，群体的个体不断进化，逐渐接近最优 解，最终达到求解问题的目的。遗传算法的运行过程为一个典型的迭代过程，其必须完成 的工作内容和基本步骤如下：（1）选择编码策略，把参数集合X和域转换为位串结构空间S ；（2）定义适应值函数f

5、（x）；确定遗传策略，包括选择群体大小，选择、交叉、变异方法，以及确定交叉概率P、c 变异概率P等遗传参数；随机初始化生成群体P ;计算群体中个体位串解码后的适应值f 3);按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；判断群体性能是否满足某一指标，或者已完成预定迭代次数，不满足则返回步骤6, 或者修改遗传策略再返回步骤6。通过比较遗传算法属于智能算法能切合实际的解决选址问题。因此下面对遗传算法进行 详细说明、应用。一 一皆壮Floyd算法Floyd算法主要用于计算所有节点对之间的最短路Floyd算法是通过权矩阵计算来 实现的一种方法，其主要思想是从代表任意两个节点V到V距

6、离的带权邻接矩阵D(o)开 i j始，首先计算D，即计算V到V .经过一次经转的所有可能路径,经过比较后选出最短路, 代替D(0)中对应的路径，迭代列/出距离矩阵D，D中各元素表示通过一次迭代后网络 中任意两点间最短路，也即网络中任意两点之间直接到达或只经过一个中间点时的最短 路.在此基础上依次计算D(2),D(3),D(k),D(k)中对应的元素表示任意两点间不经过中间 点或最多允许经过2k -1个中间点时的最短路。当D5 = D(k)时,表明得到的带权邻接矩 阵D(k)就反映了所有顶点对之间的最短距离信息，成为最短距离矩阵.其算法(记为算法 1)如下：第一步，作初始距离矩阵D (o) =

7、(d(o)，其中： d(0)=眨相邻对= 1,2,3,)； j 很不相邻或无路时第二步,构造迭代矩阵D(k)= (djo),其中： d(k)= min td(k-1)+ d(si)|r = l,2, .,n； 第三步，若D；+i)= D(. k)，迭代终止.否则，返回第二步。对Floyd算法进行分析，不难发现在不含负回路的网络中存在以下问题：在计算两点V和V之间最短路时,每次都要计算n次加法，且插入的中间节点 V很明显不能使路长变短，降低了计算效率1；r若要找出点V、V间的最短路，则要回头去查是如何计算出匕的，不妨设 d (k) = d (k-1) + d (k-1),同样再去查d (k-1)

8、、d (k -1)是如何算出的，一直查到D (0)中的元素为 止,才能找出所求最短路.显然上述寻找最短路径的方法不直观、比较繁琐.基于这两点 不足,本文在不含负回路的网络中对Floyd算法进行了优化，不仅简化了计算量，而且使 得在寻找最短路径时更简洁方便。既然原始的Floyd算法存在一些问题，则本文对Floyd算法进行优化具体思路如下：对于问题(1),构造迭代矩阵D (k) = (d；k),计算两点匕和V之间最短路时，对待插入 的节点V先进行路长比较，如果d(k-1) d(k-1)或d(k-1) d(k-1)，则说明插入节点V后，点ririjriijrV经过节点V到达点V的路长不会比原来的短，

9、于是不用再计d(k-1)+ dk-1,进入下一个irjirrj节点的搜索。对于问题(2),构造一个序号矩阵A(k)= (ak) , (k = 0,1,)，记录算法第二步中第k次迭 ij代插入节点的情况.优化后的Floyd算法(记为算法2)如下： 第一步，作初始距离矩阵D(0) = (d(o)和序号矩阵A(0) = (afo)，其中:d(0)=ij1W对，(i,j=i；3,),S，i, j不相邻或无路时/(i,j = 1,2,n)，10, i,j相邻时a(0) =一, ，i 中，i, j不相邻或无路此时距离矩阵D(0)中的元素d(0)表示任意两点v、V不经过其它节点的路长。 iji j第二步，构

10、造迭代矩阵d (k)=皿)和序号矩阵A(0) = a)。对于迭代矩阵D(k)的元素d (k) : r从1到n ,且r。i, j时，如果d(k-1) d(k-1)或d(k-1) d(k-1),说明插入点V后路长d(k-1)不会变短，此时无须计算d(k-1) + dk-1。否则 riijfr ijirrjd (k) = min d (k-1), d (k-1) + d (k-1) J。相应地，序号矩阵A(k)的各元素变化为：若d(k) = d(k-1) + d(k-1),且d(k-1) d(k-1)，则记下点匕，并在序号矩阵中A(k)对应的元素a(k)变为： ja (k) = a (k-1), V

11、, a (k-1) 。表明经过该次迭代后从节点V出发到节点V的最短路长经过节点匕路长变短.否则,a(k) = a(k-1)。 ij ij第三步，若D(k+1) + D(k),迭代终止.否则，返回第二步。针对以上算法本文用改进后的Floyd算法利用Matlab编程对实例进行试验。实例已知网络如图1所示，计算所有节点之间的最短路。vvvvv12345v 013881v801252v280483v818024v83880由图可以得到个点间的距离矩阵:5列如求节点七到节点七之间的最短路径和最短距离可用Matlab编程Floyd算法代码如下:function D,R=floyd(a)n=size(a,1);D=afor i=1:nfor j=1:nR(i,j)=j;endendRfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendkDREnd可求得节点v到节点v之间的最短路径为v T v T v T v最短距离为5。151245参考文献1林华珍，周根贵.求解最短路问题的一种优化矩阵算法J.长江大学学报：自然科学 版(理工卷)，2007 4 (4 ): 14-16实验总结采用优化的R