关于计算滑块解题中的最佳完成时间的研究
本文介绍了一种基于加权有向图和最小流限制的非确定性计算模型,并且通过一系列特例的证明和简单归约,证明了该模型可以被用于解决复杂的运动规划问题,包括障碍物移动、滑动积木等。
May, 2002
我们研究了求解迷宫类问题的 CP 和 SAT 方法,提出了一种新的可达性编码,并通过实验证明这种新编码在以 SAT 为范式的规划问题中,尤其是考虑到同时执行多个动作时是非常适用的。
Oct, 2023
使用前瞻信息作为特征,提出一种利用学习方法改善具有时间窗口的 TSP 解决方案合法性的新方法,并构建了具有硬约束条件的 TSPTW 数据集进行准确评估和基准测试。通过对多种数据集进行综合实验,MUSLA 优于现有基线算法且具有一定的泛化能力。
Mar, 2024
本文利用 Bidirectional A * 算法及三种启发式算法(曼哈顿距离、线性位差和行走距离)解决了 Fifteen Puzzle 问题,并将这三种启发式算法混合运用,有效减少了算法生成状态数和扩展节点数,大大降低了空间复杂度,保证了最优解或接近最优解。
Jan, 2023
提出了一种基于图神经网络和引导局部搜索的 TSP(旅行商问题)混合数据驱动方法,该方法能够在不损失解决方案质量的同时,快速求解大规模 TSP 实例,经实验证明,我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%,将 20 个节点实例推广到 100 个节点问题集时,我们将最优性差从 18.845% 减少到 2.622%,提高了 2 倍和 7 倍。
Oct, 2021
本文介绍了新型的方形拼图,引入了遗传算法解决未知位置和方向的拼图问题,同时还可以处理双面的、未知面和方向的拼图。结果表明我们的求解器提供了一种新的最先进技术,可以更快,更精确地解决尝试过的拼图,并自动有效地处理新引入的双面拼图。同时,本文还提供了到目前为止最为广泛的关于 Type 2 拼图的实验结果。
Nov, 2017
在这篇论文中,我们解决了关于协调运动规划(CMP)的参数化复杂性问题,即最小化机器人数量和目标的问题。我们通过对问题的最优解的结构性洞察,建立了这两个问题在前者参数化条件下的固定参数可解性。此外,我们还证明了 CMP-L 在目标参数化条件下保持固定参数可解,而 CMP-M 则成为了 para-NP-hard 问题。后者的结果不仅改进了该问题不可解性的已知边界,还使我们能够通过底层约简来简化情况,从而证明了网格上具有常数路径长度的经典顶点不相交和边不相交路径问题的 NP-hard 性。
Dec, 2023
本文提出了一种利用关系型特征抽象学习广义策略自动机(Generalized Policy Automata,GPA)来解决随机最短路径(Stochastic Shortest Path Problems,SSPs)问题的方法,该方法通过少量数据训练便能学到适用于各种相关问题的泛化的非确定性部分策略(partial policy),并在针对数量超过训练数据的问题上显著优于现有的 SSP 求解器。
Apr, 2022
本研究提出一种迭代方法来高效地解决一类严格凸代价函数的最优运输问题,该方法包括二次和 p 次幂代价函数。我们针对两个定义在离散网格上的概率分布,使用 O (n) 的存储空间和 O (n log (n)) 的操作量计算最优映射,具有近似指数收敛速度。该方法能够在几分钟内解决空间网格大小达到 4096x4096 和 384x384x384 的最优运输问题。
May, 2019