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

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

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