数学研发论坛

 找回密码
 欢迎注册
楼主: 0→∞

[求助] 果树问题讨论:这两个问题等价么?

[复制链接]
发表于 2008-8-15 10:36:52 | 显示全部楼层
程序比较土呀。
是在vc2005下,压缩包为工程目录中所有的文件,其中源码如下:
  1. // 20tree-2.cpp : Defines the entry point for the console application.
  2. //

  3. #include "stdafx.h"
  4. #include <conio.h>
  5. #include <stdlib.h>
  6. #include <time.h>
  7. #define M 4845
  8. #define K 6
  9. int show(int sk[],int skn)
  10. {
  11.         int i,k,n;
  12.         for(i=0;i<skn;i++)
  13.         {
  14.                 n=sk[i];
  15.                 for(k=0;k<20;k++)
  16.                 {
  17.                         if(n%2==1)printf("%2d,",k+1);
  18.                         n/=2;
  19.                 }
  20.         printf("\n");
  21.         }
  22.         for(k=0;k<20;k++)
  23.         {
  24.                 for(i=0;i<skn;i++)
  25.                 {
  26.                         if(sk[i]%2==1)printf(" *");else printf(" .");
  27.                         sk[i]/=2;
  28.                 }
  29.                 printf("\n");
  30.         }
  31.         return 0;
  32. }
  33. int zzch(int z[],int zn,int sk,int zz[])
  34. {
  35.         int i,j,s,kk,k,r;
  36.         r=0;
  37.         kk=z[sk];
  38.         for(i=0;i<zn;i++)
  39.         {
  40.                 k=z[i]&kk;
  41.                 s=0;
  42.                 for(j=0;j<20;j++){s+=k%2;k/=2;}
  43.                 if(s<=1)
  44.                 {
  45.                         zz[r]=z[i];r++;
  46.                 }
  47.         }
  48.         return r;
  49. }
  50. int formatzz(int z[])
  51. {
  52.         int i,j,k,s,ss;
  53.         ss=0;
  54.         for(i=0;i<1048576l;i++)
  55.         {
  56.                 k=i;s=0;
  57.                 for(j=0;j<20;j++){s+=k%2;k/=2;}
  58.                 if(s==4){z[ss]=i;ss++;}
  59.         }
  60.         return 0;
  61. }
  62. int cztoz(int z[],int zz[],int n)
  63. {
  64.         int i;
  65.         for(i=0;i<n;i++)zz[i]=z[i];
  66.         return 0;
  67. }
  68. int _tmain(int argc, _TCHAR* argv[])
  69. {
  70.         int i,j,k,kt,n,nt,skn,zn,m,skm;
  71.         int z[M],zz[M],zzz[M];
  72.         int sk[50];
  73.         formatzz(zzz);
  74.         srand((unsigned)time(NULL));
  75.         skm=0;
  76.         for(m=0;m<100000;m++)
  77.         {
  78.                 cztoz(zzz,z,M);
  79.                 skn=0;
  80.                 zn=M;
  81.                 for(j=0;zn!=0&&j<50;j++)
  82.                 {
  83.                         n=-1;
  84.                         for(i=0;i<K;i++)
  85.                         {
  86.                                 kt=rand()%zn;
  87.                                 nt=zzch(z,zn,kt,zz);
  88.                                 if(nt>n){n=nt;k=kt;}
  89.                         }
  90.                         zzch(z,zn,k,zz);
  91.                         sk[skn]=z[k];skn++;
  92.                         zn=n;cztoz(zz,z,zn);
  93. //                        printf("k=%d,n=%d.\n",k,n);
  94.                 }
  95.                 if(skn>skm)
  96.                 {
  97.                         show(sk,skn);
  98.                         printf("skn(m=%d)=%d.\n",m,skn);
  99.                         skm=skn;
  100.                 }
  101.         }
  102.         printf("End\n");
  103.         _getch();
  104.         return 0;
  105. }
复制代码

20tree-2.part01.rar

390.63 KB, 下载次数: 1, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

20tree-2.part02.rar

284.9 KB, 下载次数: 1, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 10:54:01 | 显示全部楼层
有30台四核服务器就可以了
你们研究所够不够?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 10:56:06 | 显示全部楼层
函数formatzz产生所有直线模板(共4845个?)
看你后面使用rand函数,也就是每次随机选择一条直线,然后淘汰同它不相容的直线
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 11:04:11 | 显示全部楼层
原帖由 无心人 于 2008-8-15 10:54 发表
有30台四核服务器就可以了
你们研究所够不够?

