0

我想编写一个程序，返回从 A 点到 E 点的最短距离。我编写了代码来获取长度，但我不知道如何实际获取这些点。

在此处输入图像描述

d  = {("A","A"):0, ("A","B"):1, ("A","C"):3, ("A","D"):7 , ("A","E"):101,
           ("B","A"):101, ("B","B"):0, ("B","C"):42, ("B","D"):6, ("B","E"):27,
           ("C","A"):101, ("C","B"):101, ("C","C"):0, ("C","D"):2, ("C","E"):13,
           ("D","A"):101, ("D","B"):101, ("D","C"):101, ("D","D"):0, ("D","E"):5,
           ("E","A"):101, ("E","B"):101, ("E","C"):101, ("E","D"):101, ("E","E"):0
    }

def shortestPath(Cities,Distances):
'''Returns the length of the shortest path from the first city in the list to the last city in the list, using only cities that appear in that list.'''
    if len(Cities)==1: return 0
    else: return min( map( lambda n: (Distances[Cities[0],Cities[n]] + shortestPath(Cities[n:],Distances)), range(1,len(Cities))) )

输入的答案：shortestPath(["A","B", "C", "D", "E"],d) 是 10。但程序也应该输出距离，所以答案实际上应该是为 [10, ["A", "C", "D", "E"]]

4

2 回答 2

1

如果您决定将其保留在一行中，则可以对代码进行一些小的更改：

def track_past_city(x,y):
    return (x[0]+y[0],x[1:]+y[1:]) #0 is how far you've gone, #[1:] is where you've been

def shortestPath(Cities,Distances):
    if len(Cities)==1: return 0, Cities[0]
    else: return min( map( lambda n: (track_past_city((Distances[Cities[0],Cities[n]],Cities[0]),shortestPath(Cities[n:],Distances))), range(1,len(Cities))) )


shortestPath(["A","B", "C", "D", "E"],d)
# (10, ('A', ('C', ('D', 'E'))))

我不太确定如何在哪里发生错误的元组添加，但是从这里你应该能够调整你自己的解决方案......

注意：这带有一个健康警告，你不应该将所有代码写在一行上，它很难阅读，很难调试，而且通常是个坏主意。

于 2012-09-28T23:44:29.077 回答
1

看起来像一个典型的最短路径问题。显而易见的方法是使用 dijkstra，但也有更酷的算法。例如，我在 codegolf 会话中破解了这个：

G,S,T=input();J={n:9e9if n!=T else 0for n in G}
while J[S]>1e9:J={n:0if n==T else min(c+J[d]for d,c in G[n].items())for n in G}
while S!=T:print S;S=min((c+J[d],d)for d,c in G[S].items())[1]

不过，您必须更改图形表示，但它会为此输入输出正确的最短路径（您的解释图）：

{'A': {'C': 3, 'B': 1, 'D': 7}, 'C': {'A': 3, 'B': 42, 'E': 13, 'D': 2}, 'B': {'A': 1, 'C': 42, 'E': 27, 'D': 6}, 'E': {'C': 13, 'B': 27, 'D': 5}, 'D': {'A': 7, 'B': 6, 'E': 5}}, 'A', 'E'

所以......阅读图算法，它们并不难。如果你拒绝这样做：祝你好运，理解我的 codegolfed fixpoint 算法。

于 2012-09-28T23:19:29.910 回答