給定距離計算所有可能的路徑

我有一個以下用Java編寫的路徑查找函數，需要一些工作。給定距離計算所有可能的路徑

我有一組彈簧杆，每個都有自己的「跳躍距離」。例如，具有值5的彈簧杆可以「跳」（移動）5個空格。我也有一個totalDistance變量，它保存了需要走過的距離。

用戶通過鍵盤提供輸入，其中第一個整數是距離，其餘整數是彈簧杆距離。同樣的彈簧杆可以根據需要多次使用，同樣，彈簧杆的移動距離> totalDistance也不需要。

我的算法幾乎可以按照需要工作，但由於循環迭代首先找到不同算法，因此忽略了某些組合，因此忽略了其他路徑的潛力。

我需要從本質上檢查一下路徑是否已經被計算出來，然後忽略當前的彈簧杆迭代並移動到下一個路徑。

任何人都可以幫忙嗎？以下是我找到路徑的算法。

/* 
* First integer in input 
*/ 
int totalDistance; 

/* 
* The remaining integers in the input 
*/ 
ArrayList<Integer> pogoSticks = new ArrayList<Integer>(); 


private void findPaths() { 
    ArrayList<ArrayList<Integer>> possibleSticks = new ArrayList<ArrayList<Integer>>(); 

    for (int i = 0; i < pogoSticks.size(); i++) { 

     int pogoStickDistance = pogoSticks.get(i); 

     if (pogoStickDistance == totalDistance) { 
      if (!possibleSticks.contains(new ArrayList<Integer>(pogoStickDistance))) { 
       ArrayList<Integer> list = new ArrayList<Integer>(); 
       list.add(pogoStickDistance); 
       possibleSticks.add(list); 
      } 
     } else if (pogoStickDistance < totalDistance) { 
      int remainingDistance = totalDistance; 
      ArrayList<Integer> possibleSubSticks = new ArrayList<Integer>(); 

      possibleSubSticks.add(pogoStickDistance); 
      remainingDistance -= pogoStickDistance; 

      for (int j = 0; j < pogoSticks.size(); j++) { 

       int pogoStickDistance1 = pogoSticks.get(j); 
       if (pogoStickDistance1 == remainingDistance) { 
        System.out.println(remainingDistance); 
        possibleSubSticks.add(pogoStickDistance1); 

        possibleSticks.add(possibleSubSticks); 
        break; 
       } else if (pogoStickDistance1 < remainingDistance) { 
        possibleSubSticks.add(pogoStickDistance1); 
        remainingDistance -= pogoStickDistance1; 
       } 

       if (j == (pogoSticks.size() - 1) && pogoStickDistance1 != remainingDistance) { 
        j = 0; 
       } 
      } 
     } 

    } 

    System.out.println(possibleSticks); 
}

輸出：

Enter input: 5 5 10 1 3 
[[5], [1, 1, 3], [3, 1, 1]]

前5是距離，其他數字是彈簧單高蹺距離。

我缺少諸如[1, 1, 1, 1, 1]路徑和[1, 3, 1]

來源

2016-02-02 bob

如果我沒有錯，你有另一個類似的問題[計算所有可能的路徑]（http://stackoverflow.com/questions/35144627/calculate-all-possible-paths-algorithm）？ –

是的，這個更新更多。 – bob

如果是這樣的話，爲什麼不更新前一個呢？或刪除以前也有可能 –

你可以看到所有可能的路徑探索的二叉樹在這裏您的解決方案

如果totaldistance = 5，你有兩種枝的1和3，那麼你可以看到已經達到解決方案的路徑和已經超出解決方案的路徑，不需要進一步考慮。

這個問題可以通過探索樹來解決（它可能是n-ary樹，在你有n種樹枝的情況下）。解決方案通常可以通過廣度優先搜索或深度優先搜索找到 - 您需要使用某種類型的隊列或堆棧。所以你需要廢棄你的解決方案並重新開始。

來源

2016-02-03 17:00:29 gpasch

給定距離計算所有可能的路徑

回答

相關問題