Combinaisons par paires

Question

Je travaille sur un problème de réseau dirigé et essaye de calculer tous les chemins valides entre deux points. J'ai besoin d'un moyen de regarder les chemins jusqu'à 30 "voyages" (représentés par une paire [origine, destination]) de longueur. L'itinéraire complet est alors composé d'une série de ces paires:

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

Jusqu'à présent, ma meilleure solution est la suivante:

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 

Où numRoutes est alimenté mon graphique de réseau où les nombres représentent des distances:

[[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]] 

une ville de départ, une ville de destination et les paramètres pour la longueur des routes. Distance vérifie si une route est viable et routesFromCity renvoie les nœuds attachés à chaque ville alimentée. J'ai l'impression qu'il existe un moyen beaucoup plus efficace de générer toutes les routes, en particulier lorsque je me déplace vers plusieurs étapes, mais je n'arrive pas à faire quoi que ce soit d'autre.

Answer 1

Vous pouvez utiliser une fonction récursive. Votre maxStops peut être un paramètre et chaque fois que vous appelez, vous le diminuez de 1. Lorsque minStops vaut 0, vous obtenez un résultat. Lorsque maxStops vaut 0, vous arrêtez de récurser.

Voici un exemple de code:

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 

Sortie:

[(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)]