Это теперь превратилось в проблему построения графиков с поворотом.
Проблема заключается в направленном ациклическом графике связей между остановками, и цель состоит в том, чтобы минимизировать число переключателей линий при поездке на поезде /трамвай.
т.е.этот список сетов:
1,4,8,10 <-- stop A
1,2,3,4,11,15 <-- stop B
2,4,20,21 <-- stop C
2,30 <-- stop D, destination
Ему нужно выбрать линии, доступные на его остановке выхода, и остановке его прибытия, поэтому, например, он не может выбрать 10 из остановки A, потому что 10 не делаетперейти к остановке B.
Итак, это набор доступных линий и остановок, на которых они останавливаются:
A B C D
line 1 -----X-----X-----------------
line 2 -----------X-----X-----X-----
line 3 -----------X-----------------
line 4 -----X-----X-----X-----------
line 8 -----X-----------------------
line 10 -----X-----------------------
line 11 -----------X-----------------
line 15 -----------X-----------------
line 20 -----------------X-----------
line 21 -----------------X-----------
line 30 -----------------------X-----
Если мы считаем, что рассматриваемая линия должна проходить как минимум между 2последовательные остановки, позвольте мне выделить возможные варианты линий с одинаковыми знаками:
A B C D
line 1 -----X=====X-----------------
line 2 -----------X=====X=====X-----
line 3 -----------X-----------------
line 4 -----X=====X=====X-----------
line 8 -----X-----------------------
line 10 -----X-----------------------
line 11 -----------X-----------------
line 15 -----------X-----------------
line 20 -----------------X-----------
line 21 -----------------X-----------
line 30 -----------------------X----- Затем ему нужно выбрать путь, который переносит его из А в D, с минимальным числом переключателей линий.
Поскольку он объяснил, что сначала ему нужны самые длинные поездки, следующая последовательность кажется наилучшим решением:
- взять линию 4 от остановки A до остановки C, а затем переключиться на линию 2 с C на D
Пример кода:
stops = [
[1, 4, 8, 10],
[1,2,3,4,11,15],
[2,4,20,21],
[2,30],
]
def calculate_possible_exit_lines(stops):
"""
only return lines that are available at both exit
and arrival stops, discard the rest.
"""
result = []
for index in range(0, len(stops) - 1):
lines = []
for value in stops[index]:
if value in stops[index + 1]:
lines.append(value)
result.append(lines)
return result
def all_combinations(lines):
"""
produce all combinations which travel from one end
of the journey to the other, across available lines.
"""
if not lines:
yield []
else:
for line in lines[0]:
for rest_combination in all_combinations(lines[1:]):
yield [line] + rest_combination
def reduce(combination):
"""
reduce a combination by returning the number of
times each value appear consecutively, ie.
[1,1,4,4,3] would return [2,2,1] since
the 1's appear twice, the 4's appear twice, and
the 3 only appear once.
"""
result = []
while combination:
count = 1
value = combination[0]
combination = combination[1:]
while combination and combination[0] == value:
combination = combination[1:]
count += 1
result.append(count)
return tuple(result)
def calculate_best_choice(lines):
"""
find the best choice by reducing each available
combination down to the number of stops you can
sit on a single line before having to switch,
and then picking the one that has the most stops
first, and then so on.
"""
available = []
for combination in all_combinations(lines):
count_stops = reduce(combination)
available.append((count_stops, combination))
available = [k for k in reversed(sorted(available))]
return available[0][1]
possible_lines = calculate_possible_exit_lines(stops)
print("possible lines: %s" % (str(possible_lines), ))
best_choice = calculate_best_choice(possible_lines)
print("best choice: %s" % (str(best_choice), ))
Этот код печатает:
possible lines: [[1, 4], [2, 4], [2]]
best choice: [4, 4, 2]
Поскольку, как я уже сказал, я перечисляю строки между остановками , и вышеупомянутое решение может считаться как строк, которые вы должны еxit с каждой остановки или линий, по которым вы должны прибыть на следующую остановку .
Таким образом, маршрут:
- Перейдите на линию 4 востановитесь A и езжайте на этом до остановки B, затем до остановки C
- Перейдите на линию 2 на остановке C и езжайте по ней до остановки D
Возможно, здесь есть крайние случаичто приведенный выше код не работает.
Тем не менее, я не беспокоюсь больше об этом вопросе.ФП продемонстрировал полную неспособность изложить свой вопрос в четкой и сжатой форме, и я боюсь, что любые исправления в приведенном выше тексте и / или коде для учета последних комментариев будут только вызывать больше комментариев, что приводит к еще одной версиивопрос и так до бесконечности.ОП пошел на все, чтобы избежать ответов на прямые вопросы или объяснить проблему.