我目前正在嘗試從項目 euler 中解決問題 81。如何將帶有數(shù)字流的 txt 文件轉(zhuǎn)換為存儲圖形的字典？現(xiàn)在，我的計劃是將文本文件中的數(shù)字用逗號分隔（它們不是“預(yù)網(wǎng)格”，所以它不是 80 x 80 結(jié)構(gòu)）并將它們轉(zhuǎn)換成字典，我可以將它們存儲為圖形其中所有頂點垂直和水平連接所以取 txt 文件中的項目（使用 4 x 4 網(wǎng)格作為演示）："a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p"將它們轉(zhuǎn)換為存儲圖形的字典graph = { a: b, e b: a, c, f c: b, d, g etc etc ...} 我將使用 djkstra 的算法從中找到最小路徑，因為 txt 文件中的值實際上是整數(shù)并具有權(quán)重值PS這是解決問題的好方法嗎？
2 回答
慕萊塢森
TA貢獻1810條經(jīng)驗 獲得超4個贊
在問題 81 中，你只能向右或向下移動。所以你的 Dijkstra 算法需要一個有向圖。如果您使用字典作為圖形，則此 dict 中的每個值（列表）不得超過 2 個節(jié)點（您只能在 2 個方向上移動 -> 2 個鄰居）。您可以刪除if@AustinHastings 的最后一段代碼中的前兩個塊。否則，您將向 4 個方向移動并得到不同的結(jié)果。這是問題 81 中示例的解決方案。我使用了包networkx和jupyter notebook：
import networkx as nx
import numpy as np
import collections
a = np.matrix("""131 673 234 103 18;
201 96 342 965 150;
630 803 746 422 111;
537 699 497 121 956;
805 732 524 37 331""")
rows, columns = a.shape
# Part of @AustinHastings solution
graph = collections.defaultdict(list)
for r in range(rows):
for c in range(columns):
if c < columns - 1:
# get the right neighbor
graph[(r, c)].append((r, c+1))
if r < rows - 1:
# get the bottom neighbor
graph[(r, c)].append((r+1, c))
G = nx.from_dict_of_lists(graph, create_using=nx.DiGraph)
weights = {(row, col): {'weight': num} for row, r in enumerate(a.tolist()) for col, num in enumerate(r)}
nx.set_node_attributes(G, values=weights)
def weight(u, v, d):
return G.nodes[u].get('weight')/2 + G.nodes[v].get('weight')/2
target = tuple(i - 1 for i in a.shape)
path = nx.dijkstra_path(G, source=(0, 0), target=target, weight=weight)
print('Path: ', [a.item(i) for i in path])
%matplotlib inline
color_map = ['green' if n in path else 'red' for n in G.nodes()]
labels = nx.get_node_attributes(G, 'weight')
pos = {(r, c): (c, -r) for r, c in G.nodes()}
nx.draw(G, pos=pos, with_labels=True, node_size=1500, labels = labels, node_color=color_map)
輸出：
Path: [131, 201, 96, 342, 746, 422, 121, 37, 331]
慕容708150
TA貢獻1831條經(jīng)驗 獲得超4個贊
在問題 81 中，你只能向右或向下移動。所以你的 Dijkstra 算法需要一個有向圖。如果您使用字典作為圖形，則此 dict 中的每個值（列表）不得超過 2 個節(jié)點（您只能在 2 個方向上移動 -> 2 個鄰居）。您可以刪除if@AustinHastings 的最后一段代碼中的前兩個塊。否則，您將向 4 個方向移動并得到不同的結(jié)果。這是問題 81 中示例的解決方案。我使用了包networkx和jupyter notebook：
import networkx as nx
import numpy as np
import collections
a = np.matrix("""131 673 234 103 18;
201 96 342 965 150;
630 803 746 422 111;
537 699 497 121 956;
805 732 524 37 331""")
rows, columns = a.shape
# Part of @AustinHastings solution
graph = collections.defaultdict(list)
for r in range(rows):
for c in range(columns):
if c < columns - 1:
# get the right neighbor
graph[(r, c)].append((r, c+1))
if r < rows - 1:
# get the bottom neighbor
graph[(r, c)].append((r+1, c))
G = nx.from_dict_of_lists(graph, create_using=nx.DiGraph)
weights = {(row, col): {'weight': num} for row, r in enumerate(a.tolist()) for col, num in enumerate(r)}
nx.set_node_attributes(G, values=weights)
def weight(u, v, d):
return G.nodes[u].get('weight')/2 + G.nodes[v].get('weight')/2
target = tuple(i - 1 for i in a.shape)
path = nx.dijkstra_path(G, source=(0, 0), target=target, weight=weight)
print('Path: ', [a.item(i) for i in path])
%matplotlib inline
color_map = ['green' if n in path else 'red' for n in G.nodes()]
labels = nx.get_node_attributes(G, 'weight')
pos = {(r, c): (c, -r) for r, c in G.nodes()}
nx.draw(G, pos=pos, with_labels=True, node_size=1500, labels = labels, node_color=color_map)
輸出：
Path: [131, 201, 96, 342, 746, 422, 121, 37, 331]
添加回答
舉報
0/150
提交
取消