以遞歸方法查找最小int（路徑大小）

我試圖在使用遞歸的迷宮中找到最小路徑大小。要做到這一點，迷宮必須經歷所有可能的路徑，然後不斷更新「最短長度」。以遞歸方法查找最小int（路徑大小）

我能夠通過所有可能的列表並打印這些座標和路徑大小，但我無法找到最小值，因爲上次找到的路徑總是更新爲「最短長度」。

所以，我想將所有的解決路徑長度到ArrayList<Integer> list的，然後創建遞歸之外的獨立的靜態類解決方法，在這裏我找到了最低，並返回它的價值，solve()方法，並繼續從那裏。這是做這件事的最佳方法嗎？或者我可以在solve()方法中找到最短長度和相應的座標嗎？

這是遞歸的情況下，什麼樣的代碼：

else { 
    for(int i = 0; i < directions.length; i++) 
    { 
    Coord nextSpot = currentSpot.addTo(directions[i]); 
    if(nextSpot.validSpot(maze)) 
     if(!newPath.contains(nextSpot)){ 

     ArrayList<Coord> solution = //The recursive call 
         solve(newPath,nextSpot,goal,maze); 

     if(solution != null){ 

      int shortestLength = 100; //arbitrary large length 
     // lengths.add(lengthSolution); ?? Possible alternative? 
      System.out.println(lengthSolution); 
      System.out.println(solution); 
      if(solution.size() < shortestLength){ 
      shortestLength = solution.size(); 
      System.out.println(shortestLength); 
      } 
     } 
    }//ifs 
    }//for 
    return null; 
}//else (recursive case)

來源

2015-04-05 kris

這有什麼錯* Dijstra算法*？ – 2015-04-05 19:41:12

@CommuSoft我看了那個教程，但我不確定我真的明白我將如何編寫代碼。這是否是這種情況的最佳方式？ – kris 2015-04-05 19:43:28

@ kat-如果你在實施Dijkstra的算法時遇到問題，也許一旦你從教程中練習。 'Commusoft'寫的是他對解決這個問題的看法。它必須是'Dijkstra的算法'！ – 2015-04-05 19:46:33

int globalsteps =0; 

int maze(x,y,steps) { 
    if(icangoup){ maze(x+1,y,steps +1);} 
    if(icangodown){ maze(x-1,y,steps +1);} 
    if(icangoleft){ maze(x,y+1,steps +1);} 
    if(icangoright){ maze(x,y-1,steps +1);} 
    if(ifoundtheexit!!!!) { 
     if(globalsteps == 0 || steps < globalsteps) 
      globalsteps = steps; 
     } 
    } 
}

來源

2015-04-05 19:50:02

以遞歸方法查找最小int（路徑大小）

回答

相關問題