logo标签列表

寻找网格路径的最省内存算法

calgorithmperformancememory
6
什么是最节省内存的算法，可以用来找到一个网格方块到另一个网格方块的路径？该网格可能有无法穿过的障碍。虽然最短路径不是必需的，但肯定是一个奖励。该算法将在C中编码（可用C ++，但我正在避免它以减少内存使用），并在具有2048字节SRAM的ATmega328芯片上运行。 CPU效率并不是最重要的。
编辑：网格为16x32个方块，每个方块由一个位表示。因此总内存使用量为64字节。网格被存储为无符号字符的2D数组，并且所有2048字节都可用。输出将是引用应采取的方块的整数数组。
如果一个方块中有障碍物，则方块数组将有1而不是零。这些方块应被视为墙壁。
网格数据是静态的吗？如果是，您可以预先计算查找表，这样就不必在设备上执行路径查找算法。如果可用的话，您可能可以将查找表存储在闪存或ROM中，以便它不使用RAM。 - nbering
@nbering 数据不是静态的，因为它是在运行时计算的，但是一旦数据被收集，更改的可能性非常小。 - DividedByZero
2
我推荐使用Dijkstra算法。 - Weather Vane
在迷宫示例中，我使用了一个包含坐标、状态（障碍）、距离和算法状态的结构体数组。虽然更节省内存的算法可能会花费更多时间，但这是一种非常高效的算法。 - Weather Vane
1
@RandomUser，SO通常不喜欢缺乏任何证据表明您已经尝试过某些东西而不是只是寻求现成的解决方案的问题，再加上您没有解释任何限制（并且仍然缺少例如障碍物的形式）。因此，这可能被认为是“不清楚你在问什么”和/或“范围太广”。哦，还有-如果您明确不想使用C ++-请勿标记它？！？ - underscore_d
显示剩余9条评论
3个回答
5
这是一个未完成的算法想法，可能适用于2048字节，我在尝试寻找非递归泛洪填充变体时想到了它。
第一步是创建一个额外的32×16的8位值数组；这将使用512字节。然后你水平迭代网格，并像下面的图像一样对相邻可达方块进行编号：

grid path numbered

对于一个32×16的网格，最大运行次数为256（例如使用棋盘图案或垂直条纹），因此这个编号适合8位值。
第二步是垂直迭代网格，并将相邻的运行分组：
在检查垂直线1之后： {0A，11，1A} {2E} {44，50，5C} {72} {87，8F，98}
在检查垂直线2之后： {0A，11，1A，00，24} {2E} {44，50，5C，37，69} {72} {87，8F，98，7C}
在检查了垂直线2之后：
{0A，11，1A，00，24，12，2F}
{2E}
{44，50，5C，37，69，51，73}
{72}
{87，8F，98，7C，90}
......等等，如果它们被相邻的运行链接，则合并组。最后，如果起始和目标方块的编号在同一组中，则表示存在路径。
现在，如果将组存储为简单列表（如上面的示例），这并不能真正给你一条路径; 它只告诉您可以从起始点和目标点到达哪些方块，但路径可能不需要穿过所有这些方块。
如果将组存储在数据结构中，并且知道哪些运行彼此连接，则它将变成“更小空间中的最短路径通过图”问题。我不确定哪种数据结构最适合剩余的1536个字节。
（欢迎任何人尝试进一步发展这个想法。）

这种方法可以在运行另一个算法之前简化网格。首先，对于网格的分组确定了无法到达的区域; 这些区域可以被标记为原始网格或其副本中的墙壁。其次，它识别了死胡同; 仅与另一个路径相连的路径（且不包含起点或目标方块）是不必要的绕路，也可以标记为这样。 （应重复此操作：删除单连接的路径可能会揭示另一个单连接的路径。）

grid path simplified

通过删除无法到达和单向链接的行简化网格

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

下面的JavaScript代码片段是算法的第一部分的简单示例：使用图像中的示例网格对其进行编号，将其分配到组中，在必要时合并组，然后检查起始和目标方块是否在同一组中，即是否存在路径。
分组方法可能不是最有效的，特别是在合并组时，但它使用了一个固定大小的数组，最大为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));

这是一个非常有趣的想法，然而，它似乎更适合作为预处理算法而不是实时运行的算法，特别是考虑到ATmega328的处理能力。 - DividedByZero
@RandomUser 我必须承认我甚至不知道ATmega328是什么 :-) （谷歌告诉我它在一些Arduino模型中） - m69 ''snarky and unwelcoming''
4
如果你只想找到目标，但不关心记住所走的路径，那么随机搜索在记忆方面几乎是最优的。它不需要记住任何关于先前状态的信息，因此内存使用是恒定的。（另一方面，时间复杂度是无界的，这并不好，但也不违反您的要求）
如果您确实需要记住已经走过的路径，则不能使用空间复杂度低于线性的完整算法 - 即始终可以找到路径（如果存在）。广度优先搜索和深度优先搜索都具有线性空间复杂度，因此它们与最优完整算法在渐近意义下处于相同的类别。
由于内存非常有限，您可能更喜欢使用内存受限算法，它为您提供内存使用的恒定上限，但不能保证找到可能存在的路径。我建议使用简化的内存受限A*算法。
随机搜索相对于不使用地图的算法（如Trémaux算法）在内存使用和时间复杂度方面有何区别？ - DividedByZero
@RandomUser 我不知道，我还没有分析它的复杂度。时间复杂度肯定不是无限的。 - eerorika
鉴于问题的规模，随机搜索需要很长很长的时间，特别是如果没有可走路径的话。 - chqrlie
1
我研究了使用Dijkstra算法（由Weather Vane建议），这将要求为每个网格单元存储到起点的距离和从前一个单元格的方向。不幸的是，在32x16的网格上，路径的距离可能大于255；我发现的最长路径距离为319（见下面的左图）。这意味着距离无法适应8位，距离矩阵的大小为1024字节。

