值排列

Question

问题：有 2 个并行的正值数组 A 和 B，大小为 n。

如何找到以下目标函数的最小值：

F(A, B) = Ak + Bk * F(A', B')

其中 A'、B' 表示数组 A 和 B 及其 k ：第一个元素被删除。

我正在考虑动态规划方法，但没有成功。

如何应用于此类问题，我们需要在排列上评估给定函数？

Answer 1

最佳解决方案是计算(B_k - 1)/A_k，并在递归的最外侧位置执行结果较小（包括负数较多）的结果。

这是局部最优的，因为您无法交换一对相邻的选择并进行改进，因此也是全局最优的，因为该算法除了 (B_k-1)/A_k 的相等值之外还给出了唯一的解决方案，其中没有什么区别。任何其他不具有此属性的解决方案都不是最佳的。

如果我们将 A_1+B_1*(A_2+B_2*F) 与 A_2+B_2*(A_1+B_1*F) 进行比较，则前者会更小（或相等）当且仅当

A_1 + B_1*(A_2 + B_2*F) <= A_2 + B_2*(A_1 + B_1*F)
A_1 + B_1*A_2 + B_1*B_2*F <= A_2 + B_2*A_1 + B_2*B_1*F
B_1*A_2 - A_2 <= B_2*A_1 - A_1
(B_1 - 1)/A_1 <= (B_2 - 1)/A_2

注意到 A_k > 0 。

空 F(,) 的值并不重要，因为它出现在最后乘以所有 B_k。

Answer 2

我想出了一个启发式方法。可惜这不是最优的（感谢 yi_H！） =(

起初，我认为从增加 A_i 的值开始。但是，反例仍然存在（A={1000, 900} 和 B={0.1, 0.5}）所以我想出了这个：

对于 [1..n] 中 i 的每个值，计算V_i = A_i + B_i*min(A_j) for j!=i

选择 i，使 V_i 是所有 中最小的V 值从 A 和 B 中删除 A_i 和 B_i。这是前两项，

与 A' 和 < code>B' 直到结束（直到两者都为空）。

如果您记住 V_i 并更新它们，则该算法为 O(n^2)，否​​则对于简单的实现，该算法为 O(n^3)

编辑：恭喜 yi_H 。寻找反例来说明为什么这不是最佳的！

Answer 3

不是解决方案，但可能是一种启发。看看F(A, B) = Ak + Bk * F(A', B')，很明显F(A', B')正在发生大于 Ak 或 Bk。因此，由于相乘，我们应该选择尽可能小的 Bk，这将为我们提供一个 k 值，因此可能是最小的 F(A , B) 当我们计算出来时。如果有多个最小的 Bk，我们可以计算它们并选择最小的。

然后，我们可以启动一个强力算法，遍历所有可能的结果，但我们已经有一个可能的最小结果，因此，如果当前的试验将给我们带来比我们已有的结果更大的结果，我们可以提前终止。

Answer 4

它不是有效的 [ O(2^n * n) ] 但应该可以工作并且比评论中的 O(n! *n) 更好

int n;
double[n] a,b; //global
double[1<<n] pres; //0's on startup. res is never 0

//Try to calculate this function  if only elements in mask are used.
double res(int mask){
    if(pres[mask]!=0) // do not recalc. it's lazy DP
        return pres[mask];
    if(!mask)
        return pres[mask]=1;  //F(empty) you should replace for your default value
    double pres[mask]=INF; //INF > any result
    for(int i=0;i<n;++i){
        if(mask & (1<<i)){
            //i-th elemnent not used not used 
            pres[mask]=min(min_value,a[k]+b[k]*res(mask-(1<<i));
            //try to delete it recursively and check minimum for all elements
        }
    }
    return pres[mask];
}

double ans=res((1<<n)-1); //get res for all array

你可以在没有递归的情况下对其进行编码：

res[0]=1; //F(empty)
for(int mask=1;mask<1<<n;++mask){
    res[mask]=INF;
    for(int i=0;(1<<i)<=mask;++i){
        if(mask & (1<<i)){
            pres[mask]=min(min_value,a[k]+b[k]*res[mask-(1<<i)];
        }
    }
}
//use res[(1<<n)-1]

PS：我使用所有元素都是正数，即 a< ;b&& c ac

Answer 5

我有一个循环，它尝试列表中两个元素的每个组合 (N^2) 并尝试交换它们。如果结果（我用 k=1 进行评估）变得更好，则从头开始。

似乎适用于 N<=10，也可能适用于较大的 N，但我无法真正测试，因为验证器是强力 O(N!) 算法：D 另外，我不知道它有多快对于大 Ns 收敛。

尝试过随机算法，该算法随机选择交换位置并在 X 次不成功的尝试后停止......它很少找到最佳解决方案。

更新：
在Python中运行：

N=40 N=50 N=60
2.8s 5.3s 8.4s  (starting point: not sorted)
1.7s 2.8s 4.4s  (sort on a first)
1.2s 2.2s 4.3s  (sort on b first)
0.8s 1.9s 2.5s  (using Fezvez's algorithm as a starting point)

所有测量都包含预排序（第四个Fezvez算法）的运行时间。如果有人认为他的解决方案接近最佳，请告诉我，我会测试它。

更新2：
我的算法在改进后重新开始搜索，这有点愚蠢。我不想重新运行所有测试，这里有一些新数据（仍然无法验证结果，你必须想出一个效果更好的算法。 .:)) 现在有了 Fezvez+swap 的改进：

N=100: 1.0s    N=150: 3.1s    N=200: 7.0s

一些改进统计数据（N=200，均匀分布：A: [1, 1000], B: [0.1,0.9]）

Fezvez     improvemenent
38.172841  36.764499
13.809364  13.805913
27.287438  26.389688
45.101368  40.364930
14.623132  14.599037
33.060609  31.298794

Answer 6

这个解决方案不是最优的，只是实用的。但恐怕这是一个难题。同时，以下内容应该可以为您提供良好的排列。

因为 b_k < 1，选择使 a_k 增加的排列作为排列是一个很好的起点。

您可以根据这个初始猜测尝试模拟退火。作为状态转换的随机换位应该是可以的。