Des combinaisons en paires

Question

Je travaille sur un problème de réseau dirigé et d'essayer de calculer tous les chemins valides entre deux points. Je besoin d'un moyen de regarder des chemins jusqu'à 30 « voyages » (représentés par un [origine, destination] paire) de longueur. L'itinéraire complet est alors constitué 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 représentent des nombres où les 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 d'extrémité et les paramètres de la longueur des routes.

contrôles à distance si une route est viable et routesFromCity renvoie les noeuds attachés à chaque alimenté en ville.

J'ai le sentiment qu'il est un semble beaucoup plus moyen efficace de générer toutes les routes d'autant plus que je me déplace vers beaucoup d'autres étapes, mais je ne peux pas obtenir quoi que ce soit d'autre au travail.

Answer 1

Vous pouvez utiliser une fonction récursive. Votre maxStops peut être un paramètre et chaque fois que vous vous diminuez ce par 1. appel Lorsque minStops est 0, vous donner un résultat, quand les maxStops est 0 vous arrêtez récursion.

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