Aug, 2023

最紧代理可接受最短路径

PDF
TL;DR在加权有向图中解决最短路径问题时，考虑边权重计算时间以及与权重不确定性的关系可以提高性能。通过建立在加权有向图的通用框架上，引入了找到最紧适应最短路径（TASP）的问题，该路径在最优成本的上界上最紧缩，实现了对有界不确定性的最短路径问题的泛化，其中可以用计算成本代替边权重的不确定性。我们提出了一个完整的算法来解决 TASP，并对解决方案的质量进行了保证。实证评估支持这种方法的有效性。
shortest path problemaiedge-weight computation timeweighted directed graphstightest admissible shortest path
发现论文，激发创造
  • 具有多个边成本估计的图的最短路径问题的推广

    本文提供了一种面向带权有向图的广义框架，可以计算（估算）多次边权重，并以不同准确性和运行时开销进行优化，从而提出了一个最短路径问题的广义形式。我们介绍了该问题的一个完整的任何时刻的解法算法，并在实验中证明了其有效性。

    Aug, 2022

  • 在线部分监督下的最短路径问题

    研究了在线最短路径问题及其各种监控模型，在加权有向无环图中寻找一条路径以使其对应的边权和尽可能小。提出了一种算法，将累积损失最小化，并介绍了其应用于包交换网络中路由的模拟结果。

    Apr, 2007

  • 带有对手可变成本的随机最短路径

    本文提出了对抗性 SSP 模型，包含时间上对成本的不良变化和未知转移，其开发了第一个对抗性 SSP 算法，并证明了高概率的回报上限。

    Jun, 2020

  • 随机最短路径问题的变体

    本文介绍了关于随机最短路径问题的算法和策略，提供多种保证路径长度分布，而不仅是期望值最小的解决方案，并对最近在马尔科夫决策过程的研究成果进行了应用。

    Nov, 2014

  • 权重受限最短路径问题增强方法：约束路径搜索与双目标搜索相遇

    本文研究基于 A * 算法和双目标搜索的两种解决方案，解决只有一个约束条件的成本最小路径规划问题，并研究在约束搜索中优先队列的重要性。实验证明，不带打结断的桶队列可以有效提高双目标搜索的算法性能。

    Jul, 2022

  • 最短路径与最小斯坦纳树间的查询决策回归

    对于一个具有未知权重的图，如果我们知道一些节点子集关联的最小 Steiner 树，那么我们能否找到一对节点的最短路径？本文研究了这样一个原型问题，称为具有任务转换的查询 - 决策回归，重点关注最短路径问题和最小 Steiner 树问题。我们提供了关于构建评分模型的可实现假设空间设计的理论洞察，并提出了两个有原则的学习框架。我们的实验研究显示，这样的问题可以在统计显著性的程度上得到较好的解决。

    Feb, 2024

  • 随机最短路径的近最优遗憾边界

    本文介绍了一种解决随机最短路径问题的算法，其中代理必须通过在有限次数的游戏中获得最佳策略，从而在最短期望代价下达到目标状态。通过探究悔恨最小化和最小瞬时代价的根号反比关系，本文提出了一种不依赖于最小代价的算法，并展示了任何学习算法在最坏情况下都要有至少 Omega（Bstar 根号乘以 S、A、K 的数量）的悔恨。

    Feb, 2020

  • 在对手成本和未知转移情况下以低遗憾寻找随机最短路径

    本文主要研究随机最短路径问题中的对手成本和未知转移，并提出了一种新的算法，可以在有限的次数内找到最优解，此外，我们还提出了一种新的算法，可以在特定情景下近似达到最优解。

    Feb, 2021

  • 随机最短路径问题的高效约束生成

    利用规划和运筹学的新框架，解决了随机最短路径问题中冗余计算的问题，提出了一种有效的约束生成技术，应用到了新算法 CG-iLAO*，实验证明 CG-iLAO * 相较于 LRTDP 和 iLAO * 在解决问题时速度提高了 8 倍和 3 倍，并忽略了 iLAO * 的多达 57% 的动作。

    Jan, 2024

  • 利用低树宽计算所有对最短路径

    本论文提出了两种新的算法，用于计算带有实数边权（可能为负数）的有向图的全源最短路径。这两种算法运行时间复杂度为 O (n^2w_d)，可用于空间和时间推理，比 Floyd-Warshall 算法和 Johnson 算法更快，并且具有规划和调度社区的相关性。

    Jan, 2014