ID 原文 译文
26135 实验表明，VNP-SVNME 算法的资源映射开销相对ILP 仅平均高 15% ，且优于现有的启发式可生存算法。 Experiments show that the resource mapping cost of the VNP-SVNME algorithm is only 15% higher on average than the optimal solution, but it is better than the state-of-the-art heuristic．
26136 此外，VNP-SVNME 算法的映射时间相对 ILP 大大降低，可以满足在线虚拟网络映射的需求。 In addition, the time complexity is greatly reduced compared to ILP, which can meet the requirements of on-line virtual network mapping．
26137 在一个时间窗口网络中寻找前 k 条最短路径是一项具有挑战性的任务。 It is a challenging task to find the k shortest paths in a time-window network．
26138 在时间窗口网络中，一个节点可能只有在某些特定的时间窗口内才能通行。 A node may only be accessible within some specific time windows．
26139 现有的研究大都假设运动体可以立即通过可通行节点，或者在暂不可通行节点处等待直到未来时间窗口的开始时刻才通过。 In the existing researches, an assume is made that a traveller can pass through an accessible node immediately or wait until the next accessible time window．
26140 本文针对一个更一般的时间窗口情况，其中运动体一旦到达节点，可以选择在节点的时间窗口中的任何离散时刻通过该节点。 This paper targets a more general case where a traveller, once arrived at a node, may choose to pass through the node at any discrete times in the time windows of the node．
26141 本文将这样的时间窗口网络称为拓展时间窗口网络，其解空间大小和复杂程度都显著增加。 In such a generalized time-window network, the complexity increases significantly, as the size of solution space soars up exponentially．
26142 通过模拟水面上的自然涟漪扩散现象，本文提出了一种有效的涟漪扩散算法，用于求解拓展时间窗口网络中的前 k 条最短路径。 By imitating the natural ripple-spreading phenomenon on a liquid surface, an effective ripple-spreading algorithm (ＲSA) is proposed for the k shortest paths problem in a generalized time-window network (k-SPPGTW)．
26143 除了一对一问题之外，涟漪扩散算法(ripple spreading algorithm，ＲSA)还扩展到一对多问题．在一对多问题中，需要找到从给定起点到网络中的每个其他节点的所有前 k 条最短路径。 Besides one-to-one k-SPPGTW, the ＲSA is also extended to one-to-all k-SPPGTW, where all the k shortest paths from a given source to every other node in the network need to be found．
26144 新方法具有最优性的理论保证，其计算复杂度仅为 O(k × NATU× NL)，其中 NL是网络中链接的数量，NATU是涟漪通过链接平均所需的仿真时间单位数。 The new method has a theoretically guaranteed optimality. The computational complexity of the ＲSA is O(k × NATU× NL), where NLis the number of links in the network, and NATUis the average simulated time units for a ripple to travel through a link．