我的递归算法中的问题，用于查找所有最短、唯一的路径

Question

我一直在研究一种递归算法，该算法旨在找到从n乘m矩阵中的点a到点B的所有最短、唯一的可能路径。目前，我的算法可以从一个方向找到所有可能的路径。然而，当我回到算法开始的第一个堆栈帧时，无论在第一帧中采取的先前操作中采取了什么方向，我都会被卡住。我已经确定这是因为我的移动函数引用了我正在使用的当前解决方案。我认为需要做的是，我需要进一步本地化我的参数，这样我基本上可以从头开始。不过，我不知道该怎么做，因为每当我试图放弃对我的运动算法的引用时，"解决方案"都会变成一个字母。

关于让第一个堆栈帧更独立于我的移动算法，有什么建议吗？

{void Robot::findTreasureHelper(Board whichBoard, int x, int y, std::string solution)
++callCount;
if (x == TREASURE_X && y == TREASURE_Y)
{
++numSolutions;
return;
}
if (move(whichBoard, 'N', x, y, solution))
findTreasureHelper(whichBoard, x, y, solution);
if (move(whichBoard, 'E', x, y, solution))
findTreasureHelper(whichBoard, x, y, solution);
if (move(whichBoard, 'S', x, y, solution))
findTreasureHelper(whichBoard, x, y, solution);
if (move(whichBoard, 'W', x, y, solution))
findTreasureHelper(whichBoard, x, y, solution);
{bool Robot::move(Board& whichBoard, const char& whichDir, int& x, int& y, std::string& solution)
bool didMove = false;
int direction = 1;
if (whichDir == 'S' || whichDir == 'E')
direction = -1;
int  *coordinate = &x;
if (whichDir == 'N' || whichDir == 'S')
coordinate = &y;
//check bounds, consecutive movements, and whether robot has been here on this solution
if (x == TREASURE_X && y == TREASURE_Y)
*coordinate += direction;
else if (*coordinate - direction >= 0 && *coordinate - direction < whichBoard.board.size() 
&& *coordinate - direction < whichBoard.board[y].size() && moveCount < CONSECUTIVE_MOVES)
{
*coordinate -= direction;
//check blocks and previously been here
if (whichBoard.board[y][x] == -1 || whichBoard.board[y][x] == currentSolutionIndex)
*coordinate += direction;
else if (x == TREASURE_X && y == TREASURE_Y)
{
switch (whichDir)
{
case 'N':
case 'S':
//check consecutive moves
solution.back() == 'N' || solution.back() == 'S' ? ++moveCount : moveCount = 0;
//add correct character to solution
direction == 1 ? solution += 'N' : solution += 'S';
break;
case 'E':
case 'W':
//check consecutive moves
solution.back() == 'E' || solution.back() == 'W' ? ++moveCount : moveCount = 0;
//add correct character to solution
direction == 1 ? solution += 'W' : solution += 'E';
break;
}
//*coordinate += direction;
this->solutions.push_back(solution);
didMove = true;
}
else // complete the move randomly
{
switch (whichDir)
{
case 'N':
case 'S':
//check consecutive moves
solution.back() == 'N' || solution.back() == 'S' ? ++moveCount : moveCount = 0;
//add correct character to solution
direction == 1 ? solution += 'N' : solution += 'S';
break;
case 'E':
case 'W':
//check consecutive moves
solution.back() == 'E' || solution.back() == 'W' ? ++moveCount : moveCount = 0;
//add correct character to solution
direction == 1 ? solution += 'W' : solution += 'E';
break;
}
didMove = true;
whichBoard.board[y][x] = currentSolutionIndex;
}
}
return didMove;
}

Answer 1

要找到最短路径，我建议您选择BFS而不是DFS，以便更快地找到解决方案。这可以在队列的帮助下完成。从您的起始索引开始，将邻居(在您的情况下，是您的四个邻居N、S、E、W)附加到队列中。

有一个数据结构来跟踪所有访问的索引(最好是一组)。因此，一旦你设置了这些，重复执行以下操作-

1. 从队列中弹出元素
2. 检查这是否是你的目的地索引，如果是你找到了最短的路径
3. 如果没有，请将该索引标记为已访问，并将其邻居追加到队列中

迭代解决方案-明显的好处：)