混合步长网络漫游最短路算法.pdfVIP

混合步长网络漫游最短路算法 孔造杰 (河北工业大学工商管理系t300130) 摘要 本文就作者所提出的同络量短路问曩的一种新算法——混合步长丽络疆游{蚩 进行了研究，探讨丁该方法的原理、算法和特点，并就谈法的手工表上作业进行了实倒 演行．量后提出了作者要进一步解丧的问题． 关奠词量短格，同缚，算涛K O引言 阿络最短路问题一直是网络理论与实践的重要研究课题之一，是在工农业生产及各项 经济活动中非常具有实用价值的一门计算技术，是系统工程和运筹学研究的一个重要分枝。 随着图不断发展与完善和计算技术、计算手段的不断进步，为新的网络最短路算法的研究提 供了前提和条件。经过深人的研究探索和实践，本文提出一种任意路权网络最短路的新算法 ——混台步长网络漫游法。 l网络漫游法原理 在一给定的任意路权网络图D=(v，A，W)中，矿为该网络的点集合。^为该网络的弧 集合，Ⅳ为网络各板的权数集合。确定一个点n∈y作为漫游网络的起点，并记该点的漫游 路长为零砰一o，其余各点的漫游路长口=。o，以此作为初始状态。之后，每一步都以当前漫 游点的路长来修正其余相关连点的路长，并选择一个新的提游点，如此往复，直至不再有可 以漫游的点为止。若从起始点n到任意点。』的直接路长为w。∈W，J一1，2，…，p(p为网络 的顶点数，项两点之间没有直接的强连接，则W。一c,o)，则以w，，修改各点的初始漫游路长， 以=t／J。作为第一步各点的漫游路长，并选择min∽}所对应的点作为第一步的漫游点，称之 为当前漫游点．一般而言，经过^步漫游到达第i点(iEV)，则第i点为当前漫游点，该点的 当前提游路长为露。为寻找下一步的漫游点，要计算一“=群十m，，并以口”=min{衅， 循环，宣至各能够到达的点均已漫游过且各点已不存在更短的漫游路长时，漫游终止。同时 得到了从起如点到各点的最短路。 2网络漫游法的特点 2．I混合步长 每次从当前漫游点i寻找下漫游点时，采用了算式mln{露,l?-i-wⅡ)(j≠i)，所以，下一漫 ]盯虿丽嚣冈国e—————————————一 212 第三居中国青年蠡筹与管理学者大会论文集 游点的路长不只是第k+1步中的最短路，而且是在第k+1步、第^步、…、第l步、第O步 中的最短路，是当前步长内所有步数能够到达该点的最短路。 2．2路长递藏性 由于采用了算式口“：rain{e，砖+”。，}作为第j点的第^+l步的步长，它小于等于k J 步之内任一步长的路长，具有递减性。 2．3条件记忆性 由第^步的当前漫游点寻找下一漫游点时，是在除当前点之外的其它点中寻找。其余的 点分为阻类，一类是还没有漫游过的点、它自然属于寻找的范围；另一类是已经漫游过的点， 这类点分为两种情况，其一是该点记录的^+1步步长之内的最短路值是该点作为漫游点耐 的路长，则该点不在寻找之列，即该点已漫游过这件事是在记忆之中的，其二是该点虽然已 漫游过，但在其后的授游中更新了该点漫游的路长值，剐该点在寻找范围之列，即对该点漫 游过这一事实失去记忆，如同没有漫游过的点一样。也就是说，若该点作为漫游点时的路长 值一址保持为该点的最短漫游路长，则对该点保持记忆；若该点作为漫游点时的路长值已发 生变化，列对该点的漫游失去记忆。 3网络漫游法的算法 对于给定的任意路权网络，按照如下步骤进行网络攫游，只要网络中不古负回路，最终 总可以求褥从起始点到其所能到达的所有点的最短路。当然，也可以从终点q反向漫游，以 求得从罔终的任意一点到终点n的最短路。 3．1■定漫*起始状态 若求从某点矾到其它各点的最短路，则以％作为漫游的起始点(当前漫游点)，并记该 点的起始爰游路长为零，其余各点的漫游路长为无穷大(注：若求其它各点到终点Ⅵ的最短 路，尉以q作为攫游起点，进行反向漫游即可)。 3．2从当前爱游点向外探索 计算从当前漫游点走到其它各点所产生的路长才“一C+m，，j一1，2，…，i一1，i+1， 。一，P· 3．3确定各点新的漫游路长 梅各点的，{“与其当前的最短路长砖进行比较．选取较小者作为该点新的漫游路长， 即片”=nin{C，一“}． 3．4作漫游标记 当从奉漫游点向外探索之后则对其作一标记，表示此点已漫游过。在以后的漫游中保持