c - 探索有障碍的网格

Question

我需要一个机器人算法来探索一个有障碍物的 n*n 网格（如果你愿意的话，一个迷宫）。目标是探索所有没有障碍的广场，并避开有障碍的广场。诀窍是障碍物迫使机器人改变其路径，导致它错过障碍物后面可能的自由方块。我可以懒惰地增加/减少机器人的 x/y 坐标，让机器人在四个方向中的任何一个方向移动，以防没有障碍物并且机器人可以穿过预先看到的路径（如果需要）以到达其他自由方格. 当所有空闲方块至少遇到一次时，算法应该终止。

任何简单的懒惰/有效的方法来做到这一点？一个伪代码将不胜感激

Answer 1

只需保留未探索邻居的列表即可。如有必要，可以使用一个聪明的启发式方法来确定接下来要访问列表中的哪个字段，以提高效率。

伪代码（使用堆栈来跟踪导致 DFS 的未探索邻居）：

// init
Cell first_cell;
CellStack stack;
stack.push(first_cell);

while(!stack.isEmpty()) {
    Cell currentCell = stack.pop();
    currentCell.markVisisted();
    for(neighbor in currentCell.getNeighbors()) {
        stack.push(neighbor);
    }
}

Answer 2

我相信这个问题可以从Traveling Salesman Problem减少，因此是NP-Hard，所以你不太可能找到一个多项式解决方案来优化和有效地解决问题。

但是，您可能希望对 TSP 采用一些启发式方法和近似值 ，我相信它们也可以针对此问题进行调整，因为该问题首先似乎与 TSP 非常接近

编辑：

如果不需要找到最短路径，并且您想要任何路径，则可以使用维护访问集的简单DFS来完成。在 DFS 的步骤中，您从递归中返回 - 您移动到先前的方格，这样可以确保机器人探索所有方格，如果有通向所有方格的路径。

DFS 的伪代码：

search(path,visited,current):
   visited.add(current) 
   for each square s adjacent to current:
      if (s is an obstacle): //cannot go to a square which is an obstacle
         continue
      if (s is not in visited): //no point to go to a node that was already visited
         path.add(s) //go to s
         search(path,visited,current) //recursively visit all squares accesable form s
         //step back from s to current, so you can visit the next neighbor of current.
         path.add(current)

调用search([source],{},source)

请注意，可以在该for each步骤之前使用优化启发式 - 启发式只是重新排序节点的迭代顺序。

Answer 3

我认为解决问题的最佳方法是递归（转到最近的空闲单元）。使用以下附加启发式方法：转到最近的空闲单元格最少的空闲邻居（首选存根）。

伪代码：

// init:
for (cell in all_cells) {
    cell.weight = calc_neighbors_number(cell);
}

path = [];

void calc_path(cell)
{
    cell.visited = true;
    path.push_back(cell);
    preferred_cell = null;
    for (cell in cell.neighbors)
        if (cell.visited) {
            continue;
        }
        if (preferred_cell == null || preferred_cell.weight > cell.weight)
           preferred_cell = cell;
    }
    if (preferred_cell != null) {
        calc_path(preferred_cell);
    }
}

// Start algotithm:
calc_path(start);