迷宫求解器记录回溯路径

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;
  }
}

简单的修复还是完全重组？

Answer 1

当求解器直接进入该末端时，它记录了它“从（r，c）访问”，因为您访问的数组是三个维度。但是它从未记录过它已经访问过的 剩下 从（r，c + 1）”。因此，它认为可以移动到同一 位置 两次，只要它没有使完全相同的移动两次（它没有，因为它在回溯时向左移动，不正确）。

看起来它会像您更改为二维阵列一样工作正常，只有记录 位置, ，不动。然后，您在封锁进一步移动之前访问过的每个正方形，但这没关系，因为如果正确的解决方案需要回到该方形参观广场探索。

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. 某些持有您当前迷宫状态的阶级状态
2. end_state函数知道状态何时处于解决方案
3. generate_moves函数，可以找到当前状态的所有选项
4. 可以对您的状态采取行动的make_move
5. undo_move可以撤消反对状态的行动
6. 您定义了option_t，以代表一个移动选项
7. 定义运算符<<状态

我可以告诉您，当然，我给您的解决方案在打印回溯空间时没有问题（也应该从代码中清楚）。