前提・実現したいこと
閲覧ありがとうございます。
現在Pythonでプログラミングを学んでいるのですが幅優先探索で躓いてます。
下記のようなグラフを作り具体例のような処理を行いたいのですが上手く動作させることが出来ません。
どなたかご教授していただけると助かります。
具体例
1.Starting node(1000)の隣接ノードa,b,cの中で一番重みの大きいaに100移す。 2.Starting nodeの隣接ノード(a以外)で重みが一番小さいbに500移す。 3.Starting nodeの隣接ノード(a,b以外)で重みが一番小さいcに400移す。 4.aの隣接ノードの中で一番重みの小さいdに100移す。 5.bの隣接ノードで重みが一番小さいeに350移す。 6.bの隣接ノード(e以外)で重みが一番小さいfに150移す。 7.cの隣接ノードの中で一番重みの小さいgに400移す。 8.dの隣接ノードの中で一番重みの小さいhに100移す。 9.gの隣接ノードの中で一番重みの小さいiに400移す。 10.hの隣接ノードの中で一番重みの小さいEnd nodeに100移す。 11.eの隣接ノードで重みが一番小さいEnd nodeに350移す。 12.fの隣接ノードで重みが一番小さいEnd nodeに150移す。 13.iの隣接ノードで重みが一番小さいEnd nodeに400移す。
ソースコード
python
1#graph 2graph = {} 3graph["start"] = {} 4graph["start"]["a"] = 1 5graph["start"]["b"] = 3 6graph["start"]["c"] = 4 7 8graph["a"] = {} 9graph["a"]["d"] = 5 10graph["d"] = {} 11graph["d"]["h"] = 7 12graph["h"] = {} 13graph["h"]["end"] = 2 14 15graph["b"] = {} 16graph["b"]["e"] = 1 17graph["b"]["f"] = 2 18graph["e"] = {} 19graph["e"]["end"] = 3 20graph["f"] = {} 21graph["f"]["end"] = 7 22 23graph["c"] = {} 24graph["c"]["g"] = 4 25graph["g"] = {} 26graph["g"]["i"] = 10 27graph["i"] = {} 28graph["i"]["end"] = 1 29 30graph["end"] = {} 31 32#cost 33infinity = float("inf") 34costs = {} 35costs["a"] = 100 36costs["d"] = 100 37costs["h"] = 100 38 39costs["b"] = 500 40costs["e"] = 350 41costs["f"] = 150 42 43costs["c"] = 400 44costs["g"] = 400 45costs["i"] = 400 46costs["end"] = infinity 47 48# the parents table 49parents = {} 50parents["a"] = "start" 51parents["d"] = "a" 52parents["h"] = "d" 53 54parents["b"] = "start" 55parents["e"] = "b" 56parents["f"] = "b" 57 58parents["c"] = "start" 59parents["g"] = "c" 60parents["i"] = "g" 61 62parents["end"] = None 63 64processed = [] 65 66def find_lowest_cost_node(costs): 67 lowest_cost = float("end") 68 lowest_cost_node = None 69 # Go through each node. 70 for node in costs: 71 cost = costs[node] 72 # If it's the lowest cost so far and hasn't been processed yet... 73 if cost < lowest_cost and node not in processed: 74 # ... set it as the new lowest-cost node. 75 lowest_cost = cost 76 lowest_cost_node = node 77 return lowest_cost_node 78 79# Find the lowest-cost node that you haven't processed yet. 80node = find_lowest_cost_node(costs) 81# If you've processed all the nodes, this while loop is done. 82while node is not None: 83 cost = costs[node] 84 # Go through all the neighbors of this node. 85 neighbors = graph[node] 86 for n in neighbors.keys(): 87 new_cost = cost + neighbors[n] 88 # If it's cheaper to get to this neighbor by going through this node... 89 if costs[n] > new_cost: 90 # ... update the cost for this node. 91 costs[n] = new_cost 92 # This node becomes the new parent for this neighbor. 93 parents[n] = node 94 # Mark the node as processed. 95 processed.append(node) 96 # Find the next node to process, and loop. 97 node = find_lowest_cost_node(costs) 98 99print "Cost from the start to each node:" 100print costs
発生している問題・エラーメッセージ
Traceback (most recent call last): File "sample.py", line 76, in <module> node = find_lowest_cost_node(costs) File "sample.py", line 63, in find_lowest_cost_node lowest_cost = float("end") ValueError: could not convert string to float: end
試したこと
本やネットで調べながら試行錯誤してみたのですがダメでした。
補足情報(FW/ツールのバージョンなど)
開発環境
Ubuntu18.04
python2.7
「上手く動作させることが出来ません」とは具体的にどんな状況でしょうか。開発環境でpython2.7とpython3.6.7が二つ挙げられているのはありえません。両方インストールされていても、プログラムを実行するのはどちらかのpythonに限られるはずです(構文を見る限りpython2のようですが)
python2.7を使用しているのでpython3.6.7の方を削除しました。エラーコードを追加しました。
すみません、自分の記入ミスでした。よく見直したら63行目を書き間違えてました。
そうですね。。。"end"はfloatになりません。そこを修正して動きましたか?
無事動きました。お騒がせしました。
では質問を自己解決扱いでクローズしておいてください
回答1件
あなたの回答
tips
プレビュー