数学研发论坛

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

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

  [复制链接]
发表于 2008-11-12 16:44:29 | 显示全部楼层
我前面的版本就是将数据拆分成数千个文件的,不过效果不好.所以现在改成少量几个大文件,然后用一个很大的hash值决定保存在文件的位置,不过结果效果同样不好.
没有想到移植到windows以后,速度又低了很多倍,看来这方面的确Windows不行.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-12 17:14:00 | 显示全部楼层
如果用小文件
比如,仅考虑前两组4字母组合
显然,每个文件的总可能解是能计算得到的
用个大文件,对每组双4字母组合与刘足够的空间
遇到需要保存的
建立个索引文件,保存每个组在大文件里的位置偏移
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-12 17:14:31 | 显示全部楼层


不过这个文件可能比较大了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-12 17:24:13 | 显示全部楼层
编了一个小程序,会随机产生一些解(只产生大于等于23的解),我的机器太慢了,而且最近编程总是犯错误,所以请大家测试一下。
直接运行就可以了,我这里一般1小时产生一个23的解。

tree.rar

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

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 09:28:53 | 显示全部楼层
原帖由 zgg___ 于 2008-11-12 17:24 发表
编了一个小程序,会随机产生一些解(只产生大于等于23的解),我的机器太慢了,而且最近编程总是犯错误,所以请大家测试一下。
直接运行就可以了,我这里一般1小时产生一个23的解。

是产生问题二的解吧?
问题在于边数比较多的时候,问题二的解是问题一的解的概率非常低.
以前面17颗树情况为例子,我曾用贪心法产生了数万个16行的问题二的解,结果没有一个是问题一的解,这也是为什么我前面会猜测17颗树时最多15行
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 11:13:24 | 显示全部楼层
是问题一的解。
我尝试了一种方法,用来判断某种[XXXX-XXXX-……-XXXX]的组合(下面简称[x])是不是能画出来,也就是[x]能不能满足问题一。这也就是我为什么想要一些测试数据。

求解的过程是:
[x]=空;
for(;;)
{
第一步:将[x]随机增加一组XXXX,使之依旧满足问题二;如果不能再增加了,就输出[x];
第二步:判断[x]是不是满足问题一;如果不满足就重做上一步;
}
就这样得到1组结果。我刚才将程序运行了大约1个小时,随机搜索了100000组解,从18到22的解分布为:272,14464,60830,23775,659,其它的解没有。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 11:32:52 | 显示全部楼层
我建议与其搜索20颗树情况,不如现在先搜索18颗19颗树的问题。
你判断是否能够满足问题一用什么方法?如果有比较高效的方法很重要,我觉得我现在的程序太慢了一些。
另外对于各种情况,通常平均多少个问题2的结果可以有对应的问题2的解呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 11:49:20 | 显示全部楼层
是否能简化问题二的解
把同构的去掉

