计算完全图中的距离度量

Question

假设我有一个数组，即Map。Map[i][j]表示area i和area j之间的距离。在这个定义下，我们得到：

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

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

我想构建一个返回指标D的函数func(Map,k)，而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)

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

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

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

Answer 1

为此，您可以使用A*算法，使用Map[i][j]作为到目标节点的最小剩余距离的启发式算法(假设，如您所说，所有i,j,x都使用Map[i][j] <= Map[i][x] + Map[x][j] )。与常规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]))

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

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)

这给出了len(path) >= k的结果[[4, 4, 3], [4, 2, 3], [3, 3, 2]]，或者len(path) == k的[[4, 4, 3], [4, 2, 5], [3, 5, 2]]。