python - 在不改变顺序的情况下找到最小的乘积和

Question

我有两个不等长的数组:

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(索引 2)，则 x2 不能是之前的索引。

A 和 B 的长度实际上比示例中的要大，所以我正在寻找一些有效的算法而不是暴力。有什么想法吗？

编辑:通过不更改顺序，我的意思是如果我选择索引 2 处的元素，下一个元素可能是索引 5 或 10，但不能是索引 0 或 1。它们不需要像索引 2,3 那样连续,4,5....

更新答案:这就是我迄今为止根据 @templatetypedef 和 @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

所以 min = P[n-1][m-1] = 824.67 = [7,6,5,4,3,2,1]*[33.28,33.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

Answer 1

您在这里解决的问题具有以下形式:

Given two sequences A and B of lengths m and n, along with a number k, find the subsequence of B of length m that has the lowest dot product with A.

在您原来的问题中，我们有 m = 7，但更一般地说，我认为 7 可以替换为任何数字。

这个问题有一个很好的动态规划解决方案。其背后的直觉如下。假设您从数组 B 中选择一些数字作为 m 元素向量的第一个元素。然后，您的任务是确定剩余的 m-1 个元素是什么。如果您考虑一下，您会希望选择它们，以便这些 m-1 元素与 A 的最后 m-1 元素的点积尽可能小。那么，问题就变成了“你如何决定第一个项目应该是什么”和“你如何选择后续项目？”

实现此目的的一种方法是使用递归搜索。这个想法是这样的:

• 如果 B 的长度等于 A 的长度，则您别无选择，只能按顺序选取 B 的每个元素。
• 否则，您还有选择。一个选项是排除 B 的第一个元素。如果这样做，则必须从 B 的剩余元素中选取 m 个元素，以便获得与 A 的最小点积。另一个选项是选取 B 的第一个元素B，这意味着您希望从 B 的其余部分中选取 m-1 个元素，目的是最小化与 A 的 m-1 尾部元素的点积。因此，评估这两个选项，然后选择更好的一个。<

这种方法可行，但正如所写的那样，它太慢而无法实用。幸运的是，它恰好可以很好地转换为动态编程解决方案。请注意，每个递归调用都可以被构造为解决以下形式的问题:

Given an index i into A and an index j into B, what’s the smallest dot product you can form of a subsequence of B starting at position j and the subvector of A starting at position i?

i 和 j 在这里只能取 O(mn) 个可能的值，因此我们可以将这个问题视为填充该大小的表。具体来说，让 T[i, j] 作为我们的表。我们将填写如下:

• 如果 i = m，则 T[i, j] = 0。也就是说，如果我们不允许使用 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 table-walking 算法来重建要包含的确切项目集。 (实际上，我们可以通过注意到，由于我们需要长度为 m 的 B 子序列，所以我们不需要填充整个表，因为元素的 m² 将是无穷大，因此我们实际上可以加快速度，并且我们可以跳过填写它们。这给出了 O(m(n - m + 1))) 的运行时间。