请前辈们帮看看：这样一个问题适合用分布式计算吗？

winde

有一个数字，有100位，每一位的取值范围：0－9。即该数最大为（10^100－1，10的100次方减1）,也即100个9组成。

我想遍历在每个数（从0到10^100－1）情况下，处理一些简单事情。

关键是要遍历的次数较多，从而造成总运算量较大，能否用并行计算进行？如果能，能提高运算效率大概是多少？

对并行计算不了解，呵呵，新手一个。请各位赐教！谢谢！


（8＃补充说明问题）

[ 本帖最后由 winde 于 2007-6-13 10:29 编辑 ]

fwjmath2

估计可以，如果每个数可以独立处理的话。但是现在来讲这种计算是不现实的，因为可能性实在太多了。我个人认为你应该考虑的是如何改良算法。
或者你把问题贴出来我们看看？~~~

lch=gta

遍历每一个数
具体要干什么呢？

20080030成电

数字太大了，不知道什么时候才能算完。
多线程处理，在单机上看能不能提高速度。

LZ的问题也说的不清楚。

20080030成电

如果CPU每秒处理10^10个数字，那么10^100个数字需要10^80秒。
就算是分布式也不能。

20080030成电

写错了，应该是10^90秒

老冬腌菜

很多时候有些循环可以在很前面跳到下一个

比如

for a1 = 0 to 9 step 1
    ......
    for a2 = 0 to 9 step 1
        ......
        for a3 = 0 to 9 step 1
            ......
        next a3
    next a2
next a1

有的时候不需要遍历到 a100，而只需要遍历到 a2 就可以确定这个不行，这样可以提高一些速度……

winde

没想到有这么多高手关注，先谢谢大家！

我是在做一个神经网络之遗传算法，考虑到遗传算法可能最终不能给出最优问题解答，就考虑到遍历。呵呵，只是想尝试下。遍历这么大的数，按常规算法来说，以现有计算机计算能力可能就是痴人说梦。

不过，看到这里的“并行计算”，就想问大家，有没好的算法和其它解决思路。

其中网络的权值加偏移值共100位，每个权值、偏移值变化范围为：0－9（是我人为特意这样设定）。

[ 本帖最后由 winde 于 2007-6-13 10:25 编辑 ]

winde

原帖由 老冬腌菜 于 2007-6-12 22:03 发表
很多时候有些循环可以在很前面跳到下一个

比如

for a1 = 0 to 9 step 1
    ......
    for a2 = 0 to 9 step 1
        ......
        for a3 = 0 to 9 step 1
            ......
        next a3
    next a2
...

这个思路我会考虑并试验下，谢谢！

behaviorist

FOR i = 1 TO 10
    FOR j = 1 TO i
        FOR k = 1 TO j
        NEXT k
    NEXT j
NEXT i

一共经历了多少次 k 循环...

老冬腌菜

1+(1+2)+.......+(1+2+........+10)
=(1^2+2^2+.......+10^2+1+2+3+......+10)/2
=(10*11*21/6+10*11/2)/2
=(385+55)/2
=220

fwjmath2

我觉得这个数字还是太大了。不过如果说是神经网络的话，我建议用模拟退火法试试，因为这个问题的解质量的变化应该是连续的。这个算法也不保证能出全局最优解，但可以多次运行求出很多局部最优解，可以作为一种补充，同时也便于实现并行计算。具体情况可以找些书看看。

fwjmath2

不好意思，借别人的手机不大会用重复发帖了。再补充一点，就是如果有什么可行的已知的约束条件的话也可以加到算法中。无论是什么算法，多一点信息都意味着少一点计算时间。

碧城仙

重复帖已删除，你们慢慢讨论，我细细看。

usafchn

原帖由 老冬腌菜 于 2007-6-12 22:03 发表
很多时候有些循环可以在很前面跳到下一个

比如

for a1 = 0 to 9 step 1
    ......
    for a2 = 0 to 9 step 1
        ......
        for a3 = 0 to 9 step 1
            ......
        next a3
    next a2
...

这种穷举搜索法也许是最糟糕的，是否可以考虑一下深搜和广搜