c - 用于在网格上查找路径的最有效内存算法

Question

可用于查找从一个网格方 block 到另一个网格方 block 的路径的内存效率最高的算法是什么？网格可能有无法跨越的障碍。成为最短路径不是必需的，但肯定是一种奖励。该算法将用 C 编码(C++ 可用，但我避免使用它以减少内存使用)并在只有 2048 字节 SRAM 的 ATmega328 芯片上运行。 CPU 效率并不是最重要的。

编辑: 网格是 16 x 32 正方形，每个由一位表示。因此，总内存使用量为 64 字节。网格存储为无符号字符的二维数组，所有 2048 字节都可用。输出将是一个整数数组，引用应采用的正方形。

如果正方形中有障碍物，则正方形数组的值为 1 而不是零。这些方 block 应该像墙一样对待。

Answer 1

这是一个可能适合 2048 字节的算法的未完成想法，是我在尝试寻找非递归泛洪填充变体时想到的。

第一步是创建一个额外的 32×16 8 位值数组；这使用 512 字节。然后水平遍历网格，并对相邻可到达方 block 的运行进行编号，如下图所示:

对于 32×16 网格，最大游程数为 256(例如棋盘图案或垂直条纹)，因此此编号适合 8 位值。

第二步是垂直遍历网格，并将相邻的运行分组:

After checking vertical line 1:
{0A,11,1A}
{2E}
{44,50,5C}
{72}
{87,8F,98}

After checking vertical line 2:
{0A,11,1A,00,24}
{2E}
{44,50,5C,37,69}
{72}
{87,8F,98,7C}

After checking vertical line 2:
{0A,11,1A,00,24,12,2F}
{2E}
{44,50,5C,37,69,51,73}
{72}
{87,8F,98,7C,90}

...等等，如果它们被相邻的运行链接，则合并组。如果最后，起始方 block 和目标方 block 的数量在同一组中，则表示存在路径。

现在，如果您将组存储为简单的列表，如上例所示，这实际上并没有为您提供路径；它只是告诉您哪些方 block 可以从起始方 block 和目标方 block 到达，但一条路径可能不需要穿过所有这些方 block 。

如果您将组存储在一个数据结构中，您知道哪些运行是相互连接的，那么它就变成了更小空间中的“通过图形的最短路径”问题。我不确定哪种数据结构最适合剩余的 1536 字节。

(欢迎任何人尝试进一步发展这个想法。)

---

此方法可用于在运行其他算法之前简化网格。首先，运行的分组识别网格中无法到达的部分；这些可以在原始网格或其副本中标记为墙。其次，它识别死角；仅连接到另一个运行(并且不包含起点或目标方 block )的运行是不必要的弯路，也可以这样标记。 (这应该重复:删除单连接运行可能会显示另一个运行是单连接的。)

^{通过删除无法访问和单链接的运行简化了网格}

再次运行该算法，但使用垂直运行和水平分组，可以消除额外的死角。

---

下面的 JavaScript 片段是算法第一部分的简单代码示例:使用图像中的示例网格，它对运行进行编号，将它们分配给组，必要时合并组，然后检查是否开始和目标方 block 是否在同一组中，即是否有路径。

分组方法可能不是最有效的，尤其是在合并组时，但它使用最大 256 字节(运行数×8 位值)的固定大小数组，这在有限内存中可能是最好的情况。

function gridPath(grid, x1, y1, x2, y2) {
    var runs = [], rcount = 0;
    for (var i = 0; i < 16; i++) {           // number runs
        var start = true; runs[i] = [];
        for (var j = 0; j < 32; ++j) {
            if (grid[i][j] == 0) {           // found empty cell
                if (start) ++rcount;         // start of new run
                runs[i][j] = rcount - 1;
                start = false;
            }
            else start = true;               // found blocked cell
        }
    }
    var groups = [], gcount = 0;
    for (var i = 0; i < rcount; i++) groups[i] = 0xFF;

    for (var j = 0; j < 32; ++j) {           // assign runs to groups
        var g = [];
        for (var i = 0; i < 16; ++i) {
            if (grid[i][j] == 0) g.push(runs[i][j]);
            if ((grid[i][j] == 1 || i == 15) && g.length > 0) {
                insertGroup(g);
                g = [];
            }
        }
    }     
    return groups[runs[y1][x1]] == groups[runs[y2][x2]];

    function insertGroup(g) {
        var matches = [];
        for (var i = 0; i < g.length; i++) { // check if runs are already in group
            if (groups[g[i]] != 0xFF && matches.indexOf(groups[g[i]]) < 0) {
                matches.push(groups[g[i]]);
            }
        }
        if (matches.length == 0) matches.push(gcount++); // start new group
        for (var i = 0; i < g.length; i++) { // add runs to group
            groups[g[i]] = matches[0];
        }
        if (matches.length > 1) {            // merge groups
            for (var i = 0; i < rcount; i++) {
                if (matches.indexOf(groups[i]) > 0) groups[i] = matches[0];
            }
        }
    }
}

var grid = [[1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0],
            [0,0,0,1,0,0,0,1,0,0,0,0,0,1,1,1,1,1,1,1,0,0,1,0,0,0,0,1,0,0,1,0],
            [0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0],
            [0,0,1,0,1,0,1,0,1,0,0,1,0,0,1,1,1,1,1,0,0,1,0,0,0,1,1,0,1,0,0,1],
            [1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0],
            [0,1,0,0,0,1,0,0,0,0,1,0,1,0,0,1,1,1,0,0,1,0,1,1,0,0,0,0,0,1,0,1],
            [1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,1,1,1,1,0,1,0],
            [0,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0],
            [0,1,0,0,0,1,0,0,0,1,1,0,1,0,0,1,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0],
            [0,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0],
            [1,0,0,1,0,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0,1],
            [0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,1,0],
            [1,0,1,0,1,0,1,0,1,0,1,0,0,1,1,1,1,1,0,0,1,0,0,0,1,0,1,0,1,0,0,1],
            [0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0],
            [0,1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0],
            [0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0]];
document.write(gridPath(grid, 0, 15, 15, 7));