0

我试图用 28 个变量求解这个方程：

y = (a1 * x1) + (a2 * x2) + .... + (a28 * x28)

1) y 是已知的，a1、a2 一直到 a28 也是已知的。

2) x1, x2 ..... x28 是未知变量，它们在 [-4, 4] 范围内，增量为 0.1。

有人能解释一下我困惑的大脑，什么算法在这里使用最有效吗？

4

3 回答 3

2

这等效于整数线性规划，尽管由于只有一个具有 28 个简单约束（边界，而不是方程组）的方程，您可能会做得更好。一般来说，这将是 NP 难的（请参阅https://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns），但您可能可以使用几种实现（例如，请参阅如何选择整数线性编程求解器？）

于 2012-12-14T03:44:55.587 回答
1

您可以在 prolog 中对其进行编程（SICStus prolog 引擎，例如 Eclipse 上的 SPIDER IDE）。这个问题是状态空间搜索问题。并使用 clpfd 库（有限域上的约束逻辑编程）。然后你只做一个约束，X1 到 X28 将是域变量并给定约束 y #= a1*X1 + ... + a28*X28。优化状态空间搜索的方法也很少。

/edit：或者你可以尝试用任何命令式语言来做。还使用一些启发式方法 - 例如，选择一些执行点，您可以在其中检查当前结果（例如，您有一些 tmp.sum 并且您已经从 28 个值中计算了 15 个。如果 y 减去 temp sum 小于 MIN_VARIABLE_VALUE * i，其中 i 是索引，x_i 属于剩余变量，你可以放心地决定，你不会继续，bcs。你不能得到平等）。这个启发式首先出现在我的脑海中。在此使用也可以使用一些替换。但是应该对一些测试数据进行“研究”它的效率如何。

于 2012-12-14T07:29:28.957 回答
1

首先，将所有内容乘以 10，这样您就可以继续进行整数数学运算。同样在两边加上 sum(40*a_u) 会将 x_i 的范围更改为 [0,80]

其次，答案可能呈指数级，因此您的算法必须花费指数级时间。

鉴于有 80^28（大约 2^177）个可能的答案 - 这通常是不可能的。

现在如果 x_i 的范围是 [0,1]（而不是 [0,80]）并且我们添加一个等于 y 的额外项（并将 y 更改为 0），那么问题就变成了找到集合的子集加起来为零的整数。这是一个众所周知的 NP 完全问题，它似乎比你的更容易（尽管我没有明确的减少）。

可能有动态编程解决方案，但可能太慢了：

set<float> X;

X.insert(0)

for i = 1 to 28
    for f = -4.0 to 4.0 step 0.1
        for x in X
            X.insert(x + a_i * f)

for x in X
    if (x == y)
        return true;

return false;

您可以通过传回可行范围（[y + a_i*(-4.0), y + a_i*4.0]）并在这些范围之外修剪不可行的部分解决方案来做得更好。

于 2012-12-14T03:51:12.250 回答