python-3.x - 计算完整图中的距离度量

Question

假设我有一个数组，即Map . Map[i][j]表示区域之间的距离 i和面积j .根据这个定义，我们得到:

a) Map[i][i]始终等于 0。

b) Map[i][k] <= Map[i][j] + Map[j][k]对于所有 i,j,k

我想构建一个函数 func(Map,k)返回一个指标 D , 而 D[i][j]是距离区域i的路线的最短距离前往区域j ，这条路线至少要经过k不同的区域。

这是我的 python 代码:

def func(Map,k):
    n=len(Map)    
    D_temp = [list(x) for x in Map]
    D = [list(x) for x in Map]
    for m in range(k - 1):    
        for i in range(n):
            for j in range(n):
                tmp = [D[i][x] + Map[x][j] for x in range(n) if x != i and x != j]
                D_temp[i][j] = min(tmp)
        D = [list(x) for x in D_temp]
    return D
func([[0, 2, 3], [2, 0, 1], [3, 1, 0]],2)

返回距离度量 D等于 [[4, 4, 3], [4, 2, 5], [3, 5, 2]]

D[0][0]等于 4 ，因为从area0的最短路线至 area0通过至少 2 个区域的是 { area0 --> area1 --> area0 }，路线的距离为Map[0][1] + Map[1][0] =2+2=4

想知道最好的方法是什么？

Answer 1

您可以为此使用 A* 算法，使用 Map[i][j]作为到目标节点的最小剩余距离的启发式(假设，如您所说，所有 Map[i][j] <= Map[i][x] + Map[x][j] 都是 i,j,x )。与常规 A* 的唯一区别是您只接受最小长度为 k 的路径。 .

import heapq
def min_path(Map, k, i, j):
    heap = [(0, 0, i, [])]
    while heap:
        _, cost, cur, path = heapq.heappop(heap)
        if cur == j and len(path) >= k:
            return cost
        for other in range(len(Map)):
            if other != cur:
                c = cost + Map[cur][other]
                heapq.heappush(heap, (c + Map[other][j], c, other, path + [other]))

更改您的 func使用此 min_path 返回列表理解相应地。

def func(Map, k):
    n = len(Map)  
    return [[min_path(Map, k, i, j) for i in range(n)] for j in range(n)]
res = func([[0, 2, 3], [2, 0, 1], [3, 1, 0]], 2)

这给了我结果 [[4, 4, 3], [4, 2, 3], [3, 3, 2]]对于 len(path) >= k , 或 [[4, 4, 3], [4, 2, 5], [3, 5, 2]]对于 len(path) == k .