Misra Sudip, Oommen B John
School of Computer Science, Carleton University, Ottawa, ON, Canada.
IEEE Trans Syst Man Cybern B Cybern. 2005 Dec;35(6):1179-92. doi: 10.1109/tsmcb.2005.850180.
This paper presents the first Learning Automaton-based solution to the dynamic single source shortest path problem. It involves finding the shortest path in a single-source stochastic graph topology where there are continuous probabilistic updates in the edge-weights. The algorithm is significantly more efficient than the existing solutions, and can be used to find the "statistical" shortest path tree in the "average" graph topology. It converges to this solution irrespective of whether there are new changes in edge-weights taking place or not. In such random settings, the proposed learning automata solution converges to the set of shortest paths. On the other hand, the existing algorithms will fail to exhibit such a behavior, and would recalculate the affected shortest paths after each weight-change. The important contribution of the proposed algorithm is that all the edges in a stochastic graph are not probed, and even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the shortest path graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. All the algorithms were tested in environments where edge-weights change stochastically, and where the graph topologies undergo multiple simultaneous edge-weight updates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally established. The algorithm can be applicable in domains ranging from ground transportation to aerospace, from civilian applications to military, from spatial database applications to telecommunications networking.
本文提出了首个基于学习自动机的动态单源最短路径问题解决方案。该方案涉及在单源随机图拓扑结构中寻找最短路径，其中边权重存在连续的概率更新。该算法比现有解决方案显著更高效，可用于在“平均”图拓扑结构中找到“统计”最短路径树。无论边权重是否有新变化，它都能收敛到该解决方案。在这种随机设置下，所提出的学习自动机解决方案收敛到最短路径集合。另一方面，现有算法无法表现出这种行为，并且在每次权重变化后都会重新计算受影响的最短路径。所提出算法的重要贡献在于，随机图中的所有边并非都被探测，即便被探测，也并非被同等频繁地探测。实际上，该算法几乎总是尝试仅探测那些将包含在最短路径图中的边，而对其他边进行最少次数的探测。这提高了所提出算法的性能。所有算法都在边权重随机变化且图拓扑结构经历多次同时边权重更新的环境中进行了测试。与现有算法相比，其在处理节点的平均数量、扫描边的数量以及每次更新操作的时间方面的优越性通过实验得到了证实。该算法可应用于从地面运输到航空航天、从民用应用到军事、从空间数据库应用到电信网络等多个领域。
