最短路径问题实验报告.doc

徐州工程学院管理学院实验报告实验课程名称 ： 最短路径问题 实验地点： 南主楼七楼机房经济管理实验中心 2015 年 5 月至 2015 年 6 月 实验报告实验项目：B15201302实验学时： 8 学时实验日期：2015/5-2015/6实验要求：通过对求最短路径方法的梳理，运用其中一种方法解决一个实际问题实验内容：案例分析最短路径几种算法的比较蚁群算法蚁群算法的基本原理可大致描述如下。蚂蚁属于群居昆虫,个体行为极其简单,而群体行为却相当复杂。相互协作的一群蚂蚁很容易找到从蚁穴到食物源的最短路径,而单个蚂蚁则不能。人们通过大量的研究发现,蚂蚁之所以可以做到这一点,是因为蚂蚁个体之间是通过在其所经过的路径上留下一种可称之为信息素的物质来进行信息传递。蚂蚁可以嗅到这种信息素,而且可以根据信息素的浓度来指导自己对前进方向的选择。同时,该信息素会随着时间的推移逐渐挥发掉,于是路径的长短及该路径上通过的蚂蚁的多少就对残余信息素的强度产生影响。反过来信息素的强弱又指导着其它蚂蚁的行动方向。因此,某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现出的一种信息正反馈现象。蚂蚁个体之间就是通过这种信息交流达到快速找到食物源或蚁穴的。蚁群算法就是受这种行为启发,以人工蚂蚁模拟真实蚂蚁行为来求解组合优化问题,到目前为止,人们已经用它成功地解决了、等许多组合优化问题。用基本蚁群算法(基于模型)求解最短路径问题的过程就是:将只蚂蚁放到起点处,每只蚂蚁将根据一定的概率选择下一个与此交叉点直接相邻的交叉点。蚂蚁从点出发,按照选择策略,从与相关联的边的集合中,选择一条边。然后,按照一定的方式更新这条边上的信息素浓度。接着再从这条边的另一节点开始,从与相关联的边的集合中,选择另一条边。以此类推,直到搜索到终点。于是,蚂蚁得到一个从到的解。直到所有的只蚂蚁都搜索完毕后,得到个解(包括重复的)。继续迭代直到满足停止条件,停止条件为最大迭代次数。在所求得的所有解中,值最小的解为所求的全局最优解,即最短路径的长度。遗传算法遗传算法抽象于生物体的进化过程,是一种通过全面模拟自然选择和遗传机制,形成具有“生成+检验”特征的搜索算法.遗传算法以编码空间代替问题的参数空间,以适应度函数为评价依据,以编码群体为进化基础,以对群体中个体位串的遗传操作实现选择和遗传机制,建立起一个迭代过程。在这一过程中,通过随机重组编码位串中重要的基因,使新一代的位串集合优于老一代的位串集合,群体的个体不断进化,逐渐接近最优解,最终达到求解问题的目的。遗传算法的运行过程为一个典型的迭代过程,其必须完成的工作内容和基本步骤如下：（1）选择编码策略，把参数集合和域转换为位串结构空间；（2）定义适应值函数；6（3）确定遗传策略,包括选择群体大小,选择、交叉、变异方法,以及确定交叉概率、变异概率 等遗传参数;（4）随机初始化生成群体;（5）计算群体中个体位串解码后的适应值;（6）按照遗传策略,运用选择、交叉和变异算子作用于群体,形成下一代群体;（7）判断群体性能是否满足某一指标,或者已完成预定迭代次数,不满足则返回步骤6,或者修改遗传策略再返回步骤6。通过比较遗传算法属于智能算法能切合实际的解决选址问题。因此下面对遗传算法进行详细说明、应用。算法算法主要用于计算所有节点对之间的最短路算法是通过权矩阵计算来实现的一种方法,其主要思想是从代表任意两个节点到距离的带权邻接矩阵开始,首先计算,即计算到经过一次经转的所有可能路径,经过比较后选出最短路,代替中对应的路径,迭代列出距离矩阵,中各元素表示通过一次迭代后网络中任意两点间最短路,也即网络中任意两点之间直接到达或只经过一个中间点时的最短路.在此基础上依次计算中对应的元素表示任意两点间不经过中间点或最多允许经过个中间点时的最短路。当时,表明得到的带权邻接矩阵就反映了所有顶点对之间的最短距离信息,成为最短距离矩阵.其算法(记为算法1)如下：第一步,作初始距离矩阵,其中:；第二步,构造迭代矩阵,其中:；第三步,若,迭代终止.否则,返回第二步。对算法进行分析,不难发现在不含负回路的网络中存在以下问题:（1）在计算两点和之间最短路时,每次都要计算次加法,且插入的中间节点很明显不能使路长变短,降低了计算效;（2）若要找出点、间的最短路,则要回头去查是如何计算出的,不妨设,同样再去查、是如何算出的,一直查到中的元素为止,才能找出所求最短路.显然上述寻找最短路径的方法不直观、比较繁琐.基于这两点不足,本文在不含负回路的网络中对算法进行了优化,不仅简化了计算量,而且使得在寻找最短路径时更简洁方便。既然原始的算法存在一些问题，则本文对算法进行优化具体思路如下：对于问题(1),构造迭代矩阵,计算两点和之间最短路时,对待插入的节点先进行路长比较,如果或,则说明插入节点后, 点经过节点到达点的路长不会比原来的短,于是不用再计,进入下一个节点的搜索。对于问题(2),构造一个序号矩阵，记录算法第二步中第次迭代插入节点的情况.优化后的算法(记为算法2)如下:第一步，作初始距离矩阵和序号矩阵，其中：，此时距离矩阵中的元素表示任意两点、不经过其它节点的路长。第二步,构造迭代矩阵和序号矩阵。 对于迭代矩阵的元素: 从1到,且时,如果或,说明插入点后路长不会变短,此时无须计算。否则。 相应地,序号矩阵的各元素变化为:若,且,则记下点,并在序号矩阵中对应的元素变为:。表明经过该次迭代后从节点出发到节点的最短路长经过节点路长变短.否则, 。第三步,若,迭代终止.否则,返回第二步。针对以上算法本文用改进后的算法利用编程对实例进行试验。实例 已知网络如图1所示，计算所有节点之间的最短路。图1由图可以得到个点间的距离矩阵：列如求节点到节点之间的最短路径和最短距离可用编程算法代码如下：function D,R=floyd(a)n=size(a,1);D=afor i=1:n for j=1:n R(i,j)=j; endendRfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end k D REnd可求得节点到节点之间的最短路径为最短距离为5。参考文献1林华珍，周根贵.求解最短路问题的一种优化矩阵算法J.长江大学学报:自然科学版(理工卷), 2007 4 (4 ): 14-16实验总结采用优化的算法，由于在计算路长之前先进行了比较，那些不和节点对直接相连的插