Я пытался написать алгоритм Беллмана Форда для поиска кратчайшего пути в графе, и хотя у меня есть работающее решение, оно работает не очень быстро, и я пришел к выводу, что он мог бы быть быстрее, если бы я используйте numpy вместо моего текущего подхода.
Это решение, которое я использую для циклов:
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, но я не совсем уверен, как это сделать, учитывая, что матричный/двумерный массив изменяется на каждой итерации.
Если у кого-то есть идеи о том, что мне нужно сделать, или даже что-то прочитать, что поможет мне на моем пути, это было бы здорово.
==================
Я написал обновленную версию, чтобы учесть комментарий Хайме:
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])
for i
нельзя векторизовать, аfor v
можно, хотя для этого потребуется превратитьadjacency_list
в один или несколько массивов. Можете ли вы заранее узнать максимальное количество смежных узлов для любого узла? Я предполагаю, что вы всегда можете создать массив(vertices, vertices)
, но это может занять очень много места для хранения. В связи с этим, почему вы делаете своиcache
vertices
строки длинными, когда используете только последнюю? Я думаю, вы могли бы управлять всем этим в одном списке. - person Jaime   schedule 16.01.2013