开放式代数路径问题
通过将基于图的多智能体路径规划与网络流问题相连接,本文研究表明前者可以归纳为后者,进而实现了组合网络流算法及一般线性规划技术应用于基于图的多智能体路径规划问题。此外,在研究中我们还证明了当目标具有排列不变性的情况下,问题仅有一个可行解路径集,该集合具有不超过 $n+V-1$ 的最大完成时间,并提供了一个完整的算法以在 $O (nVE)$ 时间内找到这样的解决方案。最后,我们研究了可行解的时间和距离优化,表明它们具有成对帕累托优化结构,并提供了优化这两个实际目标的有效算法。
Apr, 2012
本文定义了一种基于 $n$ 元关系代数,连接单个关系路径代数和基于张量的多关系代数的图遍历代数,提供了一个单子集、自动机和形式语言理论的基础,用于构建多关系图遍历引擎。
Nov, 2010
研究了在线最短路径问题及其各种监控模型,在加权有向无环图中寻找一条路径以使其对应的边权和尽可能小。提出了一种算法,将累积损失最小化,并介绍了其应用于包交换网络中路由的模拟结果。
Apr, 2007
本文介绍了一种基于路径收集的网络数据分析框架,使用基尔霍夫矩阵求解策略计算路径之间关系概率分布,并提高了一种框架的应用,可以计算并测量不同的节点关系度量标准,并通过实验证明了该方法在半监督分类问题上的竞争优势。
Feb, 2013
本文提出了一种解决 Hamilton-Jacobi 方程的算法,用于优化车辆在指定区域内行驶的最佳轨迹问题,旨在利用数值方法来找到最小化行驶成本和终端成本的轨迹,并将此算法应用于图像处理领域。
Mar, 2013
本文研究多智能体路径规划在有向图中的计算复杂性,证明了该问题在一般情况下是 NP - 难的,但在强连通有向图中的短路径解决方案假设成立时则在 NP 之内。同时,该论文证明了该假设在允许同步旋转的情况下仍然成立。
Oct, 2022
本文介绍了关于 Grassmann 和 Stiefel 曼陀罗上的一些新的数值线性代数算法,具有优秀的性能表现,并可用于对称特征值问题、非线性特征值问题、电子结构计算和信号处理等领域中出现的约束条件进行建模。
Jun, 1998
本文介绍一种使用强化学习训练图神经网络求解单人游戏定义的图组合优化问题的新框架,可以处理最小生成树、最短路径、旅行商问题和车辆路径问题等一系列问题,该方法可在线性运行时间内输出近似解,并且能够推广到多种情况,包括 NP 困难的问题和真实世界的图。
Jun, 2020
在加权有向图中解决最短路径问题时,考虑边权重计算时间以及与权重不确定性的关系可以提高性能。通过建立在加权有向图的通用框架上,引入了找到最紧适应最短路径(TASP)的问题,该路径在最优成本的上界上最紧缩,实现了对有界不确定性的最短路径问题的泛化,其中可以用计算成本代替边权重的不确定性。我们提出了一个完整的算法来解决 TASP,并对解决方案的质量进行了保证。实证评估支持这种方法的有效性。
Aug, 2023