跳跃点搜索是否严格优于 A*？

Question

根据很多相关资料，似乎Jump Point Search在满足要求条件（uniform-cost grid等）时严格优于A*

但是经过一些实际测试，我发现跳跃点搜索的搜索时间几乎与A*相同（甚至更糟......），我对此不太确定......（实现问题? 随机网格 ?)

搜索实现来自here，测试代码如下：

int profileCount = 256;
long elapsedJumpPoint = 0;
long elapsedAStar = 0;

for (int i = 0; i < profileCount; ++i)
{
    // random set obstacles here
    RandomizeGrid(searchGrid);

    {
        searchGrid.Reset();

        var stopWatch = Stopwatch.StartNew();
        jumpParam.DiagonalMovement = (DiagonalMovement)cbbJumpType.SelectedIndex;
        jumpParam.CurIterationType = cbUseRecursive.Checked ? IterationType.RECURSIVE : IterationType.LOOP;
        jumpParam.Reset(startPos, endPos);
        var path = JumpPointFinder.FindPath(jumpParam);
        elapsedJumpPoint += stopWatch.ElapsedMilliseconds;
    }

    {
        searchGrid.Reset();

        var stopWatch = Stopwatch.StartNew();
        starParam.DiagonalMovement = (DiagonalMovement)cbbJumpType.SelectedIndex;
        starParam.SetHeuristic(HeuristicMode.EUCLIDEAN);
        starParam.Reset(startPos, endPos);
        var path = AStarFinder.FindPath(starParam);
        elapsedAStar += stopWatch.ElapsedMilliseconds;
    }
}

MessageBox.Show(string.Format("JP time : {0}ms\nA* time : {1}ms", elapsedJumpPoint / (float)profileCount, elapsedAStar / (float)profileCount));

RandomizeGrid 代码在这里：

void RandomizeGrid(BaseGrid searchGrid, float randomPercent = 0.2f)
{
    if (searchGrid != null)
    {
        var width = searchGrid.width;
        var height = searchGrid.height;

        for (int i = 0; i < width; ++i)
        {
            for (int j = 0; j < height; ++j)
            {
                searchGrid.SetWalkableAt(new GridPos(i, j), true);
            }
        }

        var random = new Random();
        for (int i = 0; i < width * height * randomPercent; ++i)
        {
            var randWidth = random.Next(0, width);
            var randHeight = random.Next(0, height);
            searchGrid.SetWalkableAt(new GridPos(randWidth, randHeight), false);
        }
    }
}

一些测试结果也列在下面：

|随机百分比 |太平绅士 | A* |

| 0.05 | ~8.7 毫秒 | ~8.2 毫秒 |

| 0.1 | ~11 毫秒 | ~14.3 毫秒 |

| 0.2 | ~15 毫秒 | ~13.7 毫秒 |

| 0.5 | ~20.5 毫秒 | ~22 毫秒 |

Answer 1

跳转点搜索显着减少了 A* 优先级队列的大小，但查找每个跳转点本身所花费的时间要长得多。但是，它节省了大量时间，因为它不需要存储和维护可以从 A* 生成的大型优先级队列，而在 A* 中保持排序的推送操作可能很昂贵。较小的队列也有助于缓存行。但是跳跃点搜索最终可以扩展比 A* 更多的节点，即使它们没有被添加到开放列表/优先级队列中。

要回答关于运行时间是否严格更好的问题，这实际上取决于算法的实现以及给定的地图。由于打开列表的大小要小得多，因此内存使用通常会更好。如果网格像迷宫或有很多障碍物，速度通常会降低，因为它最终会增加很多跳跃点，这可能很昂贵。

我针对 A* (https://github.com/YashTrikannad/mpl/blob/master/include/mpl/jps.h) 对跳跃点搜索的实现进行了基准测试，跳跃点搜索在 1000x1000 二维网格上平均快了 10 倍运行1000 运行s 有 4-5 个大型障碍物（不是迷宫）。

跳跃点搜索是否严格优于 A*？

Is Jump Point Search strictly better than A*?

search

a-star