<p>在这种特定情况下,使用您的数据结构,您似乎应该能够并行运行两个场景:</p>
<ul>
<li>A的成本</li>
<li>B的成本</li>
</ul>
<p>您可以维护当前成本,并且您收集的数据在第三个元素中提供了“切换成本”。在</p>
<p>所以你需要问:哪个更便宜?是停留在起始路径上,还是切换到另一条路径上?在</p>
<pre><code>path_list = [
(50, 10, 30),
(5, 90, 20),
(40, 2, 25),
(10, 8, 0),
]
A = 0
B = 1
Switch = 2
def cheapest_path(path_list, path=None, history=None):
if history is not None:
# Terminate when path_list is empty
if not path_list:
return history
# Determine cost to stay this path, vs. cost to switch
step = path_list[0]
path_list = path_list[1:]
stay_on_path = cheapest_path(path_list, path, history + [step[path]])
switch_path = cheapest_path(path_list, B if path == A else A, history + [step[path], step[Switch]])
return switch_path if sum(switch_path) < sum(stay_on_path) else stay_on_path
else:
pathA = cheapest_path(path_list, A, [])
pathB = cheapest_path(path_list, B, [])
return pathA if sum(pathA) < sum(pathB) else pathB
print(", ".join(map(str, cheapest_path(path_list))))
</code></pre>