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です。ただし、プログラムは距離も出力する必要があるため、実際には答えが必要です。 be [10、["A"、 "C"、 "D"、 "E"]]

4

2 に答える 2

1

典型的な最短経路問題のように見えます。明らかなアプローチはダイクストラを使用することですが、そこにはもっとクールなアルゴリズムがあります。たとえば、これは私がコードゴルフセッションでハッキングしたものです。

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'

だから...グラフアルゴリズムを読んでください、それらはそれほど難しいことではありません。そうすることを拒否した場合：私のコードゴルフされた不動点アルゴを理解して頑張ってください。

于 2012-09-28T23:19:29.910 に答える
1

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'))))

誤ったタプルの追加がどこで発生するかはよくわかりませんが、これから独自のソリューションを微調整できるはずです...

注：これにはヘルス警告が付属しています。すべてのコードを1行で記述しないでください。読みにくく、デバッグしにくく、一般的に悪い考えです。

于 2012-09-28T23:44:29.077 に答える