在多约束下求取网络中多条最短简单路径的启发式方法

摘要

本发明公开了一种在多约束下求取网络中多条最短简单路径的启发式方法。该方法使用改进的路径控制性法则和对路径延伸到目的节点后代价下限的预测，丢弃含有环的、违反约束的和代价超过已获得的第k条最短简单路径的路径。在被保留的路径中，以宽度优先的方式和可调的精度搜索符合约束条件的前k条最短简单路径。该方法对于网络的类型、规模及约束程度的变化有很强的适应性，且复杂度接近传统的宽度优先搜索方法。通过设置路径中环的探察深度和受控判决的收放系数，能够在路径的数量、质量和发现路径的能力等方面表现出优异且稳定的性能。