| 主权项 |
在多约束下求取网络中多条简单路径的启发式方法，其特征在于包含以下2个主要步骤：反向路径代价预测：当路由请求具有m个约束条件时，使用Dijkstra算法m次，依次基于每个约束条件对应的代价分量计算目的节点D至其它节点路径的代价下限，从网络拓扑图中删除该代价下限的数值超过约束上限的节点以及通往这些节点的链路；计算基于单个代价分量得到的m条源节点S与目的节点D之间的最短路径的归一化非线性代价；取其中前k个符合约束路径的代价按照递增顺序排队，记为D的代价队列lmax[1]，...，lmax[k]，其中相同路径的代价只记一次，代价个数不足k时用1补充队列末尾的所有空位；将队列中的第k个数值lmax[k]作为有可能成为前k条最短简单路径的有效路径的归一化非线性代价上限；正向路径计算：将所有与源节点S直接相邻的节点列表中的第1条路径放入已经发现的全部路径的集合Q中；从Q中选取归一化非线性代价下限的预测值最小的一条路径P(S→u[i])，其中，归一化非线性代价下限的预测值被定义为，源节点S到节点u的m个代价分量wr(S→u[i])(r＝1，...，m)与节点u到目的节点D的m个反向预测代价分量下限预测值wr‑pre(u→D)(r＝1，...，m)分别相加并作归一化非线性合并后的数值；判断这条路径延伸到其末尾节点的所有邻接节点后的新路径P(S→u[i]→v)的有效性，其中，判断路径有效性的过程包括以下步骤：判断末端延伸到节点v后的新路径P(S→u[i]→v)的归一化非线性代价下限的预测值是否仍然小于lmax[k]；判断路径P(S→u[i]→v)末尾是否存在环；判断路径P(S→u[i]→v)与末尾节点v列表中路径之间的控制状况；若该新延伸路径被确认为含有环的、代价分量不符合约束条件的或归一化非线性代价下限的预测值超过lmax[k]，则将其丢弃，反之，使用该有效路径更新节点v的路径列表，若v为目的节点D，更新D的路径代价队列；重复执行从Q中选取路径的循环，直到Q中全部的有效路径都已经被选取完毕。 |