这个不能瞎用
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 11:19:19 | 显示全部楼层


资源浪费阿
就和我们的50台高性能便宜机器一样
给学生做AutoCAD练习
一天多少计算资源浪费啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 11:20:15 | 显示全部楼层

补充71层

程序没有注释,这里简单解释一下。
我们知道从20个里面选4个,共有4845种选法,我们用formatzz列出它们。然后随机从其中取一个,划掉与这一个冲突的选法,然后循环。zzch就是用来将放在z中的选法,挑出与sk不冲突的选法放在zz中的函数。还有cztoz是用来将z中的结果倒来倒去的,show是显示最终结果的。后来对上面提到的随机选取做了改进,加入了贪婪的因素,贪婪因子K大家是可以调整的,就是先预选K次,然后执行其中冲突最少的选法。所以K越大就越贪婪。
可以看到程序中有许多地方都为了编程容易,没有优化,所以说土呢,呵呵。而且这个程序是不能搜索所有的组合的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 11:26:36 | 显示全部楼层
  随机算法效果就是好
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-15 13:06:41 | 显示全部楼层

回复 61# 没——问题 的帖子

恩,早就放弃了
早期是因为很容易就画出了一个20条直线的解,所以低估了这个问题的难度

不过,我准备闭门去学c语言了,争取开学前能看懂你们的程序
我比你们都年轻,最有希望的还是我
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 14:56:50 | 显示全部楼层
恩,0→∞努力吧

感谢mathe的排版
我确实没有养成好的习惯,不过这次这么夸张是有原因的:
早期为了练习c语言给自己订了一个原则:低于100行的代码就不留备份
这个代码写完后是150多行(mathe的排版是182行),去掉所有调试性的输出和注释剩120行,想尝试一下到底能缩到多少行,最终还是108行。代码得以保留。

那个2147483647纯属恶搞,只是想试试编译器(我用的是c-free3.5,应该是gcc/g++编译器的)到底允许多大(因为书上没说过)。我想无心人是对的,编译通过了也不可能分配那么多。事实上那个程序也不需要那么多空间:
即使搜索了20个点的所有情况(搜索完所有情况后有一个退出语句,这对pc机用户是没意义的 ),设最多的时候搜到过30行的情况(不现实),即最大深度为30,设兄弟结点数最大为1000(达不到),那么最多只会存储30*1000条线的数据。所以该做30000就可以了,高兴可以写65535

最终在这个代码中还有两个未完成的工作:
1、同mathe的node_edge_set所实现的功能
2、读取上次的结果继续搜的功能(现在每次运行都会从头搜)
这个(2)虽说简单,但我那个代码写的易读性太差了,很多变量都为了方便随手命名,而且到处乱用。所以mathe恐怕很难做这个修改(还不如自己重写),而我自己有没时间了囧
另外,还可以通过一些修改使得对某一[线的条数]的搜索更高效。例如代码中有一句注释说的0到4的问题,有兴趣可以试试改成0到4然后搜20点24条线,看看效率下降多少。

还是有点怀疑现有的数学软件能不能用来解这个方程组囧(虽然没用过wxMaxima,但应该也差不多)

zgg说的“划掉冲突”的方法,我最初时也想过,但没实施。两个程序的初衷不同。

ps:高考这东西太烦了,我会很少来,希望坛主别因为我长时间不登陆而删除了我的账号。期待着诸位的进展。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 16:08:58 | 显示全部楼层
原帖由 没——问题 于 2008-8-15 14:56 发表
ps:高考这东西太烦了,我会很少来,希望坛主别因为我长时间不登陆而删除了我的账号。


昨天与 没——问题 短消息交流时,对方曾说:
非常喜欢这个论坛,但迫于高中生活没办法常来"泡"


我回复如下:
是高中老师还是学生?水平蛮高的嘛!

这是个技术性并带学术性的论坛,欢迎大家常来,
但大家各自都有自己的工作和学习,
只要碰到问题需要解决或分享时,记得来这里就够了。


所以,不会删除账号的。

如果长时间未登陆,而忘了登陆密码时,可以通过“访客留言”给我,
系统会随机生成新密码发到注册信箱中去。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-9-18 17:00 , Processed in 0.087207 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表