0

Dijkstra Algorithm のこの回答をプロジェクトにコピーして貼り付けました。いくつかの簡単なテストの後、問題ないように見えました。

私の特定の実装では、ノードのリストを返すアルゴリズムが必要です。そのため、常にリストを返すように元のコードを変更する必要があります。より具体的には、そこにあるすべての行を削除しましたreturn "string"。私が変更したコードは次のとおりです。

## using Dijkstra Algorithm ##
def choosePath(s, t):
    net = {'0':{'1':138, '9':150},
       '1':{'0':138, '2':178, '8':194},
       '2':{'1':178, '3':47.5},
       '3':{'2':47.5, '4':70},
       '4':{'3':70, '5':70},
       '5':{'4':70, '6':36},
       '6':{'5':36, '7':50},
       '7':{'6':50, '8':81},
       '8':{'7':81, '9':138, '1':194},
       '9':{'8':138, '0':150}}
    # sanity check
    if s == t:
        return []
    # create a labels dictionary
    labels={}
    # record whether a label was updated
    order={}
    # populate an initial labels dictionary
    for i in net.keys():
        if i == s: labels[i] = 0 # shortest distance form s to s is 0
        else: labels[i] = float("inf") # initial labels are infinity
    from copy import copy
    drop1 = copy(labels) # used for looping
    ## begin algorithm
    while len(drop1) > 0:
        # find the key with the lowest label
        minNode = min(drop1, key = drop1.get) #minNode is the node with the smallest label
        # update labels for nodes that are connected to minNode
        for i in net[minNode]:
            if labels[i] > (labels[minNode] + net[minNode][i]):
                labels[i] = labels[minNode] + net[minNode][i]
                drop1[i] = labels[minNode] + net[minNode][i]
                order[i] = minNode
        del drop1[minNode] # once a node has been visited, it's excluded from drop1
    ## end algorithm
    # print shortest path
    temp = copy(t)
    rpath = []
    path = []
    while 1:
        rpath.append(temp)
        if order.has_key(temp):
            temp = order[temp]
        if temp == s:
            rpath.append(temp)
            break
    for j in range(len(rpath)-1,-1,-1):
        path.append(rpath[j])
    return [junctions[int(elem)] for elem in path]

その後、実行すると、次のエラーが発生します。

>>> Traceback (most recent call last):
  File "C:\Users\...\simulation.py", line 162, in choosePath
    rpath.append(temp)
MemoryError

明らかに、これは return "string" 行を削除したためです。しかし、どの削除がそれを死に至らしめるのかを見つけることができませんでした. なぜそうなのですか？

どうすれば再び機能し、常に文字列ではなくリストを返すことができますか?

4

1 に答える 1

2

あなたの問題は、間違った引数を関数に渡していることだと思います。に電話したいchoosePath('0', '9')。弦。整数ではありません。

コミカルなのは、削除したプログラムの一部がまだそこにある場合、これをキャッチしてプログラムを停止したことです。この部分で、入力が間違っているかどうかをキャッチします。

if net.has_key(s)==False:
    return "There is no start node called " + str(s) + "."
if net.has_key(t)==False:
    return "There is no terminal node called " + str(t) + "."

この部分で、解に至らない場合はキャッチします。

else: return "There is no path from " + str(s) + " to " + str(t) + "."

あなたが言及したように、ネットでパスが保証されているため、サニティチェックは厳密には必要ありません。それでも、何かを変更することを選択した場合、コンピューターが明らかな間違いを指摘してくれるので、チェックは素晴らしいものです。1 つのオプションは、これらのメッセージを例外に置き換えることです。これは、何かひどく問題が発生しない限り、これらのメッセージは実際には表示されないためです。それが、次のコードで選択したものです。

class NoPathException(Exception):
    pass

def choosePath(s, t):
    net = {'0':{'1':138, '9':150},
       '1':{'0':138, '2':178, '8':194},
       '2':{'1':178, '3':47.5},
       '3':{'2':47.5, '4':70},
       '4':{'3':70, '5':70},
       '5':{'4':70, '6':36},
       '6':{'5':36, '7':50},
       '7':{'6':50, '8':81},
       '8':{'7':81, '9':138, '1':194},
       '9':{'8':138, '0':150}}
    # sanity check
    if s == t:
        return []
    if not net.has_key(s):
        raise ValueError("start node argument not in net")
    if not net.has_key(t):
        raise ValueError("end node argument not in net")
    # create a labels dictionary
    labels={}
    # record whether a label was updated
    order={}
    # populate an initial labels dictionary
    for i in net.keys():
        if i == s: labels[i] = 0 # shortest distance form s to s is 0
        else: labels[i] = float("inf") # initial labels are infinity
    from copy import copy
    drop1 = copy(labels) # used for looping
    ## begin algorithm
    while len(drop1) > 0:
        # find the key with the lowest label
        minNode = min(drop1, key = drop1.get) #minNode is the nod2 with the smallest label
        # update labels for nodes that are connected to minNode
        for i in net[minNode]:
            if labels[i] > (labels[minNode] + net[minNode][i]):
                labels[i] = labels[minNode] + net[minNode][i]
                drop1[i] = labels[minNode] + net[minNode][i]
                order[i] = minNode
        del drop1[minNode] # once a node has been visited, it's excluded from drop1
    ## end algorithm
    # print shortest path
    temp = copy(t)
    rpath = []
    path = []
    while 1:
        rpath.append(temp)
        if order.has_key(temp):
            temp = order[temp]
        else:
            raise NoPathException("no path to solution")
        if temp == s:
            rpath.append(temp)
            break
    for j in range(len(rpath)-1,-1,-1):
        path.append(rpath[j])

    return path

テスト

a = choosePath('3', '9')
print(a)
['3', '4', '5', '6', '7', '8', '9']

これはあなたが探している出力ですか？

于 2013-10-04T10:13:25.817 に答える