0

一方面，我有一个griddefaultdict，它将每个节点的相邻节点存储在网格上及其权重（在下面的示例中均为 1）。

        node   (w  nbr_node)
grid = { 0:   [(1, -5), (1, -4), (1, -3), (1, -1), (1, 1), (1, 3), (1, 4), (1, 5)], 
         1:   [(1, -4), (1, -3), (1, -2), (1, 0), (1, 2), (1, 4), (1, 5), (1, 6)], 
         2:   [(1, -3), (1, -2), (1, -1), (1, 1), (1, 3), (1, 5), (1, 6), (1, 7)], 
         3:   [(1, -2), (1, -1), (1, 0), (1, 2), (1, 4), (1, 6), (1, 7), (1, 8)],
        ...
        }

另一方面，我有一个Djisktra函数可以计算该网格上 2 个节点之间的最短路径。该算法使用该heapq模块并且工作得非常好。

import heapq

def Dijkstra(s, e, grid): #startpoint, endpoint, grid
    visited = set()
    distances = {s: 0} 
    p = {} 
    queue = [(0, s)] 

    while queue != []:

        weight, node = heappop(queue) 
        if node in visited: 
            continue

        visited.add(node) 

        for n_weight, n_node in grid[node]: 
            if n_node in visited: 
                continue

            total = weight + n_weight 

            if n_node not in distances or distances[n_node] > total: 

                distances[n_node] = total
                heappush(queue, (total, n_node))
                p[n_node] = node

问题：多次调用 Djikstra 函数时，是......无缘无故heappush在字典中添加新键！grid

这是一个MCVE：

from collections import defaultdict

# Creating the dictionnary
grid = defaultdict(list) 
N = 4
kernel = (-N-1, -N, -N+1, -1, 1, N-1, N, N+1)

for i in range(N*N): 
    for n in kernel:
        if i > N and i < (N*N) - 1 - N and (i%N) > 0 and (i%N) < N - 1:
            grid[i].append((1, i+n))



# Calling Djikstra multiple times
keys = [*range(N*N)]

while keys:

    k1, k2 = random.sample(keys, 2)

    Dijkstra(k1, k2, grid) 

    keys.remove(k1)
    keys.remove(k2)

原来的grid默认字典：

dict_keys([5, 6, 9, 10])

Djikstra...并在多次调用该函数后：

dict_keys([5, 6, 9, 10, 4, 0, 1, 2, 8, 3, 7, 11, 12, 13, 14, 15])

Djikstra当多次调用该函数时 heappush（只是在最后评论 heappush）：

dict_keys([5, 6, 9, 10])

问题：

  • 我怎样才能避免这种奇怪的行为？

请注意，我使用的是 Python 2.7，不能使用 numpy。

4

1 回答 1

1

我可以复制和修复。问题在于您正在构建的方式grid：它包含不在示例中从 -4 到 0 以及从 16 到 20 的键中的值。所以你把那些不存在的节点推到头上，然后弹出它们。

最后执行for n_weight, n_node in grid[node]:wherenode不（仍然）存在于grid. 与griddefaultdict 一样，新节点会自动插入一个空列表作为值。

修复是微不足道的（至少对于示例数据）：足以确保所有添加为网格的节点作为键存在模数：

for i in range(N*N): 
    for n in kernel:
        grid[i].append((1, (i+n + N + 1)%(N*N)))

但即使对于真实数据，确保网格值中存在的所有节点也存在于键中应该不是很困难......

顺便说一句，如果grid是一个简单dict的错误就会立即出现KeyErroron grid[node]。

于 2019-03-26T17:19:56.990 回答