Python：确定跨n个数组的路径中的每个步骤是否低于阈值

Question

给定n个整数数组，是否有一个好的算法来确定是否有一条路径穿过这些数组，使得沿着该路径的每个“步骤”的最小（欧几里德）距离低于某个阈值？也就是说，穿过所有数组的路径将只包括来自每个数组的一个成员，并且该路径的每个步骤的距离将由在给定步骤期间被比较的两个数组的值之间的绝对距离确定。例如，假设您有以下数组：

a = [1,3,7]
b = [10,13]
c = [13,24]

以及

threshold = 3

在这种情况下，您需要确定a和b中的任何元素之间的距离是否为3或更小，对于a和b中的所有元素对，实际上它们之间的距离为3或更小，您需要确定a中的给定成员或b中的给定成员之间的距离是否为3或更小来自c的任何成员。（在上面的示例中，每个步骤的距离低于阈值条件的整数的唯一路径是7-->；10-->；13。）

当数组的数目为3时，我是如何处理这样一个问题的：

from numpy import*

a = [1,3,7]
b = [10,13]
c = [13,24]
d = [45]

def find_path_across_three_arrays_with_threshold_value_three(a,b,c):
    '''this function takes three lists as input, and it determines whether
    there is a path across those lists for which each step of that path
    has a distance of three or less'''

    threshold = 3

    #start with a,b
    for i in a:
        for j in b:

            #if the absolute value of i-j is less than or equal to the threshold parameter (user-specified proximity value)
            if abs(i-j) <= threshold:

                for k in c:

                    if abs(i-k) <= threshold:
                        return i,j,k

                    elif abs(j-k) <= threshold:
                        return i,j,k

    #now start with a,c                    
    for i in a:
        for k in c:
            if abs(i-k) <= threshold:

                for j in b:

                    if abs(i-j) <= threshold:
                        return i,j,k
                    elif abs(j-k) <= threshold:
                        return i,j,k

    #finally, start with b,c
    for j in b:
        for k in c:
            if abs(j-k) <= threshold:

                for i in a:

                    if abs(i-j) <= threshold:
                        return i,j,k
                    elif abs(i-k) <= threshold:
                        return i,j,k


if find_path_across_three_arrays_with_threshold_value_three(a,b,c):
    print "ok"

但是，如果您事先不知道有多少个数组，那么最有效的方法是什么来计算所有n个数组之间是否有一条路径，从而使路径中每个“步”的距离都低于所需的阈值？Dijkstra算法是将这个问题推广到n个数组的最佳方法吗？你知道吗

编辑：

@Falko的方法对我有用：

import numpy as np
import itertools

my_list = [[1, 3, 7], [10, 13], [13, 24], [19], [16]]

def isPath(A, threshold):
        for i in range(len(A) - 1):
            #print "Finding edges from layer", i, "to", i + 1, "..."
            diffs = np.array(A[i]).reshape((-1, 1)) - np.array(A[i + 1]).reshape((1, -1))
            reached = np.any(np.abs(diffs) <= threshold, axis = 0)
            A[i + 1] = [A[i + 1][j] for j in range(len(reached)) if reached[j]]
            #print "Reachable nodes of next layer:", A[i + 1]
        return any(reached)

for i in itertools.permutations(my_list):
    new_list = []
    for j in i:
        new_list.extend([j])

    if isPath(new_list,3):
        print "threshold 3 match for ", new_list
    if isPath(new_list,10):
        print "threshold 10 match for ", new_list

Answer 1

（简短的回答：在这种情况下，弗洛伊德·沃沙尔比单纯地应用迪克斯特拉的方法更有效）

我对你的例子不是百分之百的清楚，但是看起来你必须以递增的顺序遍历数组，而且你不能回溯。你知道吗

例如。。。你知道吗

A = [1, 300]
B = [2, 11]
C = [12, 301] 

您转到A（1）->；B（2），但是没有到C的路径，因为您无法跳到B（11）->；C（12）。同样，你也不能跳过A（300）—>；C（301）。你知道吗

您可以创建一个大小为NM x NM的邻接矩阵，其中N是|数组|，M是每个数组|中的|元素。您可能希望使用稀疏数组实现，因为大多数值都是nil。你知道吗

对于每个递增对（ai，bj），（bi，cj），执行成对计算并存储连接（如果它是<；=阈值）。 运行时间为N*M^2，这比查找路径的成本（在最坏的情况下）要小，因此可能是可以接受的。对于threshold<；<；M和数组不包含重复的情况，可以通过先排序将其减少为N*MlgM。因为每个数组对比较最多需要阈值*M比较。你知道吗

要使用Dijkstra，你必须运行M*M次，对于数组a和n中的每一对元素运行一次，结果是O（M^2*ElgV）（E是边的数目，V是顶点的数目），在最坏的情况下E=（n-1）*M^2，V是n*M。或者n*M^4*lg（n*M）。所有最短路径对的Floyd-Warshall算法在V^3或（N*M）^3中运行，后者较小。你知道吗

Answer 2

我找到了一个更简单的解决方案（可能与JohnB的解决方案有关；我不确定）：

import numpy as np

def isPath(A, threshold):
    for i in range(len(A) - 1):
        print "Finding edges from layer", i, "to", i + 1, "..."
        diffs = np.array(A[i]).reshape((-1, 1)) - np.array(A[i + 1]).reshape((1, -1))
        reached = np.any(np.abs(diffs) <= threshold, axis = 0)
        A[i + 1] = [A[i + 1][j] for j in range(len(reached)) if reached[j]]
        print "Reachable nodes of next layer:", A[i + 1]
    return any(reached)

print isPath([[1, 3, 7], [10, 13], [13, 24]], 3)
print isPath([[1, 3, 7], [10, 13], [13, 24]], 10)

输出：

Finding edges from layer 0 to 1 ...
Reachable nodes of next layer: [10]
Finding edges from layer 1 to 2 ...
Reachable nodes of next layer: [13]
True

Finding edges from layer 0 to 1 ...
Reachable nodes of next layer: [10, 13]
Finding edges from layer 1 to 2 ...
Reachable nodes of next layer: [13]
True

它从一个层到另一个层，并检查在给定预定义的threshold的情况下仍然可以到达哪些节点。无法访问的节点将从数组中删除。当循环继续时，不再考虑这些节点。你知道吗

我想这是相当有效和容易实施。你知道吗

Answer 3

首先，我要建立一个无向图：数组中的每个数字都是一个节点，相邻行的节点连接在一起，当且仅当它们的距离小于阈值时。你知道吗

然后您可以使用标准算法来确定图的连接组件。您可能会找到许多关于这个常见问题的参考资料和代码示例。你知道吗

最后，您需要检查一个组件是否包含来自a的节点以及最后一行的节点，在本例中是c。你知道吗