組合成對

Question

我正在處理定向網絡問題並嘗試計算兩點之間的所有有效路徑。我需要一種方法來查看長達30個「行程」（由[起始，目的地]對代表）的路徑。然後，將整個路線由一系列這些對的：

route = [[start, city2], [city2, city3], [city3, city4], [city4, city5], [city5, city6], [city6, city7], [city7, city8], [city8, stop]] 

到目前爲止，我最好的解決辦法如下：

def numRoutes(graph, start, stop, minStops, maxStops): 
    routes = [] 

    route = [[start, stop]] 
    if distance(graph, route) != "NO SUCH ROUTE" and len(route) >= minStops and len(route) <= maxStops: 
      routes.append(route) 

    if maxStops >= 2: 
     for city2 in routesFromCity(graph, start): 
      route = [[start, city2],[city2, stop]] 
      if distance(graph, route) != "NO SUCH ROUTE" and len(route) >= minStops and len(route) <= maxStops: 
       routes.append(route) 
    if maxStops >= 3:  
     for city2 in routesFromCity(graph, start): 
      for city3 in routesFromCity(graph, city2): 
       route = [[start, city2], [city2, city3], [city3, stop]] 
       if distance(graph, route) != "NO SUCH ROUTE" and len(route) >= minStops and len(route) <= maxStops: 
        routes.append(route) 

    if maxStops >= 4: 
     for city2 in routesFromCity(graph, start): 
      for city3 in routesFromCity(graph, city2): 
       for city4 in routesFromCity(graph, city3): 
        route = [[start, city2], [city2, city3], [city3, city4], [city4, stop]] 
        if distance(graph, route) != "NO SUCH ROUTE" and len(route) >= minStops and len(route) <= maxStops: 
         routes.append(route) 
    if maxStops >= 5: 
     for city2 in routesFromCity(graph, start): 
      for city3 in routesFromCity(graph, city2): 
       for city4 in routesFromCity(graph, city3): 
        for city5 in routesFromCity(graph, city4): 
         route = [[start, city2], [city2, city3], [city3, city4], [city4, city5], [city5, stop]] 
         if distance(graph, route) != "NO SUCH ROUTE" and len(route) >= minStops and len(route) <= maxStops: 
          routes.append(route) 
return routes 

凡numRoutes被送到我的網絡圖，其中的數字代表的距離：

[[0, 5, 0, 5, 7], [0, 0, 4, 0, 0], [0, 0, 0, 8, 2], [0, 0, 8, 0, 6], [0, 3, 0, 0, 0]] 

開始城市，終點城市和路線長度的參數。

距離檢查路由是否可行，並且routesFromCity將附加節點返回給城市中的每個城市。

我感覺有一種更有效的方式來生成所有的路線，特別是當我朝着更多的步驟走，但我似乎無法得到任何其他工作。

Answer 1

您可以使用遞歸函數。你的maxStops可以是一個參數，每次你打電話給你時減1。當minStops爲0時，你得到一個結果，當maxStops爲0時，你停止遞歸。

下面是一個代碼示例：

def routesFromCity(x): 
    for i in range(2, 10): 
     yield x * i 

def findRoutes(start, stop, minStops, maxStops): 
    if start == stop: 
     if minStops <= 0: 
      yield [] 
    else: 
     if maxStops > 0: 
      for nextCity in routesFromCity(start): 
       for route in findRoutes(nextCity, stop, minStops - 1, maxStops - 1): 
        yield [(start, nextCity)] + route 

for route in findRoutes(1, 12, 2, 5): 
    print route 

輸出：

[(1, 2), (2, 4), (4, 12)] 
[(1, 2), (2, 6), (6, 12)] 
[(1, 2), (2, 12)] 
[(1, 3), (3, 6), (6, 12)] 
[(1, 3), (3, 12)] 
[(1, 4), (4, 12)] 
[(1, 6), (6, 12)]