Комбинации в пары
-
22-09-2019 - |
Вопрос
Я работаю над проблемой направленной сети и пытаюсь вычислить все допустимые пути между двумя точками.Мне нужен способ просмотра путей длиной до 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]]
начальный город, конечный город и параметры длины маршрутов.
distance проверяет, является ли маршрут жизнеспособным, а RouteFromCity возвращает присоединенные узлы каждому питающемуся в городе.
У меня такое ощущение, что существует гораздо более эффективный способ создания всех маршрутов, особенно когда я продвигаюсь вперед на гораздо большем количестве шагов, но, похоже, ничего другого заставить работать не получается.
Решение
Вы можете использовать рекурсивную функцию.Ваш 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)]