- 论坛徽章:
- 0
|
回复 #15 marco_hxj 的帖子
原帖由 marco_hxj 于 2009-1-8 21:30 发表
蚂蚁算法?
分析了下题目,我的直觉和15楼一样, 启发式搜索? 但是, 蚁群也好,遗传也好,模拟煺火也好, 归根在于产生一个能约束在题设中的收敛序列. 但是, 就题目本身而言: N个文件, 每个文件Si个数据项. 如果遍历的话, 算法复杂度是 O( 求和Si(i 属于 1,...,N));
问题本身就是线性的. 而这个时候启发式搜索反而在使问题变复杂. 可以做如下假设:
对于任意文件看成一个部落. 我可以这么理解问题, 为了简化计算(x和y的Euler距离), 对于文件中的记录, 每两两组对,如果可以只计算x和配对的组中一个组员euler距离的话, 计算规模减少1/2. 但是为了达到这个目的,可以让这 S/2个组对进行遗传演化, 让所有组对成员之间euler距离之和最小... 而这个演化过程将远远超出减少的1/2规模. 也就是说问题反而变复杂了. 启发式搜索是为了求取一个NPC问题的局部最优解而有效...
因此,从算法本身上来看. 遍历似乎已经是最优的解决办法了,尚且不能满足需求的话, 或者真的只能从架构上想办法了, 比如试试 map-reduce ?
[ 本帖最后由 mwishes 于 2009-1-9 00:23 编辑 ] |
|