跳点搜索

在计算机科学中，跳点搜索（JPS）是对均匀成本网格的A*搜索算法的一种优化。它通过图的修剪来减少搜索程序中的对称性，根据对当前节点的邻居可以做出的假设来消除网格中的某些节点，只要与网格有关的某些条件得到满足。因此，该算法可以考虑沿着网格中的直线（水平、垂直和对角线）进行长距离跳跃，而不是普通A*所考虑的从一个网格位置到下一个网格位置的小步骤。跳跃点搜索保留了A*的最优性，同时有可能将其运行时间减少一个数量级。

Harabor和Grastien的原始出版物提供了邻居修剪和识别继承者的算法。邻居修剪的原始算法允许发生切角，这意味着该算法只能用于宽度为零的移动代理，限制了其在现实生活中的代理（如机器人）或模拟（如许多游戏）的应用。

作者在第二年提出了修改后的修剪规则，用于不允许剪角的应用。这篇论文还提出了一种预处理网格的算法，以xxx限度地减少在线搜索时间。作者在2014年发表了一些进一步的优化措施。这些优化包括探索列或行的节点，而不是单个节点，预先计算网格上的跳点，以及更强的修剪规则。

虽然跳点搜索仅限于统一成本的网格和同质大小的代理，但作者将未来的研究放在将JPS与现有的基于网格的加速技术（如分层网格）的应用上。