在遞歸騎士之旅中正確聲明變量（Java作業）

我無法在我的代碼中找到我上一個學年項目（我作爲CS學生的第一年）的錯誤。我被卡在執行騎士巡迴賽問題的遞歸中。這是有問題的文件：https://github.com/sheagunther/tsp161knightstour/blob/master/KnightsTourRecursiveSearch.java 在遞歸騎士之旅中正確聲明變量（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;

的這部分代碼改變棋盤爲-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至反映了此舉。然後遞歸調用它自己，將調用的結果分配給本地聲明的布爾變量，您可以將其命名爲「成功」。如果成功分配爲true，findTour將返回 true。如果成功是錯誤的，findTour將撤消它剛剛做出的動作，或者「回溯」，並嘗試candidateNextMoves的下一步移動。您將維護一個靜態int變量backtrackCount，該變量初始化爲爲0，並且對於移動的每次撤消都會遞增。

一個音符 - 我叫我的布爾'tourFound'而不是'成功'。

來源

2012-05-11 Shea Gunther

請寫出要點，精確和簡短。 –

@BhavikAmbani這個問題似乎寫得很好 - 雖然它可以使用一些格式來提高可讀性。 –

@PaulBellora因爲沒有人會閱讀整篇論文來解決你的問題。 –

無限遞歸常常是這種情況，首先要檢查的是您計劃如何擺脫它的條件。在這種情況下，你只能逃避，如果

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

檢查你的算法和初始化的東西會阻止currentMoveNumber到達numberOfMovesOnBoard。

提示：在您進入遞歸方法之前，您的起始條件是什麼？

來源

2012-05-11 20:06:08 Thomas

太棒了！感謝您的建議，我會看看這個。 –

我發現我的NumberOfMovesOnBoard被關閉了1.我把它設置爲平方的平方數。如果巡迴賽將被關閉 - 如果騎士退回到他跳到的第一個方格上，這是正確的數額，但是因爲我現在的代碼正在尋找一個開放的解決方案，棋盤上的棋子數量是數量減去1.這還沒有解決問題，但很好解決。步步高昇。 –

我不認爲我已經解決了我的問題，但它只是成功地找到了一個5x5板卡。 –

在遞歸騎士之旅中正確聲明變量（Java作業）

回答

相關問題