gpt4 book ai didi

python - 将矢量化与 numpy 结合用于 Bellman-Ford 算法

转载 作者:太空宇宙 更新时间:2023-11-04 06:33:22 25 4
gpt4 key购买 nike

我一直在努力编写 Bellman Ford 算法来寻找图中的最短路径,虽然我有一个可行的解决方案,但它运行得不是很快,我被引导相信它可能是如果我使用 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 对其进行矢量化,但我不太确定该怎么做,因为矩阵/二维数组在每次迭代时都会发生变化。

如果有人对我需要做什么有任何想法,甚至可以阅读一些可以帮助我前进的东西,那就太棒了。

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

我写了一个更新版本以考虑 Jaime 的评论:

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])

最佳答案

在听从 Jaime 的建议后,我得到了以下矢量化代码:

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])

关于python - 将矢量化与 numpy 结合用于 Bellman-Ford 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14349084/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com