0

私を悩ませている何かについてあなたの助けが欲しい. 私は本当にこれを自分で理解しようとしましたが、数時間後に完全に立ち往生しているように感じます.

つまり、私は Python (私の第 2 言語) は初めてで、学部生の研究の一環として Dijkstra のアルゴリズムの実装を書いています。

奇妙な理由で、Unvisited.remove(Current) を使用して未訪問のセットから現在のノードを削除しようとすると、次のエラーが発生します。

Traceback (most recent call last):
Current Node: 
  File "H:\DijkstraShortestPath\src\Main.py", line 92, in <module>
    Unvisited.remove(Current)
ValueError: list.remove(x): x not in list
1
Unvisited Nodes: 
['1', '2', '3', '4', '5', '6', '7', '8']
Current Node: 
8
Unvisited Nodes: 
['2', '3', '4', '5', '6', '7', '8']

Current はリストから取得した値であるのに対し、Unvisited はリストであることに注意してください。

ここでいくつかのスレッドを調べたり、インターネットを精査したりした後、混乱を避けるためにコード全体を投稿することにしました。list.remove(x) がループにネストされているときに何らかの問題があることに気付きました (私のものも for ループにネストされています) が、すべての技術用語の下で何が起こっているのかわかりません。

なぜこれが問題なのか説明してもらえますか？修正するにはどうすればよいですか?

#Main File
#Excecutes the Dijkstra Shortest Path Algorithm

#import Create_Network #Generates Network with 5 OD pairs as replications

testfile = "\DijkstraShortestPath\Backup And Tests\TEST"
Arcfile = testfile + "\Arcs.txt"
ODfile = testfile + "\ODpairs.txt"
Nodefile = testfile + "\Nodes.txt"

#INITIALIZE ALGORITHM
#Populate label, visited, and unvisited sets
#For initial conditions, label is infinite for all nodes except origin
#For initial conditions, all nodes are unvisited (including origin)

LabelArray = [] #Stores the distance labels for each of the nodes; has length
                #equal to the number of nodes in the network
Unvisited = [] #Stores unvisited nodes, by NodeID
Visited = [] #Stores visited nodes, by NodeID
ODArray = [] #Stores Origin and Destination Pairs

#Get the origin and destination pair
with open(ODfile,'r') as f:
    for line in f:
        ODArray = line.strip().split(",")
Origin = ODArray[0]
Destination = ODArray[1]
#Set the first current node as the origin
Current = Origin

#Generate Unvisited nodes and Labels (all infinite, except origin)
with open(Nodefile,'r') as f:
    for line in f:
        LabelArray.append(float("inf")) #make all node distance labels infinite
        NodeID = line.strip().split(",")[0]
        Unvisited.append(NodeID) #Add NodeID to Unvisited

#Set distance for origin to zero
LabelArray[int(ODArray[0])-1] = float(0) #float(0) to match float("inf")

#Count number of lines and items in each line
#i.e., find out how many nodes and params for storage in ArcParams list
numarcs = 0
with open(Arcfile,'r') as f:
    for line in f:
        if line != '\n':
            numarcs = numarcs + 1 #integer
            numparams = len(line.strip().split(",")) #integer

#Store arc origin, destination, length to ArcParams list
ArcParams = [[0 for i in range(numparams)] for i in range(numarcs)]

with open(Arcfile,'r') as f:

    for line in f:
        params = line.strip().split(",")
        ArcParams[int(params[0])-1][0] = params[0]
        ArcParams[int(params[0])-1][1] = params[1]
        ArcParams[int(params[0])-1][2] = params[2]
        ArcParams[int(params[0])-1][3] = float(params[3])

#END INITIALIZATION

#BEGIN DIJKSTRA SHORTEST PATH, LOOPING OVER NODES IN NETWORK

for node in Unvisited:

    #Find the nodes adjacent to Current AND in Unvisited
    Adjacent = []

    for i in range(numarcs):
        if ArcParams[i][1] == Current: #search for origin = current
            if ArcParams[i][1] in Unvisited: #checks if nodes found are in Unvisited
                if ArcParams[i][1] != ArcParams[i][2]: #excludes Current as adjacent
                    Adjacent.append(ArcParams[i][2]) #Add node to Adjacent

    #For each adjacent node, update distance labels

    for node in Adjacent:
        temp = float(LabelArray[int(Current)-1]) + float(ArcParams[int(node)][3])

        if temp < LabelArray[int(node)-1]:
            LabelArray[int(node)-1] = temp

    #Add current node to Visited set
    print "Current Node: "
    print Current
    print "Unvisited Nodes: "
    print Unvisited

    Visited.append(Current)
    Unvisited.remove(Current)

    #Check for end-conditions; has destination entered Visited?
    #Or is the smallest tentative distance infinite? Stop both ways.

    if Destination in Visited:
        if LabelArray[int(Destination)-1] == inf:
            print "There is no feasible path"
        print "Shortest distance found!"
        print "Distance is: " + str(LabelArray[Destination-1])


    #Select the Unvisited node marked with smallest tentative distance
    MinDist = min(LabelArray[1:])
    MinNode = LabelArray.index(MinDist) + 1

    #Clear existing Current, set new Current
    Current = MinNode
4

1 に答える 1

0

あなたのコードは基本的にこれを行います：

for item in container:
    # stuff
    container.remove(item)
    # more stuff

反復処理中にコンテナーを変更すると、通常、コードが壊れます。Java 標準ライブラリには特定の例外 (ConcurrentModificationException) があり、これにより通常、プログラムはこの種の問題を回避できますが、Python は残念ながらそうではありません。あなたのループは間違ったことをするだけです。

ここでの状況は、古いジョーク、患者のようなものです:「これをすると痛いです。」医者：「そうしないでください。」

代わりに次のようにしてみてください。

container = [6, 7, 8]

while len(container) > 0:
    item = container.pop()
    # do something useful with item

これにより、最後に使用されたアイテムが最初に処理されます。たとえば、最初の反復では 8、次に 7、次に 6 が返されます。左から右に処理する場合は、collections.deque クラスを使用する必要があります。

import collections

container = collections.deque([6, 7, 8])

while len(container) > 0:
    item = container.popleft()
    # do something useful with item

また、コードに関するいくつかのスタイルのニッチ:

  • あなたのコードは PEP 8 コーディング スタイル ガイドに違反しています。変数には、words_separated_by_underscores で名前を付ける必要があります。クラス名の場合のみ大文字で始める必要があります。http://www.python.org/dev/peps/pep-0008/#global-variable-namesを参照してください。(私が提案したクラス deque もこのガイドに違反していますが、これは、PEP 8 が広く受け入れられる前の Python の初期の頃に作成されたものであり、その後は下位互換性のために変更できなかったためだと思います。 Py3K では変更されていません。手がかりがありません。)

  • バックスラッシュの使用も疑わしいです。次のように、バックスラッシュを含む文字列には Python の raw 文字列機能を使用する必要があります。

    testfile = r"c:\新しいフォルダ"

代替手段としては、代わりにスラッシュを使用する (Windows ファイルシステムで使用されます)、クロスプラットフォームの互換性のために os.path.join を使用する、コマンドライン引数でファイル名を受け入れる、または二重のバックスラッシュを使用することが含まれます。

于 2013-03-14T05:38:07.470 に答える