回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>给定n个整数数组,是否有一个好的算法来确定是否有一条路径穿过这些数组,使得沿着该路径的每个“步骤”的最小(欧几里德)距离低于某个阈值?也就是说,穿过所有数组的路径将只包括来自每个数组的一个成员,并且该路径的每个步骤的距离将由在给定步骤期间被比较的两个数组的值之间的绝对距离确定。例如,假设您有以下数组:</p>
<pre><code>a = [1,3,7]
b = [10,13]
c = [13,24]
</code></pre>
<p>以及</p>
<pre><code>threshold = 3
</code></pre>
<p>在这种情况下,您需要确定a和b中的任何元素之间的距离是否为3或更小,对于a和b中的所有元素对,实际上它们之间的距离为3或更小,您需要确定a中的给定成员或b中的给定成员之间的距离是否为3或更小来自c的任何成员。(在上面的示例中,每个步骤的距离低于阈值条件的整数的唯一路径是7-->;10-->;13。)</p>
<p>当数组的数目为3时,我是如何处理这样一个问题的:</p>
<pre><code>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"
</code></pre>
<p>但是,如果您事先不知道有多少个数组,那么最有效的方法是什么来计算所有n个数组之间是否有一条路径,从而使路径中每个“步”的距离都低于所需的阈值?Dijkstra算法是将这个问题推广到n个数组的最佳方法吗?你知道吗</p>
<h2>编辑:</h2>
<p>@Falko的方法对我有用:</p>
<pre><code>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
</code></pre>