通過reccursion找到所有可能的路線

Question

因此，我一直在這方面努力，只是似乎無法解決這個問題。我有一個列有開始城市和目標城市的「道路」列表。通過遞歸，我必須找到所有可能的路線。我目前的代碼只找到最長的路線。 我能做些什麼來解決這個問題？

道路：

Colorado Springs,Denver 
Denver,Loveland 
Loveland,Fort Collins 
Loveland,Greeley 
Greeley,Fort Collins 
Fort Collins,Cheyenne 
Fort Collins,Laramie 
Laramie,Cheyenne 

電流輸出：

All paths from Colorado Springs to Fort Collins are: 
1. [Colorado Springs, Denver, Loveland, Fort Collins] 
2. [Colorado Springs, Denver, Loveland, Greeley, Fort Collins] 
3. [Colorado Springs, Denver, Loveland, Greeley, Fort Collins, Loveland, Greeley, Fort Collins] 

編輯更新的代碼： 現在我得到額外的輸出...

public ArrayList<String> findPath2(String startCity, String goalCity, String oStartCity, ArrayList<String> route){ 

    //see if goal city possible 
    if(tester(goalCity) != true){ 
     return null; 
    } 

    ///Base Case//// 
    if(startCity.equals(goalCity)){ 
     route.add(goalCity); 
     String derp = route.toString(); 
     paths.add(derp); 
     System.out.println(derp); 
     //return route; 
    }else{ 
     for (int i = 0; i < theRoads.size(); i ++){ 
      if(theRoads.get(i).isFrom(startCity)){ 


       route.add(startCity); 
       findPath2(theRoads.get(i).endsAt(), goalCity, oStartCity, route); 

       //System.out.println(route); 
       //course = startCity + " -> " + course; 

       for (int l = i+1; l < theRoads.size(); l ++){ 
        if(theRoads.get(l).isFrom(startCity) && !(theRoads.get(l).startsAt().equals(goalCity))){ 
         System.out.println("SPLIT"); 

         route.remove(goalCity); 
         findPath2(theRoads.get(l).endsAt(), goalCity, oStartCity, route); 
         System.out.println("SPLIT RETURNING"); 

        } 
       } 

       //return route; 
      } 
     } 
    } 
    return route; 
} 

而且我所有的代碼，如果任何人都有興趣： http://pastebin.com/3yeBU2fn

2ND編輯：@Vandale

仍然不能得到它的工作，但這樣的事情？

public ArrayList<String> findPath2(String startCity, String goalCity, ArrayList<String> route){ 

     ArrayList<String> course = new ArrayList<>(); 

     if(startCity.equals(goalCity)){ 
      course.add(startCity); 
     }else{ 
      route.add(startCity); 
      for (int i = 0; i < theRoads.size(); i ++){ 
       if(theRoads.get(i).isFrom(startCity)){ 

        for (int l = 0; l < route.size(); l ++){ 
         //check if city has already been visited && if its possible to get to goal city (not sure if this works) 
         if(!(route.get(l).equals(startCity)) && (findPath2(theRoads.get(l).endsAt(), goalCity, route).equals(goalCity))){ 

          course.add(startCity + "->" + findPath2(theRoads.get(l).endsAt(), goalCity, route)); 

         } 
        } 
       } 
      } 
      route.remove(startCity); 
     } 
     System.out.println(course); 
     return course; 
    } 

感謝您的幫助！

Answer 1

oStartCity在您的方法的主體中從未實際使用過，因此您可以擺脫它。

一種方式來做到這一點是因爲遵循

Create empty list of paths 
if at target city 
    add current city to paths 
else 
    add current city to list of visited cities 
    for each city connected to this 
     if not already visited city and city has path to the target city 
      add current city + each one of connected cities paths to paths 
    remove current city from list of visited cities 
return paths 

爲了保持跟蹤你已經訪問過的城市，你應該使用類似一個HashSet，應通過在作爲參數傳遞給函數。

需要注意的一件事是，如果沒有到目的地城市的路徑，那麼該函數將返回一個空列表，您可以使用它來檢查是否有任何路徑。如果你使用這個，你不需要打電話給測試人員。

Answer 2

所以我想通了，希望這有助於未來的人！

public void findAllPaths(String startCity, String goalCity){ 
     clearPaths(); 
     findPathHelps(startCity, goalCity, ""); 
    } 

    private void findPathHelps(String startCity, String goalCity, String path){ 
     //base 
     if(startCity.equals(goalCity)) 
      paths.add(path + goalCity); 
     //cycle through 
     for(Road road : this.roads) 
      if(road.isFrom(startCity)) 
       //recursion and stuff 
      findPathHelps(road.endsAt(), goalCity, path+startCity+"->"); 
    }