Python:判断跨n个数组的路径中的每一步是否都低于阈值

Question

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

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

和

threshold = 3

在这种情况下，您需要确定 a 和 b 的任何元素之间的距离是否为 3 或更小，以及 a 和 b 中实际上距离为 3 或更小的所有元素对在它们之间，您可能想要确定来自 a 的给定成员或来自 b 的给定成员与 c 的任何成员的距离是否为 3 或更小。 (在上面的例子中，每一步的距离低于阈值条件的唯一路径是 7-->10-->13。)

当数组的数量为三个时，我是这样处理这个问题的:

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

我找到了一个更简单的解决方案(可能与 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 的情况下仍然可以到达哪些节点。无法访问的节点从数组中删除。当循环继续时，不再考虑这些节点。

我猜它非常高效且易于实现。