5

我在学年的最后一个项目（我作为 CS 学生的第一年）的代码中找不到错误。我在执行骑士巡回问题时陷入了递归。这是有问题的文件：https ://github.com/sheagunther/tsp161knightstour/blob/master/KnightsTourRecursiveSearch.java

具体来说，我的问题在于这部分代码（从第 265 行开始）：

   else{
   for(int i = 0; i < numberOfPossibleNextMoves; i++){
      Cell nextCellToMoveTo = candidateNextMoves.get(i);

      int currentRowStorage = currentRow;
      int currentColumnStorage = currentColumn;
      currentRow = nextCellToMoveTo.row;
      currentColumn = nextCellToMoveTo.column;

      listOfMoves.add(nextCellToMoveTo);
      chessBoard[currentRow][currentColumn] = 1;
      currentMoveNumber++;

      boolean tourFound = findTour();

      if(tourFound){
         return true;
            }
            else{ // Undo the last move just made
               backtrackCount++;
               chessBoard[currentRow][currentColumn] = -1;
               currentRow = currentRowStorage;
               currentColumn = currentColumnStorage;                           
               listOfMoves.remove(nextCellToMoveTo);
               currentMoveNumber--;         
            }
         }
         return false;

这是 findTour() 的结束。这是程序的一部分，它测试从当前方格（也称为单元格）的所有可能的移动，如果可以从新移动到的方格完成游览，则返回 true。如果不能从广场完成游览，它会进入 else{ 并撤消移动。这就是我认为的问题所在。

现在，按照上面的代码设置，程序陷入了无限递归循环。

请注意声明的这一部分else{：

chessBoard[currentRow][currentColumn] = -1;
currentRow = currentRowStorage;
currentColumn = currentColumnStorage;

这部分代码将 chessBoard 中的方块更改为 -1，这意味着它未被访问（1 = 已访问）。如上所示，新移动的 currentRow 和 currentColumn 用于将方格设置回未访问状态。然后使用 currentRowStorage 和 currentColumnStorage 将这些值重置为先前的跳转值。

如果我将代码更改为

currentRow = currentRowStorage;
currentColumn = currentColumnStorage;
chessBoard[currentRow][currentColumn] = -1;

它成功地找到了一个错误的路线，其中最后 1/3 左右的移动只是在几个方格之间来回跳跃。这是意料之中的，因为它没有正确处理重置过程。

我怀疑我的问题是由于我声明变量的位置。这是我的第一个复杂的递归问题，我不确定我是否正确处理了 currentRow/Column 和 currentRow/ColumnStorage 之间的切换。我应该在本地或多或少地声明它们吗？

这是描述该项目的页面： http: //cs.usm.maine.edu/~briggs/webPage/c161/projects/KnightsTour.html

以下是要求的相关部分：

如果游览未完成，则 findTour 确定可以从骑士的当前单元格到达的空单元格列表（可能为空），并将此列表存储在本地声明的列表变量中，candidateNextMoves。将此列表变量声明为方法的本地变量是至关重要的。如果此列表为空，则无法扩展当前部分游览，因此 findTour 应返回 false。如果列表不为空，则 findTour 尝试通过列表上的每个移动来扩展游览，如下所示。它遍历列表，并且对于列表中的每个单元格，它会下一次移动到该单元格，更新所有 L（巡回赛中的移动列表），B（棋盘状态的二维数组（已访问，未访问))、currRow 和 currCol 以反映这一举动。然后它递归地调用自己，将调用结果分配给本地声明的布尔变量，您可以将其命名为“成功”。如果 success 为 true，findTour 返回 true。如果成功为假，findTour 撤消它刚刚进行的移动，或“回溯”，并尝试 CandidateNextMoves 的下一步移动。您将维护一个静态 int 变量 backtrackCount，该变量初始化为 0，并随着移动的每次撤消而递增。

一个注释-我将我的布尔值称为“tourFound”而不是“成功”。

4

1 回答 1

5

与无限递归的情况一样，首先要检查的是您计划如何摆脱它的条件。在这种情况下，您只能在以下情况下逃脱

if(currentMoveNumber == numberOfMovesOnBoard){
     return true;
  }

检查您的算法和初始化是否会阻止 currentMoveNumber 达到 numberOfMovesOnBoard。

提示：在你输入递归方法之前，你的起始条件是什么？

于 2012-05-11T20:06:08.070 回答