algorithm - 多少步才能到达目的地？高效灌水

Question

我想计算单元格与目标单元格的距离，使用四向移动的次数来到达某物。因此，与目的地紧邻的四个单元格的距离为 1，每个单元格的四个主要方向上的距离为 2，依此类推。最大距离可能在 16 或 20 左右，并且有些单元格被障碍物占据；距离可以绕过它们，但不能穿过它们。

我想将输出存储到一个二维数组中，并且我希望能够非常快速地为更大的迷宫 map 上的任何目的地计算这个“距离图”。

我通过洪水填充的变体成功地做到了这一点，我将相邻未填充单元格的增量距离放置在优先级队列中(使用 C++ STL)。

我对这些功能很满意，现在想专注于优化代码，因为它对性能非常敏感。

可能有哪些巧妙而快速的方法？

Answer 1

我认为你做的一切都是对的。如果您编码正确，则需要 O(n) 时间和 O(n) 内存来计算洪水填充，其中 n 是单元格的数量，并且可以证明不可能做得更好(在一般情况下)。填充完成后，您只需返回任何目的地的距离，复杂度为 O(1)，很容易看出它还可以做得更好。

所以如果要优化性能，只能着眼于CODE LOCAL OPTIMIZATION。这不会影响渐近，但可以显着改善您的实际执行时间。但是，如果不实际查看源代码，很难给您任何代码优化建议。

因此，如果您真的想查看优化代码，请参阅以下内容(纯 C):

包括

int* BFS()
{
    int N, M; // Assume we have NxM grid.
    int X, Y; // Start position. X, Y are unit based.
    int i, j;
    int movex[4] = {0, 0, 1, -1}; // Move on x dimension.
    int movey[4] = {1, -1, 0, 0}; // Move on y dimension.

    // TO DO: Read N, M, X, Y

    // To reduce redundant functions calls and memory reallocation 
    // allocate all needed memory once and use a simple arrays.
    int* map = (int*)malloc((N + 2) * (M + 2)); 
    int leadDim = M + 2;
    // Our map. We use one dimension array. map[x][y] = map[leadDim * x + y];
    // If (x,y) is occupied then map[leadDim*x + y] = -1;
    // If (x,y) is not visited map[leadDim*x + y] = -2;

    int* queue = (int*)malloc(N*M);
    int first = 0, last =1; 

    // Fill the boarders to simplify the code and reduce conditions
    for (i = 0; i < N+2; ++i)
    {
        map[i * leadDim + 0] = -1;
        map[i * leadDim + M + 1] = -1;
    }

    for (j = 0; j < M+2; ++j)
    {
        map[j] = -1;
        map[(N + 1) * leadDim + j] = -1;
    }

    // TO DO: Read the map.

    queue[first] = X * leadDim + Y;
    map[X * leadDim + Y] = 0;

    // Very simple optimized process loop.
    while (first < last) 
    {
        int current = queue[first];
        int step = map[current];

        for (i = 0; i < 4; ++i)
        {
            int temp = current + movex[i] * leadDim + movey[i];
            if (map[temp] == -2) // only one condition in internal loop.
            {
                map[temp] = step + 1;
                queue[last++] = temp;
            }
        }

        ++first;
    }

    free(queue);

    return map;
}

代码可能看起来很棘手。当然，它看起来不像 OOP(我实际上认为 OOP 粉丝会讨厌它)，但如果您想要真正快速的东西，那就是您所需要的。