longest path and largest queue

左：最长路径（距离=319）。右：等距单元格的最大数量（16个单位距离处的72个单元格）

然而，在所有距离相等的正方形网格中，可以将Dijkstra简化为不使用距离矩阵的广度优先搜索；如果使用FIFO队列，则按照到起始单元格的距离顺序访问单元格，因此无法找到已访问单元格的更短路径。

FIFO队列将包含特定距离的每个单元格，然后逐渐过渡到距离+1等。队列的最大大小取决于可能存在的等距单元格数量；我发现最大值为72（请参见上图右侧），在从以前的距离过渡时，这需要一个可以容纳76个单元格坐标或152字节的队列。

算法返回的路径是一个数组，包含最多320个单元格的坐标，因此其最大尺寸为640字节。在构建此数组之前，可以丢弃队列，因此仅在内存中同时保存方向网格和路径。

以下是简化算法的代码示例，仅包含方向矩阵和FIFO队列；它可能在许多方面得到改进，但它展示了这个想法。findPath()函数使用最少664字节至最多1152字节的分配内存（取决于路径长度），再加上约20字节的附加变量。 可以进一步减少，例如将方向矩阵存储为4位半字节，将其大小从512字节减小到256字节（但需要更多计算），或者将路径作为上/右/下/左方向的序列返回而不是单元格坐标，每步只需要2位，将其最大大小从640字节减小到80字节。 
#include <stdlib.h>                                         //  gcc -std=c99

short int findPath(char grid[][32], char x1, char y1, char x2, char y2, char **path) {
    char (*dir)[16][32] = calloc(512, 1);                   // allocate direction matrix: 512 bytes (zeros)
    (*dir)[y2][x2] = 5;                                     // mark starting cell as visited (search backwards)
    char *queue = malloc(152);                              // allocate fifo queue: 152 bytes
    queue[0] = x2; queue[1] = y2;                           // put starting cell in queue (search backwards)
    unsigned char qRead = 0, qWrite = 2;                    // queue pointers
    char qCurSize = 1, qNextSize = 0;                       // queue size per distance
    short int distance = 0;                                 // distance to current cell
    char dx[4] = {0, 1, 0, -1};                             // up, right, down, left
    while (qRead != qWrite && !(*dir)[y1][x1]) {            // until queue empty (fail) or target reached
        char x = queue[qRead++], y = queue[qRead++];        // take oldest cell from queue
        qRead %= 152;                                       // wrap-around queue pointer
        for (char i = 0; i < 4; i++) {                      // check 4 neighbouring cells
            char nx = x + dx[i], ny = y + dx[3 - i];        // coordinates of neighbouring cell
            if (nx >= 0 && nx < 32 && ny >= 0 && ny < 16    // coordinates not off-grid
            && !grid[ny][nx] && !(*dir)[ny][nx]) {          // traversable unvisited cell
                (*dir)[ny][nx] = i + 1;                     // store direction 1-4
                queue[qWrite++] = nx; queue[qWrite++] = ny; // put cell in queue
                qWrite %= 152;                              // wrap-around queue pointer
                ++qNextSize;                                // increment queue size for next distance
            }
        }
        if (!--qCurSize || (*dir)[y1][x1]) {                // current distance done or target reached
            qCurSize = qNextSize;                           // switch to distance + 1
            qNextSize = 0;
            ++distance;
        }
    }
    free(queue);                                            // free up queue memory for path
    if (!(*dir)[y1][x1]) distance = -1;                     // no path found
    else {                                                  // path found
        *path = malloc(distance * 2 + 2);                   // allocate path array: 2 bytes per step
        (*path)[0] = x1; (*path)[1] = y1;                   // starting position (forward)
        for (short int i = 1; i <= distance; i++) {         // retrace steps
            char d = (*dir)[y1][x1] - 1;                    // direction of previous step 0-3
            x1 -= dx[d]; y1 -= dx[3 - d];                   // go back to previous position
            (*path)[i * 2] = x1; (*path)[i * 2 + 1] = y1;   // add cell to path
        }
    }
    free(*dir);                                             // discard direction matrix
    return distance + 1;                                    // return number of cells in path
}

int main() {
    char grid[][32] = // max queue size: 76
        {{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};
    char x1 = 31, y1 = 0, x2 = 16, y2 = 7, *path = NULL;
    short int steps = findPath(grid, x1, y1, x2, y2, &path);
    // do stuff
    free(path);                                             // discard path array

    return 0;
}
@AleksandurMurfitt，我看到你取消了对这个答案的接受，并接受了我的另一个答案。你发现这种方法有问题了吗？ - m69 ''snarky and unwelcoming''
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接