Kombinationen in Paare

Question

Ich arbeite an einem gerichteten Netzwerk Problem und versuchen, alle gültigen Pfade zwischen zwei Punkten zu berechnen. Ich muß einen Weg zu Blick auf Pfade bis zu 30 „Trips“ (dargestellt durch ein [Ursprung, Ziel] Paar) in der Länge. Die vollständige Route wird dann aus einer Reihe dieser Paare:

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

Bisher meine beste Lösung ist wie folgt:

    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

Wo numRoutes zugeführt wird mein Netzwerk Graphen, wo Zahlen Abstände darstellen:

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

eine Start Stadt, ein Ende Stadt und die Parameter für die Länge der Strecken.

Entfernung überprüft, ob eine Route ist lebens- und routesFromCity gibt die angeschlossenen Knoten zu jedem in der Stadt eingespeist.

Ich habe das Gefühl, es gibt eine wesentlich effizientere Art und Weise alle Routen zu erzeugen, vor allem als ich auf vielen weiteren Schritte bewegen, aber ich kann nicht scheinen, etwas anderes zu Arbeit zu erhalten.

Answer 1

Sie könnten eine rekursive Funktion verwenden. Ihre maxStops kann ein Parameter sein und jedes Mal, wenn Sie diese um 1 zu verringern rufen Wenn minStops 0 ist, können Sie ein Ergebnis liefern, wenn die maxStops 0 Sie stoppen Rekursion.

Hier ist ein Codebeispiel:

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

Ausgabe:

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