迷宫求解器记录回溯路径

Question

我已经让我的迷宫解决程序工作了，但它似乎在最终输出的解决方案路径中包括了回溯的空间（它去到而又碰到墙壁不得不掉头的地方）。以下是示例：

我应该如何防止这种情况发生在下面的当前实现中：

int dir = 4;

bool visited[Max_Maze][Max_Maze][dir];


for (row = 0; row < size; ++ row)
{
  for (col = 0; col < size; ++ col)
  {
    for (dir = 0; dir < 4; ++ dir)
    {
      visited[row][col][dir]=false;
    }
  }
}

bool notSolved = true;
int path = 0;
row = 0;
col = 0;

rowStack.push(row);
colStack.push(col);

while (notSolved)
{

  //from perspective of person looking at maze on screen
  if (((row-1)>=0)&&(maze[row - 1][col] == 0)&&(visited[row][col][0]==false))
  {
    // if that space is not out of bounds and if you can go up
    // and you have not gone in that direction yet, go up
    visited[row][col][0] = true; 
    row--;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else if (((col+1)<size)&&(maze[row][col + 1] == 0)&&(visited[row][col][1]==false))
  {
    //else if you can go right etc., go right
    visited[row][col][1] = true;
    col++;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else if (((row+1)<size)&&(maze[row + 1][col] == 0)&&(visited[row][col][2]==false))
  {
    //else if you can go down etc., go down
    visited[row][col][2] = true;
    row++;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else if (((col-1)>=0)&&(maze[row][col - 1] == 0)&&(visited[row][col][3]==false))
  {
    //else if you can go left etc., go left
    visited[row][col][3] = true;
    col--;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else
  {
    //if stuck
    if (path == 0)
    {
      cout << "No Solution Path" << endl;
      notSolved = false;
    }
    else
    {
      rowStack.pop();
      colStack.pop();
      row = rowStack.top();
      col = colStack.top();
      path--;
    }
  }

  if((maze[row][col] == 0) && (row == (size - 1) && col == (size - 1)))
  {
    //if we reached an exit
    cout << "Solution Path:(in reverse)" << endl;
    for (int i = 0; i <= path; i++)
    {
      cout << "row:" << rowStack.top() << " col:" << colStack.top() << endl;
      rowStack.pop();
      colStack.pop();
    }
    notSolved = false;
  }
}

需要简单修复还是彻底重构？

- darko

---

它只是打印第一个找到的解决方案还是所有解决方案？ - Kevin

是的，它不会找到最快的或任何其他东西，只是第一个。 - darko

Answer 1

当求解器进入死胡同时，它记录了它已经"从(R,C)向右访问过"，因为你的visited数组是三维的。但它从未记录过它已经"从(R,C + 1)向左访问过"。所以它认为重复移动到同一个位置是可以的，只要不做完全相同的移动（因为当它回溯时，它向左移动而不是向右）。

如果将visited更改为二维数组并仅记录位置而不是移动，则似乎它将正常工作。然后，你在之前访问过的每个方格都会阻止进一步移动，但这没关系，因为如果正确的解决方案需要回到该方格，你最终会达到else的情况，足以弹回到该方格，然后就有一个未曾访问过的方块可以探索。

- Ben

---

好的，我认为我正确地实现了那个更改：http://pastebin.com/67pdjtxT 但是仍然存在相同的问题：http://imgur.com/3h9GZ 这次只包括一个回溯空格？ - darko

@mwmnj 我没有时间详细阅读你的代码（这是你的作业，不是我的），但我可以想到许多可能出错的地方。确保记录起始方格已被访问。如果你在离开一个方格之前记录了它被访问过，请确保在弹出的情况下也这样做。如果你在进入一个方格之前记录了它被访问过，请确保你正在记录即将到达的方格，而不是当前所在的方格。如果以上都没有问题，那么请逐步执行你的代码，找出应该弹出而回溯的位置，并找出原因。 - Ben

忘记标记第一个访问的正方形了，谢谢帮忙！ - darko

Answer 2

不针对你的具体解决方案发表评论，你可以考虑将其重做为标准深度优先搜索算法，我认为你会同意这样更加清晰：

boolean dfs (State s) {
    if (end_state(s)) {
        return true;
    }

    vector<option_t> options = generate_moves(s);
    for (vector<option_t>::iterator it = options.begin();
         it != options.end(); it++) {
        make_move(s, it);
        boolean found = dfs(s);
        if (found) {
            cout << s << endl;
        }
        undo_move(s, it);
        if (found) return true;
    }
    return false;
}

正如您所看到的，只要您能够创建以下内容，它就可以正常工作：

1. 一个保存当前迷宫状态的类State
2. end_state函数，用于判断State是否为解决方案
3. generate_moves函数，用于查找当前State的所有选项
4. make_move函数，用于对状态应用移动
5. undo_move函数，用于撤销状态下的移动
6. 您定义option_t，以表示移动选项
7. 为State定义operator<<

我可以告诉您，我给出的解决方案肯定不会出现打印回溯空格的问题（从代码中也应该清楚）。

- Kevin