Комбинации в пары - PullRequest
Новая
       9

Комбинации в пары

1 голос
/ 24 марта 2010

Я работаю над направленной сетевой проблемой и пытаюсь вычислить все допустимые пути между двумя точками. Мне нужен способ посмотреть на пути до 30 "поездок" (представленных парой [origin, destination]) в длину. Полный маршрут состоит из серии этих пар: 

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

начальный город, конечный город и параметры длины маршрутов.

расстояние проверяет, является ли маршрут жизнеспособным, и routFromCity возвращает присоединенные узлы каждому каналу в городе.

У меня такое ощущение, что есть гораздо более эффективный способ создания всех маршрутов, особенно когда я продвигаюсь к еще большему количеству шагов, но, похоже, я не могу заставить что-то еще работать.

1 Ответ

0 голосов
/ 24 марта 2010

Вы можете использовать рекурсивную функцию. Ваш 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)]
...