这现在已经成为一个带有变化的图形问题。
问题是一张有向无环图，它连接了不同站点之间的关系，目标是在乘坐火车/电车时最小化换乘次数。
例如，这个集合列表：
1,4,8,10 <-- 站点 A
1,2,3,4,11,15 <-- 站点 B
2,4,20,21 <-- 站点 C
2,30 <-- 站点 D，目的地
他需要选择他到达和离开的站点上有的线路，例如，他不能从站点A选择10号线，因为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-----
如果我们认为考虑中的线路必须在至少两个连续站之间运行，那么我将用等号突出显示可选线路：
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-----
然后他需要选择一种从A到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), ))
这段代码输出：
可能的路线：[[1, 4], [2, 4], [2]]
最佳选择：[4, 4, 2]
正如我所说，我列出了在站点之间的路线，并且上面的解决方案可以作为你需要从每个站点下车的路线或者你需要到达下一个站点的路线。
所以路线是：
- 在A站点搭乘4号线并乘坐到B站点，然后到C站点
- 在C站点搭乘2号线并乘坐到D站点
这里可能有一些边缘情况，上述代码可能无法处理。
然而，我不再为此问题烦恼。提问者完全无法清晰、简洁地表达他的问题，我担心对上述文本和/或代码进行任何更正以适应最新评论都只会引起更多的评论，导致问题的又一个版本等等。提问者已经竭尽全力避免回答直接的问题或解释问题。
