2

我正在编写一个 MATLAB 程序,用于查找满足以下约束的频率 f_i 的所有可能值:

f1+f2+f3+f4+f5+f6=100 
f2+2*f3+3*f4+4*f5+5*f6=95

由于巨大的嵌套 for 循环,该程序需要大量时间,但我无法得到答案,那么解决这个问题的可能方法是什么?

此外,我真正的问题要大得多,我需要具有类似约束的 150 f_i 的所有可能频率

f1+f2+...+f150=10,000,000
f2+3*f3+...+17*f150=9,500,000

那么,是否有任何方法或技术来解决此类问题,如果是,那么如何解决?

4

3 回答 3

1

你不需要循环,你需要线性代数。您有 2 个线性方程和 6 个变量。这为您留下了 4 个自由度。

我假设您的变量是限制在某个范围内的整数,否则会有无限数量的解决方案。

将整数值赋给f1f2f3f4并求解其余方程。一种方法是生成某个范围内所有整数的 4D 网格,并求解线性系统。

[f1,f2,f3,f4] = ndgrid(1:10,1:10,1:10,1:10);
res = [1 1; 4 5] \ ([100-f1(:)-f2(:)-f3(:)-f4(:)  95-f2(:)-2*f3(:)-3*f4(:)]');
f5 = res(1,:);
f6 = res(2,:);

solutions = [f1(:) f2(:) f3(:) f4(:) f5(:) f6(:)]
于 2012-10-17T12:13:01.210 回答
1

您给出的示例问题有 6 个未知数,只有 2 个方程。在你真正的问题中,你说你可以有 150 个变量,但仍然只有 2 个方程。

这些问题严重不足,您可以分配无限数量的不同值来f1--f150满足这两个约束。列举所有可能的解决方案是没有意义的——你最好为每个频率生成一个数组,并在使用特定组合时检查约束。这要高效得多,因为开始时的限制很少。

现在,你说所有f_i都是非零正整数。这仍然没有帮助,因为1/0它也是一个整数。我假设还有一个额外的限制,那就是所有频率都不能大于某个预定义的最大值。

我将向您说明我的担忧。假设最大值为 100。那么有多少种不同的组合?对于 6 个不同的频率(如示例中所示),

num_fi = 100*100*100*100*100*100 = 100^6 = 10^12 = 1 trillion

组合。对于, f_i_i = 150

num_fi = 100*100*...150 times...*100 = 100^150 = 10 ^ 300

(这是 300 的 10 倍!)不同的组合。

假设你想存储它们。由于 1 到 100 之间的整数只占用 1 个字节,因此您必须存储

[number of combinations] * [number of f_i in the set] * [number of bytes]  
    = [num_fi] * i * 1byte 
    = (10^300 * 150) bytes
    = 1.5 * 10^290 TERABYTES. 

假设你使用 4TB 硬盘,每个硬盘高 1cm,你需要

3.75 * 10^289  

4TB 硬盘。这些硬盘驱动器堆叠在一起时,将形成一个可以到达的塔

(3.75*0.01*10^289)/384400000/2 = 4.87 * 10^278 

往返月球的次数,或

(3.75*0.01*10^289)/2.54e6/9.4605284e15/2 = 7.80 * 10^264

多次往返仙女座星系,或

(3.75*0.01*10^289)/13.2e9/9.4605284e15/2    
= 1.50 * 10^261 

多次到UDFj-39546284 并返回

既然是星期五,我将投入一些奖金:

硬盘驱动器将填满:

  • 1.59e+247 倍球体,以太阳为中心,半径为 39AU(至冥王星)
  • 3.75e+222 倍球体,以银河系中心的 SMB 为中心,半径 100,000 光年(整个银河系)
  • 1.39e+207倍球体,以地球为中心,半径139亿光年(可观测宇宙)

这只是最大值为 100。

所以我们在这里真的无能为力,除非你给我们更多关于你试图用f_i's完成什么的上下文。

于 2012-10-17T12:53:04.310 回答
0

你的问题是线性的。

因此,您可能做的是以矩阵形式编写问题,然后寻找矩阵内核 - matlab 计算所做的(至少在找到它的方向方面,参见例如http://www.mathworks.de/matlabcentral /newsreader/view_thread/45457)。

但是,在这里,我们假设频率是真实的(只要它具有物理意义)。否则问题就更难了。

于 2012-10-17T12:15:02.260 回答