Papers

ibaraki1973

最早的研究文献之一

提供了几种算法, 没仔细看的时候没看懂, 但在第三篇文献 RNDM2015 中提到这些算法是 类似BFS的全局搜索(被RNDM2015嫌弃了一番)

andrade2013

用 IP 作为主要方法求解

文中描述了两个松弛:

• 其中最基本的方法 (模型 Q, 基于多次迭代添加消环路径, p2380) 和 commit ac35305 中的算法完全一致
• 其中第二个模型(Q2) 仔细看之后仍然没看懂, 考虑到文章中的结果表明Q2 不如 Q3, 暂时不管 Q2 了
• 第三个模型(Q3) 用对偶变量进行成环约束. 在 RNDM2015 中也应用了此模型, 看上去可能是对的, 并可以彻底解决模型 Q 在多次迭代时, 速度慢的问题. 应该进一步测试.
  • 实测(commit a60e3e2) 发现由于增加了大量约束条件, 这个模型的表现与 Q 相当, 具体结果依赖成环迭代的次数.

RNDM2015

研究的是 protected path, 即有一条 backup 路径 q 的最短路径 p, p q 节点不相交(node-disjoint).

注意到这个约束比复赛只要求边不相交要更严格. (复赛题目结合 Multi-graph 可能会有两条路径恰好使用 相同顶点的两条不同边 的情况出现)

不过另一方面, 复赛要求两条路都过一些指定点. 并且除了找到路, 还要求最短路径和.

文中用 IP method 作为正对照, 研究了几种启发式搜索算法的效率和速度.

• 在文中作者提到了我们初赛中使用的 V'-based 压缩算法. (SK66 & SK, p122)

  • 但文中的 SK66 与我们压缩后用 DFS 不同, 用启发式, 每次增加一个最小路径节点.
  • p122 III B 中, 作者阐述的算法 SK 有必要进行尝试. SK 的要点:
    • 压缩
    • DP

• 作者最后给出的最佳启发式算法是 ABSK. 他们认为这个算法比起 IP method (CPLEX) , 虽然牺牲了求解质量(即有部分题目解不出, 解的质量如何还没仔细看). 但在 运算速度 上有很大的提升.

• 作者提到 IP method 在没有解的时候表现很差, 这点需要进一步测试.

Martins1998

集中讨论了 K shortest loopless paths.

在第 3 节给出了 The tree of K shortest loopless paths 的描述.

需要分析一下本文给出的算法复杂度和我们目前实现的算法复杂度.

BTW: 在此题中, 如果时间注定不够, 或者找第 N 条路成为决速步, 我们也许可考虑不再按权排序, 而是考虑把路径树变成每条路都和前面的路都有减少的边 /点(似乎这对于边来说是显然的, 不必太考虑了...)