在递归骑士之旅中正确声明变量(Java作业)

Question

我在学年的最后一个项目(我作为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{声明的这一部分:

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(板的状态的2D数组(访问过,没有看到)),currRow和currCol来反映这一举动.然后它以递归方式调用自身,将调用结果分配给本地声明的布尔变量,您可以将其命名为"success".如果成功指定为true,则findTour返回true.如果成功为假,则findTour撤消刚才所做的移动,或"回溯",并尝试候选下一步移动.您将维护一个静态int变量backtrackCount,该变量初始化为0,并为每次移动撤消递增.

一个注意事项 - 我调用了我的布尔值'tourFound'而不是'success'.

Answer 1

通常情况下无限递归,首先要检查的是你计划如何摆脱它的条件.在这种情况下,你只能逃避

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

检查您的算法和初始化,以防止currentMoveNumber达到numberOfMovesOnBoard.

提示:在输入递归方法之前,您的起始条件是什么？