algorithm - 优化涉及多嵌套循环的任务的计算成本

Question

我只是编程的初学者，很抱歉因为一个(可能)基本的问题打扰了您。

我想执行以下任务:

(对于给您带来的不便，我深表歉意；我不知道如何在 Stack Overflow 中输入 TeX-y 公式)。我主要考虑在 MATLAB 或 Scilab 上实现，但语言并不重要。

我认为执行此操作的最天真的方法是形成一个 n 嵌套的 for 循环，即(例如在 MATLAB 上显示 n=2 的情况)，

n=2;
x=[x1,x2];
for u=0:1
    y(1)=u;
    if x(1)>0 then
        y(1)=1;
    end
    for v=0:1
        y(2)=v;
        if x(2)>0 then
            y(2)=1;
        end
        z=Function(y);
    end
end

但是，这种实现对于大n来说过于费力，更重要的是，它会导致函数的2^n-2^k次大量求值，其中k是x中负元素的个数。此外，天真地形成一个 k 嵌套的 for 循环，知道 x 中的哪个元素是负数，例如

n=2;
x=[-1,2];
y=[1,1];
for u=0:1
    y(1)=u;
    z=Function(y);
end

好像不是个好办法；如果我们想对不同的 x 执行任务，我们必须重写代码。

如果您提供实现代码的想法，我将不胜感激，这样 (a) 仅对函数求值 2^k 次(可能的最小求值次数)并且 (b) 我们甚至不必重写代码如果我们改变 x。

Answer 1

您可以使用递归轻松地在 y in Ax 上评估 Function

function eval(Function, x, y, i, n) {
    if(i == n) {
        // break condition, evaluate Function
        Function(y);
    } else {
        // always evaluate y(i) == 1
        y(i) = 1;
        eval(Function, x, y, i + 1, n);
        // eval y(i) == 0 only if x(i) <= 0
        if(x(i) <= 0) {
            y(i) = 0;
            eval(Function, x, y, i + 1, n);
        }
    }
}

将其转化为高效的 Matlab 代码是另一个问题。

如您所述，评估次数为 2^k。让我们对 x 进行排序，以便只有最后的 k 元素是非正数。使用 x 排序的反向排列来评估 Function 索引 y:Function(y(perm))。更好的是，同样的方法允许我们直接使用 dec2bin 构建 Ax:

// every column of the resulting matrix is a member of Ax: y_i = Ax(:,i)
function Ax = getAx(x)
    n = length(x);
    // find the k indices of non-positives in x
    is = find(x <= 0);
    k = length(is);
    // construct Y (last k rows are all possible combinations of [0 1])
    Y = [ones(n - k, 2 ^ k); (dec2bin(0:2^k-1)' - '0')];
    // re-order the rows in Y to get Ax according to the permutation is (inverse is)
    perm([setdiff(1:n, is) is]) = 1:n;
    Ax = Y(perm, :);
end

现在重写 Function 以接受矩阵或迭代 Ax = getAx(x); 中的列以评估所有 Function(y).