张 品;李乐民;王 晟
电子学报. 2003, 31(12): 1861-1865.
本文基于模糊数学的有关原理,论述了网络环境不确定的条件下路由问题的求解.本文假定网络链路延迟是模糊数,给出了路径延迟小于端到端延迟约束的可信度的定义,提出了路径可信度判定(Path Reliability Decision:PRD),最优可信度路由(Most Optimal Reliability Path:MORP),最优路径分解(Path Optimal Partition:POP),及最优分解路径(Most Optimal Partition Path:MOPP)等问题.本文证明,PRD是多项式可解的,POP可以用等可信度分解实现,一般情况下,MORP和MOPP是等价的.在所有链路延迟的宽度都相同时,MORP转化为约束为跳数的最短路径问题,因此是多项式可解的.最后我们给出了MORP的近似算法,算法的时间复杂度为O(log(ε)-1(vlog(v)+e)).