我有两个不等长度的数组：
A = np.array([7,6,5,4,3,2,1])
B = np.array([37.97, 34.45, 32.41, 32.17, 35.48, 35.91, 33.81, 32.23, 33.46,
35.35, 33.03, 37.36, 32.18, 29.29, 30.23, 30.94, 34.26, 31.74,
29.24, 25.93, 29.26, 33.64, 33.28])
我需要从B中选择7个数字，这样与A的点积最小，或者min(7x1 + 6x2 + 5x3 +...+2x6 + x7)。两个数组的顺序都不能更改，例如，如果x1 = 32.41 (index 2)、x2不能是以前的索引。
事实上，A和B的长度比例子中的要大，所以我正在寻找一些有效的算法，而不是残酷的力量。有什么想法吗？
编辑：不改变顺序，我的意思是，如果我选择索引2处的元素，下一个元素可能是索引5或10，但不是索引0或1处。它们不需要像指数2,3,4,5那样连续
更新答案：所以这是我迄今为止基于@templatepedef和@Damien所做的回答：
def min_dot_product(A,B,m,n):
P = np.zeros((n,m))
A_ = np.zeros((n,m))
B_ = np.zeros((n,m))
#P[0,0] = 0
P[1,1] = A[1]*B[1]
S[1,1] = 1
for k in range(2,m):
P[1,k] = np.inf
for i in range(2,n):
P[i,0] = 0
for k in range(1,m):
P[i,k] = min (P[i-1,k], P[i-1,k-1] + B[i] * A[k])
if (P[i-1,k] > P[i-1,k-1] + B[i] * A[k]):
A_[i,k] = A[k]
B_[i,k] = B[i]
S[i,k] = 1
return P,A_,B_,S
A = np.array([0,7,6,5,4,3,2,1]) # -> Insert 1 dummy value at the first position
B = np.array([0,37.97, 34.45, 32.41, 32.17, 35.48, 35.91, 33.81, 32.23, 33.46,
35.35, 33.03, 37.36, 32.18, 29.29, 30.23, 30.94, 34.26, 31.74,
29.24, 25.93, 29.26, 33.64, 33.28]) # -> Insert 1 dummy value at the first position
m = len(A)
n = len(B)
mat,A_,B_,S = min_dot_product(A,B,m,n)
Out:
mat
array([[ 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[ 0. , 241.15, inf, inf, inf, inf, inf, inf],
[ 0. , 226.87, 435.61, inf, inf, inf, inf, inf],
[ 0. , 225.19, 419.89, 596.46, inf, inf, inf, inf],
[ 0. , 225.19, 419.89, 596.46, 738.38, inf, inf, inf],
[ 0. , 225.19, 419.89, 596.46, 738.38, 846.11, inf, inf],
[ 0. , 225.19, 419.89, 588.94, 731.7 , 839.81, 913.73, inf],
[ 0. , 225.19, 418.57, 581.04, 717.86, 828.39, 904.27, 945.96],
[ 0. , 225.19, 418.57, 581.04, 714.88, 818.24, 895.31, 937.73],
[ 0. , 225.19, 418.57, 581.04, 714.88, 818.24, 888.94, 930.66],
[ 0. , 225.19, 418.57, 581.04, 713.16, 813.97, 884.3 , 921.97],
[ 0. , 225.19, 418.57, 581.04, 713.16, 813.97, 884.3 , 921.66],
[ 0. , 225.19, 418.27, 579.47, 709.76, 809.7 , 878.33, 916.48],
[ 0. , 205.03, 400.93, 564.72, 696.63, 797.63, 868.28, 907.62],
[ 0. , 205.03, 386.41, 552.08, 685.64, 787.32, 858.09, 898.51],
[ 0. , 205.03, 386.41, 541.11, 675.84, 778.46, 849.2 , 889.03],
[ 0. , 205.03, 386.41, 541.11, 675.84, 778.46, 846.98, 883.46],
[ 0. , 205.03, 386.41, 541.11, 668.07, 771.06, 841.94, 878.72],
[ 0. , 204.68, 380.47, 532.61, 658.07, 755.79, 829.54, 871.18],
[ 0. , 181.51, 360.26, 510.12, 636.33, 735.86, 807.65, 855.47],
[ 0. , 181.51, 357.07, 506.56, 627.16, 724.11, 794.38, 836.91],
[ 0. , 181.51, 357.07, 506.56, 627.16, 724.11, 791.39, 828.02],
[ 0. , 181.51, 357.07, 506.56, 627.16, 724.11, 790.67, 824.67]])
A_
array([[0., 0., 0., 0., 0., 0., 0., 0.],
[0., 0., 0., 0., 0., 0., 0., 0.],
[0., 7., 6., 0., 0., 0., 0., 0.],
[0., 7., 6., 5., 0., 0., 0., 0.],
[0., 0., 0., 0., 4., 0., 0., 0.],
[0., 0., 0., 0., 0., 3., 0., 0.],
[0., 0., 0., 5., 4., 3., 2., 0.],
[0., 0., 6., 5., 4., 3., 2., 1.],
[0., 0., 0., 0., 4., 3., 2., 1.],
[0., 0., 0., 0., 0., 0., 2., 1.],
[0., 0., 0., 0., 4., 3., 2., 1.],
[0., 0., 0., 0., 0., 0., 0., 1.],
[0., 0., 6., 5., 4., 3., 2., 1.],
[0., 7., 6., 5., 4., 3., 2., 1.],
[0., 0., 6., 5., 4., 3., 2., 1.],
[0., 0., 0., 5., 4., 3., 2., 1.],
[0., 0., 0., 0., 0., 0., 2., 1.],
[0., 0., 0., 0., 4., 3., 2., 1.],
[0., 7., 6., 5., 4., 3., 2., 1.],
[0., 7., 6., 5., 4., 3., 2., 1.],
[0., 0., 6., 5., 4., 3., 2., 1.],
[0., 0., 0., 0., 0., 0., 2., 1.],
[0., 0., 0., 0., 0., 0., 2., 1.]])
B_
array([[ 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[ 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[ 0. , 32.41, 32.41, 0. , 0. , 0. , 0. , 0. ],
[ 0. , 32.17, 32.17, 32.17, 0. , 0. , 0. , 0. ],
[ 0. , 0. , 0. , 0. , 35.48, 0. , 0. , 0. ],
[ 0. , 0. , 0. , 0. , 0. , 35.91, 0. , 0. ],
[ 0. , 0. , 0. , 33.81, 33.81, 33.81, 33.81, 0. ],
[ 0. , 0. , 32.23, 32.23, 32.23, 32.23, 32.23, 32.23],
[ 0. , 0. , 0. , 0. , 33.46, 33.46, 33.46, 33.46],
[ 0. , 0. , 0. , 0. , 0. , 0. , 35.35, 35.35],
[ 0. , 0. , 0. , 0. , 33.03, 33.03, 33.03, 33.03],
[ 0. , 0. , 0. , 0. , 0. , 0. , 0. , 37.36],
[ 0. , 0. , 32.18, 32.18, 32.18, 32.18, 32.18, 32.18],
[ 0. , 29.29, 29.29, 29.29, 29.29, 29.29, 29.29, 29.29], x7
[ 0. , 0. , 30.23, 30.23, 30.23, 30.23, 30.23, 30.23], x6
[ 0. , 0. , 0. , 30.94, 30.94, 30.94, 30.94, 30.94],
[ 0. , 0. , 0. , 0. , 0. , 0. , 34.26, 34.26],
[ 0. , 0. , 0. , 0. , 31.74, 31.74, 31.74, 31.74],
[ 0. , 29.24, 29.24, 29.24, 29.24, 29.24, 29.24, 29.24], x5
[ 0. , 25.93, 25.93, 25.93, 25.93, 25.93, 25.93, 25.93], x4
[ 0. , 0. , 29.26, 29.26, 29.26, 29.26, 29.26, 29.26], x3
[ 0. , 0. , 0. , 0. , 0. , 0. , 33.64, 33.64], x2
[ 0. , 0. , 0. , 0. , 0. , 0. , 33.28, 33.28]]) x1
因此，最小值=p[n-1][m-1]=824.67=[7,6,5,4,3,2.1]*[33.28,3.64,29.26,25.93,29.24,30.23,29.29]
反转A_和B_:
def reverse(S,A_,B_):
n,m = S.shape
state = m-1
pos = []
if state >= 0:
for i in range(n-1,0,-1):
if (S[i][state] == 1):
state = state - 1
pos.append([i,state+1])
new_B = np.zeros(B_.shape)
new_A = np.zeros(A_.shape)
for p in pos:
new_B[p[0],p[1]] = B_[p[0],p[1]]
new_A[p[0],p[1]] = A_[p[0],p[1]]
return new_B,new_A
您在这里解决的问题有以下形式：
给定长度为m和n的两个序列A和B，以及一个数字k，找到长度为m的B的子序列，该子序列与A
在您最初的问题中，我们有m=7，但更一般地说，我认为7可以被任何数字取代。
这个问题有一个很好的动态编程解决方案。它背后的直觉如下。假设您从数组B中选择某个数字作为m元素向量的第一个元素。然后你的任务是确定剩下的m-1个元素是什么。如果你仔细想想，你会想挑选它们，这样这些m-1个元件与A的最后m-1个单元的点积就尽可能小。因此，问题变成了"你如何决定第一个项目应该是什么"one_answers"你如何选择后续项目？">
一种方法是使用递归搜索。这个想法是这样的：
- 如果B的长度等于A的长度，则您别无选择，只能按顺序拾取B的每个元素
- 否则，你有选择。一种选择是排除B的第一个元素。如果你这样做，你必须从B的剩余元素中挑选m个元素，这样你就可以得到A的最小点积。另一种选择则是挑选B的第一元素，这意味着你想从B的其余元素中挑选m-1个元素，目的是最小化A的m-1个尾部元素的点积。因此，评估这两个选项，然后选择更好的选项
这种方法会起作用，但正如所写的那样，它太慢了，不实用。幸运的是，它恰好很好地转换为动态编程解决方案。请注意，每个递归调用都可以被构造为解决以下形式的问题：
给定A中的索引i和B中的索引j，从位置j开始的B的子序列和从位置i开始的A的子向量的最小点积是多少？
这里只有O(mn)个可能的值，i和j可以接受，所以我们可以把这个问题当作填写一个这样大小的表来处理。具体来说，让T[i，j]作为我们的表。我们将按如下方式填写：
- T[i，j]=0如果i=m。也就是说，如果我们不允许使用A的任何元素，那么点积将是零的空和
- T[i，j]＝无穷大，如果n-j<m-i。也就是说，如果我们在B中剩下的元素比在A中剩下的少，那么我们甚至不能形成点积，所以我们只会假装答案是"大到你永远不会选择的东西。">
- T[i，j]＝min(T[i、j+1]，A[i]*B[j]+T[i+1，j+1])。也就是说，我们有两个选择：不要在向量中包含B的第j个元素，在这种情况下，我们必须在从位置j+1开始的B的子阵列中找到要拾取的元素；或者包括B的第j个元素，该元素将乘以点积中A的第i个元素，然后最小化剩余的元素
填充每个表项需要时间O(1)，因此我们可以在时间O(mn)中填充表。从那里，我们可以使用标准的DP表遍历算法来重建要包含的项目的精确集合。(实际上，我们可以通过注意到，由于我们需要长度为m的B的子序列，我们不需要填充整个表，因为元素的m2将是无穷大，我们可以跳过填充它们。这给出了O(m(n-m+1))的运行时间。)。
问题在@templateypedf:的答案中被重写
给定长度为m和n的两个序列A和B，求长度为m的B与A的点积最小的子序列
这里的方法是考虑一种动态编程算法，使用前向-后向过程来寻找最可能的隐藏状态序列。
这里，位置i处的状态对应于可能在该位置使用的A的元素的数目，其中i对应于B阵列中的索引。然后，可能性的总数可以用图来表示，最佳解决方案对应于该图中的路径。
这种方法主要使用两个阵列：
P[i][k]：考虑A的第一个i值的最佳(最小)当前点积值，假设使用了B阵列的k值
S[i][k]为每个状态k存储在步骤i中作出的决定k对应于底层网格的状态。
正向迭代：路径度量的计算
初始化：
P[1][0] = 0 -> case B[1] is not used
P[1][1] = A[1]*B[1] -> case B[1] is used
P[1][k] = infinite for k = 2..m
S[1][0] = 0
S[1][1] = 1
P[i][k]的递推计算
Do i = 2 to n
P[i][0] = 0
S[i][0] = 0
Do k = 1 to m
P[i][k] = min (P[i-][k], P[i-1][k-1] + B[i] * A[k])
S[i][k] = 0 in the first case -> B[i] is not used
S[i][k] = 1 in the second case -> B[i] is used
请注意，在内部循环中，可以将最大k值设置为min(i, m)，而不是m，以节省一些无用的计算。
反向迭代：读取解决方案
Minimum dot product = P[n][m]
相应的最佳A值是通过从位置(n, m)开始以相反的顺序遍历网格，并注意到我们有S[i][state] = 1的i位置而获得的。图中的最优路径对应于state的连续值。
state = m;
Do i = n to 1
if (S[i][state) == 1)
state = state - 1
B[i] (or index i) is added to the solution set S[]
else
state unchanged
在该过程结束时，数组S[]以相反的顺序包含B[i]的最佳序列。
全局时间和空间复杂度为O(nm)。
这种动态方法类似于@templatepedef的回复中发布的方法。不同之处在于，它是通过显式引入隐藏状态而获得的，而在另一种方法中是隐式的。
另一个区别是，我们得到的是循环解决方案，而不是递归的解决方案。
好了。编辑：对不起，刚才看到你想要一个算法。如果它很重要的话，运行它并不需要很长时间。对于长度为1000和1000000的数组，它需要1.57秒。它具有线性复杂性，我不明白为什么要使用算法。
import numpy as np
A = np.array([7,6,5,4,3,2,1])
B = np.array([37.97, 34.45, 32.41, 32.17, 35.48, 35.91, 33.81, 32.23, 33.46,
35.35, 33.03, 37.36, 32.18, 29.29, 30.23, 30.94, 34.26, 31.74,
29.24, 25.93, 29.26, 33.64, 33.28])
def return_smallest(short, long):
f = list()
len_small = short.shape[0]
len_long = long.shape[0]
for x in [long[i:i+len_small] for i in range(0, len_long-len_small)]:
f.append(np.dot(short, x))
i = np.argmin(f)
return long[i:i+len_small]
return_smallest(A, B)
Out[1]: array([29.29, 30.23, 30.94, 34.26, 31.74, 29.24, 25.93])