另外,是否总有一些模式无解
如果有很多模式
能快速的淘汰一批解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 11:50:12 | 显示全部楼层
我把代码贴上来吧。编写的比较乱。上面发的可执行文件去掉了写盘的部分。
其中conf()和ssn()是用来判断的部分。
现在还是不敢确定算法判断是不是正确,但是如果和mathe程序的判断结果一致就比较对了。呵呵。
  1. // n-13.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. unsigned ddy[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};
  9. unsigned z_xs[1000],z_ans[1000],z_z[M],z_x;
  10. int z_xsn,z_ansn,z_zn;
  11. int show(unsigned d)
  12. {
  13.         unsigned i;
  14.         for(i=0;i<20;i++)if(d&ddy[i])printf("%c",'A'+i);
  15.         return 0;
  16. }
  17. int shows(unsigned *d,int dn)
  18. {
  19.         int i;
  20.         printf("[");
  21.         if(dn>0)
  22.         {
  23.                 for(i=0;i<dn-1;i++){show(d[i]);printf("-");}
  24.                 show(d[i]);
  25.         }
  26.         printf("]\n");
  27.         return 0;
  28. }
  29. int fshow(FILE *fp,unsigned d)
  30. {
  31.         unsigned i;
  32.         for(i=0;i<20;i++)if(d&ddy[i])fprintf(fp,"%c",'A'+i);
  33.         return 0;
  34. }
  35. int fshows(FILE *fp,unsigned *d,int dn)
  36. {
  37.         int i;
  38.         fprintf(fp,"[");
  39.         if(dn>0)
  40.         {
  41.                 for(i=0;i<dn-1;i++){fshow(fp,d[i]);fprintf(fp,"-");}
  42.                 fshow(fp,d[i]);
  43.         }
  44.         fprintf(fp,"]\n");
  45.         return 0;
  46. }
  47. int init()
  48. {
  49.         int i1,i2,i3,i4;
  50.         z_zn=0;
  51.         for(i1=0;i1<17;i1++)
  52.         for(i2=i1+1;i2<18;i2++)
  53.         for(i3=i2+1;i3<19;i3++)
  54.         for(i4=i3+1;i4<20;i4++)
  55.         {
  56.                 z_z[z_zn]=ddy[i1]|ddy[i2]|ddy[i3]|ddy[i4];
  57.                 z_zn++;
  58.         }
  59.         return 0;
  60. }
  61. int ssn(unsigned *qtx,int qtxn,unsigned *ans)
  62. {
  63.         unsigned lxz[1000],sxz1,sxz2,sxz3,sjx[3000],sjd1,sjd2,sjxl1[3000],sjxl2[3000],sjxl3[3000];
  64.         int i,i1,i2,i3,k1,k2,lxzn,sjxn,ansn;
  65.         unsigned z,zz,z1,z2,z3,sa1,sa2,sa3,sb1,sb2,sb3;
  66.         ansn=0;
  67.         for(z=1;z<=524288;z*=2)
  68.         {
  69.                 lxzn=0;for(i=0;i<qtxn;i++)if(z&qtx[i]){lxz[lxzn]=qtx[i]^z;lxzn++;}
  70.                 for(i1=0;i1<lxzn-2;i1++)
  71.                 for(i2=i1+1;i2<lxzn-1;i2++)
  72.                 for(i3=i2+1;i3<lxzn;i3++)
  73.                 {
  74.                         sxz1=lxz[i1];sxz2=lxz[i2];sxz3=lxz[i3];
  75.                         sjxn=0;
  76.                         for(z1=1;z1<=524288;z1*=2)
  77.                         {        if((z1&sxz1)==0)continue;
  78.                         for(z2=1;z2<=524288;z2*=2)
  79.                         {        if((z2&sxz2)==0)continue;
  80.                         for(z3=1;z3<=524288;z3*=2)
  81.                         {        if((z3&sxz3)==0)continue;
  82.                                 zz=z1|z2|z3;
  83.                                 for(i=0;i<qtxn;i++)if(zz==(zz&qtx[i]))break;if(i<qtxn)continue;
  84.                                 for(i=0;i<qtxn;i++)if(((z2&qtx[i])!=0)&&((z3&qtx[i])!=0)){sjxl1[sjxn]=qtx[i]&(~z2)&(~z3);break;}if(i==qtxn)continue;
  85.                                 for(i=0;i<qtxn;i++)if(((z1&qtx[i])!=0)&&((z3&qtx[i])!=0)){sjxl2[sjxn]=qtx[i]&(~z1)&(~z3);break;}if(i==qtxn)continue;
  86.                                 for(i=0;i<qtxn;i++)if(((z1&qtx[i])!=0)&&((z2&qtx[i])!=0)){sjxl3[sjxn]=qtx[i]&(~z1)&(~z2);break;}if(i==qtxn)continue;
  87.                                 sjx[sjxn]=zz;sjxn++;
  88.                         }}}
  89.                         for(k1=0;k1<sjxn-1;k1++)
  90.                         for(k2=k1+1;k2<sjxn;k2++)
  91.                         {
  92.                                 sjd1=sjx[k1];sjd2=sjx[k2];
  93.                                 if(sjd1&sjd2)continue;
  94.                                 sa1=sjxl1[k1];sa2=sjxl2[k1];sa3=sjxl3[k1];
  95.                                 sb1=sjxl1[k2];sb2=sjxl2[k2];sb3=sjxl3[k2];
  96.                                 if((sa1&sb1)!=0&&(sa2&sb2)!=0&&(sa3&sb3)!=0){zz=(sa1&sb1)|(sa2&sb2)|(sa3&sb3);
  97.                                         for(i=0;i<qtxn;i++)if(zz==(zz&qtx[i]))break;if(i==qtxn){ans[ansn]=zz;ansn++;}}
  98.                         }
  99.                 }
  100.         }
  101.         return ansn;
  102. }
  103. int ztoz(unsigned *z0,unsigned *z,int zn)
  104. {
  105.         int i;
  106.         for(i=0;i<zn;i++)z[i]=z0[i];
  107.         return zn;
  108. }
  109. int sdcd(unsigned *z,int zn)
  110. {
  111.         int i,j,rn;
  112.         if(zn<=1)return zn;
  113.         rn=1;
  114.         for(i=1;i<zn;i++)
  115.         {
  116.                 for(j=0;j<rn;j++)if(z[i]==z[j])break;
  117.                 if(j==rn){z[rn]=z[i];rn++;}
  118.         }
  119.         return rn;
  120. }
  121. int nu(unsigned z)
  122. {
  123.         int i,r;
  124.         r=0;
  125.         for(i=0;i<20;i++)if(ddy[i]&z)r++;
  126.         return r;
  127. }
  128. int doz()
  129. {
  130.         int i,j,zn;
  131.         unsigned x,z[M];
  132.         zn=0;
  133.         for(j=0;j<z_zn;j++)
  134.         {
  135.                 x=z_z[j];
  136.                 for(i=0;i<z_xsn;i++)if(nu(x&z_xs[i])>=2)break;
  137.                 if(i<z_xsn)continue;
  138.                 for(i=0;i<z_ansn;i++)if(nu(x&z_ans[i])==2)break;
  139.                 if(i<z_ansn)continue;
  140.                 z[zn]=x;zn++;
  141.         }
  142.         z_zn=ztoz(z,z_z,zn);
  143.         return 0;
  144. }
  145. int dozf()
  146. {
  147.         int i,j,zn;
  148.         unsigned x,z[M];
  149.         zn=0;
  150.         for(j=0;j<z_zn;j++)
  151.         {
  152.                 x=z_z[j];
  153.                 for(i=0;i<z_xsn;i++)if(nu(x&z_xs[i])>=2)break;
  154.                 if(i<z_xsn)continue;
  155.                 z[zn]=x;zn++;
  156.         }
  157.         z_zn=ztoz(z,z_z,zn);
  158.         return 0;
  159. }
  160. int doz1()
  161. {
  162.         int i,rn;
  163.         rn=0;
  164.         for(i=0;i<z_zn;i++)
  165.                 if(z_x!=z_z[i]){z_z[rn]=z_z[i];rn++;continue;}
  166.         z_zn=rn;
  167.         return rn;
  168. }
  169. int conf()
  170. {
  171.         unsigned room[1000],ans[1000],imp[1000];
  172.         int roomn,ansn,impn,i,j;

  173. Begin:
  174.         roomn=ztoz(z_xs,room,z_xsn);
  175.         roomn+=ztoz(z_ans,room+roomn,z_ansn);
  176. //        printf("the input of ssn is(roomn=%d):\n",roomn);
  177. //        shows(room,roomn);
  178.         ansn=ssn(room,roomn,ans);
  179.         if(ansn>0)
  180.         {
  181. //                printf("Add z_zans to ansn.\n");
  182.                 ansn+=ztoz(z_ans,ans+ansn,z_ansn);
  183. //                printf("\nThere is %d(ansn) ans, and they are:\n",ansn);
  184. //                shows(ans,ansn);
  185.                 ansn=sdcd(ans,ansn);
  186. //                printf("Get rid of the same ans, there is %d(ansn) ans lest, and they are:\n",ansn);shows(ans,ansn);
  187. //                printf("Cal imp of ans..\n");
  188.                 impn=0;
  189.                 for(i=0;i<ansn;i++)
  190.                 for(j=i+1;j<ansn;j++)
  191.                         if(nu(ans[i]&ans[j])==2){imp[impn]=ans[i]|ans[j];
  192. //                        printf("There is 2 ans to 1 imp: [");show(ans[i]);show(ans[j]);show(imp[impn]);printf("]]].\n");
  193.                         impn++;}
  194.                 if(impn>0)
  195.                 {
  196. //                        printf("There is %d imp. check imp if or not conf with z_xs?\n",impn);
  197.                         for(i=0;i<impn;i++)
  198.                         {
  199.                                 for(j=0;j<z_xsn;j++)
  200.                                         if(nu(imp[i]&z_xs[j])>=2){
  201. //                                                printf("Conf...with ");show(imp[i]);show(z_xs[j]);
  202.                                                 return -1;}
  203.                                 z_xs[z_xsn]=imp[i];z_xsn++;
  204.                         }
  205. //                        printf("No, there is no conf in imp. and new z_xsn is %d.\n",z_xsn);
  206. //                        printf("Get rid of ans in the imp, and put to z_ans.\n");
  207.                         z_ansn=0;
  208.                         for(i=0;i<ansn;i++)
  209.                         {
  210.                                 for(j=0;j<impn;j++)if(ans[i]==(ans[i]&imp[j]))break;
  211.                                 if(j!=impn){
  212. //                                        printf("GEtridof ans>>>");show(ans[i]);
  213.                                         continue;}
  214.                                 z_ans[z_ansn]=ans[i];z_ansn++;
  215.                         }
  216.                 }
  217.                 else
  218.                 {
  219. //                        printf("There is no imp.\n");
  220.                         z_ansn=ztoz(ans,z_ans,ansn);
  221.                 }
  222. //                printf("Check conf with z_ans and all z_xs...\n");
  223.                 for(i=0;i<z_ansn;i++)
  224.                 for(j=0;j<z_xsn;j++)
  225.                         if(nu(z_ans[i]&z_xs[j])==2){
  226. //                                printf("Conf...with");show(z_ans[i]);show(z_xs[j]);
  227.                                 return -1;}
  228. //                printf("No, there is no conf in z_ans and z_xs.\n");
  229. //                printf("Now z_ans (number is %d):",z_ansn);shows(z_ans,z_ansn);
  230. //                printf("$$$$$$$$$$Recal ssn...$$$$$$$$$\n");
  231. //                _getch();
  232.                 goto Begin;
  233.         }
  234.         return 0;
  235. }
  236. int _tmain(int argc, _TCHAR* argv[])
  237. {
  238.         unsigned xs[1000],ans[1000],z[M];//,aa[1000];
  239.         int kkk[30];
  240. //        int key[1000],zn[1000],sn[1000],xsl[1000],ansl[1000],aal[1000],n,aan;
  241.         int loop,xsn,ansn,k,i,zn;//,j;
  242.         int r,tn;
  243.         FILE *fp;

  244.         printf("The program is running...\n");
  245.         fopen_s(&fp,"d:\\xt.txt","w");
  246.         for(i=0;i<30;i++)kkk[i]=0;
  247. //        aan=0;
  248.         srand((unsigned)time(NULL));
  249.         init();
  250.         zn=ztoz(z_z,z,z_zn);
  251.         for(i=0;i<500000;i++)
  252.         {
  253. //                n=0;
  254.                 z_xsn=z_ansn=0;
  255.                 xsn=ansn=0;
  256.                 z_zn=ztoz(z,z_z,zn);
  257.                 for(loop=0;loop<500;loop++)
  258.                 {
  259. //                        printf("\n\n\nLoop %d:\n",loop);
  260.                         if(z_xsn<10)
  261.                         {
  262.                                 k=((unsigned)rand())%z_zn;z_x=z_z[k];
  263.                                 z_xs[z_xsn]=z_x;z_xsn++;
  264.                                 dozf();
  265.                                 continue;
  266.                         }

  267.                         if(z_xsn==10)tn=z_zn;

  268.                         xsn=ztoz(z_xs,xs,z_xsn);
  269.                         ansn=ztoz(z_ans,ans,z_ansn);

  270. //                        aan=0;
  271. //                        for(j=0;j<ansn;j++)
  272. //                        for(k=0;k<z_zn;k++)if(ans[j]==(ans[j]&z_z[k])){aa[aan]=z_z[k];aan++;}
  273.                        
  274. //                        if(aan>0){k=((unsigned)rand())%aan;z_x=aa[k];}
  275. //                        else {k=((unsigned)rand())%z_zn;z_x=z_z[k];}
  276.                         k=((unsigned)rand())%z_zn;z_x=z_z[k];
  277. //                        printf("Get a x:\n");show(z_x);
  278.                         z_xs[z_xsn]=z_x;z_xsn++;

  279. //                        printf("====Input=================================\n");
  280. //                        printf("Now z_xs (number is %d):",z_xsn);
  281. //                        shows(z_xs,z_xsn);
  282. //                        printf("Now z_ans (number is %d):",z_ansn);
  283. //                        shows(z_ans,z_ansn);
  284. //                        printf("-------------------------------------------\n");
  285.                         r=conf();
  286. //                        printf("\nr=%d.\n",r);
  287. //                        if(r==0){
  288. //                        printf("====Output=================================\n");
  289. //                        printf("Now z_xs (number is %d):",z_xsn);
  290. //                        shows(z_xs,z_xsn);
  291. //                        printf("Now z_ans (number is %d):",z_ansn);
  292. //                        shows(z_ans,z_ansn);
  293. //                        printf("-------------------------------------------\n");
  294. //                        }else printf("-1\n");
  295.                         if(r==0)
  296.                         {
  297. //                                printf("@@@@@@@ r=0, and doz() it....\n");
  298.                                 doz();
  299.                         }
  300.                         else
  301.                         {
  302. //                                printf("&&&&&&& r=-1, recover z_xsn x_ans and doz1() it...\n");
  303.                                 z_xsn=ztoz(xs,z_xs,xsn);
  304.                                 z_ansn=ztoz(ans,z_ans,ansn);
  305.                                 doz1();
  306.                         }
  307. //                        printf("z_zn[%d]=%d.\n",n,z_zn);
  308. //                        key[n]=k;sn[n]=z_xsn;zn[n]=z_zn;xsl[n]=z_xsn;ansl[n]=z_ansn;aal[n]=aan;n++;
  309.                         if(z_zn==0)break;
  310. //                        printf("-------------------------------------------\n");
  311.                 }
  312.                 kkk[z_xsn]++;
  313. if(z_xsn>22)
  314. {
  315.                 printf("\n\nFinish(@%d)[%d]...        %d\n**********************************************\n",loop,tn,z_xsn);
  316.                 printf("Now z_xs's number is %d):\n",z_xsn);
  317.                 shows(z_xs,z_xsn);
  318.                 printf("**********************************************\n");
  319. //                if(z_xsn>0)printf("%d,",z_xsn);
  320. //                for(j=0;j<n;j++)
  321. //                {
  322. //                        printf("key[%d]=%d(%d),  sn[%d]=%d,  zn[%d]=%d,  xsl[%d]=%d,  ansl[%d]=%d\n",j,key[j],aal[j],j,sn[j],j,zn[j],j,xsl[j],j,ansl[j]);
  323. //                }
  324.                 printf("=================================================================================\n\n");
  325. //                _getch();

  326.                 fprintf(fp,"\n\nFinish(@%d)...        %d\n**********************************************\n",loop,z_xsn);
  327.                 fprintf(fp,"Now z_xs's number is %d):\n",z_xsn);
  328.                 fshows(fp,z_xs,z_xsn);
  329.                 fprintf(fp,"**********************************************\n");
  330. //                if(z_xsn>0)printf("%d,",z_xsn);
  331. //                for(j=0;j<n;j++)
  332. //                {
  333. //                        printf("key[%d]=%d(%d),  sn[%d]=%d,  zn[%d]=%d,  xsl[%d]=%d,  ansl[%d]=%d\n",j,key[j],aal[j],j,sn[j],j,zn[j],j,xsl[j],j,ansl[j]);
  334. //                }
  335.                 fprintf(fp,"=================================================================================\n\n");
  336. //                _getch();
  337. }
  338.         }
  339.         printf("\nEnd\n");
  340.         for(i=0;i<30;i++)printf("%d,",kkk[i]);;
  341.         for(i=0;i<30;i++)fprintf(fp," %d,",kkk[i]);;
  342.         _getch();
  343.         return 0;
  344. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 12:05:21 | 显示全部楼层
代码挺难看懂的,还是大概介绍一下思路吧。
我的方法是不能完全运行时判断的,只能运行时淘汰部分解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-12-3 12:33 , Processed in 0.089395 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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