jps期刊发表论文水平如何

本文的思路受到博客： 和论文： 的启发和借鉴。 JPS(jump point search)算法实际上是对A 寻路算法的一个改进，即在扩展搜索节点时，提出了更优化的策略，A 在扩展节点时会把节点所有邻居都考虑进去，这样openlist中点的数量会很多，搜索效率较慢。JPS算法通过寻找跳点的方式，排除了大量不感兴趣的点，减少了openlist中搜索的点的数量，速度大大提高。 水平(垂直)搜索：如图右边部分描述，点1和4如果经过x到达，还不如从点p(x)到达，所以不用考虑点1,4，同理继续向右搜索时，点2,5和点3,6，都是类似的情况，直到遇到黑色的障碍，没有发现感兴趣的点，x处水平方向搜索完成，垂直方向搜索类似。如图左边部分描述，在点x处向右搜索至点y时，点y有一个强迫邻居(点7)，因此y是从点x处沿水平方向搜索的一个跳点，需要将y加入到openlist中。水平搜索结束。 对角搜索：斜向搜索时，需要先在当前点的水平和垂直方向搜索一下，看能否找到感兴趣的点，如果找到，则将当前点加到openlist，结束斜向搜索，如果找不到，则继续斜向多走一步，继续，直到找到感兴趣的点或者斜向方向遇到障碍。 一条完整路线的搜索过程： 搜索算法： 下面两张对比图，摘自上面的论文，可以看出，JPS算法实在优秀。 github链接 上图中红色块为节点x，基于前节点为P(x)的情况下的自然邻居节点。而被迫邻居则是图中绿色的方块（其对称情况未画出）。x被迫邻居包含三层隐藏含义：首先被迫邻居的位置是基于P(x)、x、阻挡块的相对关系定的，如第三个图所示，如果第三个图中，P(x)的位置在节点6的位置，那么绿色方块就不是x的被迫邻居了。其次，被迫邻居一点是考察非自然邻居的节点。最后被迫邻居一定是P(x)经过x到达才能取得最短路径的点。 起点S，终点T，黑色块为阻挡黄色块为跳点，红色箭头是搜索方向，但是没有找到跳点，绿色箭头表示找到跳点。横坐标A-N，纵坐标1-10。 起始位置S，将A10加入openlist里，开始算法流程。 从openlist里取出代价最小的节点(现在为S)，当前节点没有方向，所以需要搜索8个方向，只有右上方B9点是跳点。因为根据跳点定义iii，斜向搜索时，需要在两个分量方向查找跳点，右方是墙壁，略过，上方B8点有强迫邻居点C7，所以B8是跳点（根据跳点定义ii），所以B9是跳点。将B9加入openlist里。A10处理完后，将其从openlist中移除，加入closelist里。 从openlist中取出B9点，该点的父亲是S，所以搜索方向为右斜上，需要在右斜上，右方，上方搜索跳点，只有B8满足要求，将B8加入openlist。处理完B9点将其移到closelist。 从openlist取出B8点，该点搜索方向为上，B8有被邻居C7点，在斜上方搜索跳点，可以看出D8是C7的被迫邻居，所以C7是跳点，B8处继续向上搜索结束。 从openlist中取出C7点。需要搜索右上，右，上三个方向。水平搜索时发现被迫邻居D8，加入openlist。右上搜索时发现跳点G3（因其在上方搜索时发现具有被迫邻居节点的G2），将G3加入openlist。C7点处理结束。 取出G3点（为啥是G3，而不是D8点呢，因为从总代价来说G3比D8更小，总代价=已经走过的距离 + 估值，估值可采用曼哈顿距离或者高斯距离），需要搜索右上，右，上三个方向。向上搜索到跳点G2。 其余点路径在图上标注，就不再重复了。 (1) 若current方向是直线 i. 如果current左后方不可走且左方可走，则沿current左前方和左方寻找跳点。 ii. 如果current当前方向可走，则沿current方向寻找跳点。 iii. 如果current右后方不可走且右方可走，则沿current右前方和右方寻找跳点。 (2) 若current方向是斜线 i. 如果当前方向的水平分量可走，则沿current方向的水平分量方向寻找跳点。 ii. 如果当前方向可走，沿current方向寻找跳点。 iii. 如果当前方向的垂直分量可走，则沿current方向的垂直分量方向寻找跳点。 上述算法流程是建立在斜向不可穿过阻挡基础上。