遞歸與迷宮求解

該項目是使用遞歸和樹編寫Java中的迷宮解算器（我用我自己的鏈表，不能完全確定，如果它是一棵樹，但我不介意）。遞歸與迷宮求解

講師沒有解釋任何東西，所以我在網上把我所有的知識。我有我的遞歸方法麻煩，我不知道該怎麼辦，因爲我無法找到能與我的項目

在我的鏈接列表的例子，我有右邊鏈接到節點，左邊，底部和頂部。如果右側有牆，則鏈接將爲空。我也有在鏈表wallRight，wallLeft，wallBottom和wallTop布爾值，看看是否有例如牆壁的權利。因此，如果右側有一堵牆，則「右側」鏈接將爲空，並且wallRight將爲真。

我也使用的標籤，其是圖像，因此，如果我降落在一個點，圖像顯示。我認爲，如果將我在位置1，它使標籤1顯示，所以在遞歸方法我用了int pos知道哪個標籤顯示的方法。

現在到了我的遞歸方法的麻煩。我嘗試了兩種方法，但都沒有成功。這裏是他們兩個：

public boolean move(Maze rigting,int pos) // Righting = direction 
{ 
    if(rigting.goal == true) 
     return true; //BASE CASE - tests if it is on the goal node 

    else if(rigting.wallR != true) //checks if there is a wall on the right 
    { 
     pos += 1; 
     move(rigting.right, pos); //moves right 

     showLabel(pos); 
     return true; 
    } 

    else if(rigting.wallD != true) //checks if there is a wall below 
    { 
     pos += 10; 
     move(rigting.down, pos); //moves down 

     showLabel(pos); 
     return true; 
    } 

    else if(rigting.wallL != true) //checks if there is a wall on the left 
    { 
     pos -= 1; 
     move(rigting.left, pos); //moves left 

     showLabel(pos); 
     return true; 
    } 

    else if(rigting.wallU != true) //checks if there is a wall above 
    { 
     pos -= 10; 
     move(rigting.up, pos); //moves up 

     showLabel(pos); 
     return true; 
    } 

    return false; //I know this return is incorrect, but it won't run without one 
}

public boolean move(Maze rigting,int pos) //Righting = direction 
{ 
    if(rigting.goal == true) 
     return true; 

    return (rigting.wallR != true) ? move(rigting.right, pos += 1) : false || 
    (rigting.wallD != true) ? move(rigting.down, pos += 10) : false || 
    (rigting.wallL != true) ? move(rigting.left, pos -= 1) : false || 
    (rigting.wallU != true) ? move(rigting.up, pos -= 10) : false; 
}

這兩個給計算器例外...
我覺得我的錯誤是，如果右側牆壁上，然後右擊鏈接是null。如果我能以某種方式讓，沒有一個環節是null，那我就不需要布爾wallRight等，但我不知道如何實現這一點。

我真的很感激，如果你能在正確的方向給我！我只需要在10月10日提交項目，所以如果我完全錯了，我不介意重新開始！

來源

2012-09-29 Pierre

沒有真正讀懂了這一切，但在一般情況下，當你有一個遞歸函數，你會得到計算器，如果你不小心得到一些無限遞歸。因此，通過該程序並尋找。此外，這是Java？爲它添加標籤。 – keyser

我不知道Netbeans有一個step功能，會檢查出來，謝謝！是的，這是Java。我在遞歸方面非常新，這是我的第一個遞歸方法，我知道它是錯誤的。謝謝回覆！ – Pierre

皮埃爾，從學術的角度看，我相信，你的教授希望你能實現像**Trémaux的算法一個衆所周知的解決方案**。從[維基百科的迷宮求解算法]開始（http://en.wikipedia.org/wiki/Maze_solving_algorithm）文章。[本網站]（http://www.astrolog.org/labyrnth/algrithm.htm）也可能有用。 –

因爲這是你的功課，我不會給你這裏的解決方案，但一些提示。

你的第一個解決方案沒有後續調用的結果考慮move()，因此只有遞歸結束，如果你達到了目標（accidentially）。
在你的第二個解決方案，您考慮的結果，但不是一個情況下，你在哪裏在一個循環中移動準備。您需要標記已經訪問過的節點並在那裏打破（返回值爲false）。

對於遞歸，最好先從break-condition開始（如你所做的那樣），然後實現一個簡單的例子（例如總是向右）。管理後，簡單的情況下，你可以添加其他（分公司）

來源

2012-09-30 08:36:36 Andy

遞歸與迷宮求解

回答

相關問題