2

私は、グラフ内の最短経路を見つけるためのベルマン フォード アルゴリズムを書いてみました。実用的なソリューションを手に入れましたが、それほど速くは実行されません。私の現在のアプローチの代わりにnumpyを使用してください。

これは私が for ループを使用している解決策です:

import os                    
file = open(os.path.dirname(os.path.realpath(__file__)) + "/g_small.txt")

vertices, edges = map(lambda x: int(x), file.readline().replace("\n", "").split(" "))

adjacency_list = [[] for k in xrange(vertices)]
for line in file.readlines():
    tail, head, weight = line.split(" ")
    adjacency_list[int(head)-1].append({"from" : int(tail), "weight" : int(weight)})

n = vertices

shortest_paths = []
s=2

cache = [[0 for k in xrange(vertices)] for j in xrange(vertices)]
cache[0][s] = 0

for v in range(0, vertices):
    if v != s:
    cache[0][v] = float("inf")

# this can be done with numpy I think?
for i in range(1, vertices):
    for v in range(0, vertices):
        adjacent_nodes = adjacency_list[v]

        least_adjacent_cost = float("inf")
        for node in adjacent_nodes:
            adjacent_cost = cache[i-1][node["from"]-1] + node["weight"]
            if adjacent_cost < least_adjacent_cost:
                least_adjacent_cost = adjacent_cost

        cache[i][v] = min(cache[i-1][v], least_adjacent_cost)

shortest_paths.append([s, cache[vertices-1]])

for path in shortest_paths:
    print(str(path[1]))

shortest_path = min(reduce(lambda x, y: x + y, map(lambda x: x[1], shortest_paths)))  
print("Shortest Path: " + str(shortest_path))

入力ファイルはこんな感じ -> https://github.com/mneedham/algorithms2/blob/master/shortestpath/g_small.txt

ネストされたループが半分ほど下にあることを除いて、ほとんど面白くありません。numpy を使用してベクトル化しようとしましたが、反復ごとにマトリックス/2D 配列が変更されるため、その方法がよくわかりません。

誰かが私が何をする必要があるか、または読むべき何かについて何かアイデアを持っていれば、それは私の途中で私を助けるでしょう.

==================

ハイメのコメントを考慮して、更新版を作成しました。

s=0

def initialise_cache(vertices, s):
    cache = [0 for k in xrange(vertices)]
    cache[s] = 0

    for v in range(0, vertices):
        if v != s:
            cache[v] = float("inf")
    return cache    

cache = initialise_cache(vertices, s)

for i in range(1, vertices):
    previous_cache = deepcopy(cache)
    cache = initialise_cache(vertices, s)
    for v in range(0, vertices):
        adjacent_nodes = adjacency_list[v]

    least_adjacent_cost = float("inf")
    for node in adjacent_nodes:
        adjacent_cost = previous_cache[node["from"]-1] + node["weight"]
        if adjacent_cost < least_adjacent_cost:
            least_adjacent_cost = adjacent_cost

    cache[v] = min(previous_cache[v], least_adjacent_cost)

================

そして、今回はベクトル化を使用した別の新しいバージョン:

def initialise_cache(vertices, s):
    cache = empty(vertices)
    cache[:] = float("inf")
    cache[s] = 0
    return cache    

adjacency_matrix = zeros((vertices, vertices))
adjacency_matrix[:] = float("inf")
for line in file.readlines():
    tail, head, weight = line.split(" ")
    adjacency_matrix[int(head)-1][int(tail)-1] = int(weight)    

n = vertices
shortest_paths = []
s=2

cache = initialise_cache(vertices, s)
for i in range(1, vertices):
    previous_cache = cache
    combined = (previous_cache.T + adjacency_matrix).min(axis=1)
    cache = minimum(previous_cache, combined)

shortest_paths.append([s, cache])
4

1 に答える 1

0

ハイメのアドバイスに従って、次のベクトル化されたコードになりました。

def initialise_cache(vertices, s):
    cache = empty(vertices)
    cache[:] = float("inf")
    cache[s] = 0
    return cache    

adjacency_matrix = zeros((vertices, vertices))
adjacency_matrix[:] = float("inf")
for line in file.readlines():
    tail, head, weight = line.split(" ")
    adjacency_matrix[int(head)-1][int(tail)-1] = int(weight)    

n = vertices
shortest_paths = []
s=2

cache = initialise_cache(vertices, s)
for i in range(1, vertices):
    previous_cache = cache
    combined = (previous_cache.T + adjacency_matrix).min(axis=1)
    cache = minimum(previous_cache, combined)

shortest_paths.append([s, cache])
于 2013-01-17T19:53:32.993 に答える