果树问题讨论:这两个问题等价么？

mathe · 发表于 2008-11-12 16:44:29

我前面的版本就是将数据拆分成数千个文件的,不过效果不好.所以现在改成少量几个大文件,然后用一个很大的hash值决定保存在文件的位置,不过结果效果同样不好.
没有想到移植到windows以后,速度又低了很多倍,看来这方面的确Windows不行.

无心人 · 发表于 2008-11-12 17:14:00

如果用小文件
比如，仅考虑前两组4字母组合
显然，每个文件的总可能解是能计算得到的
用个大文件，对每组双4字母组合与刘足够的空间
遇到需要保存的
建立个索引文件，保存每个组在大文件里的位置偏移

无心人 · 发表于 2008-11-12 17:14:31

不过这个文件可能比较大了

zgg___ · 发表于 2008-11-12 17:24:13

编了一个小程序，会随机产生一些解（只产生大于等于23的解），我的机器太慢了，而且最近编程总是犯错误，所以请大家测试一下。
直接运行就可以了，我这里一般1小时产生一个23的解。

mathe · 发表于 2008-11-13 09:28:53

原帖由 zgg___ 于 2008-11-12 17:24 发表
编了一个小程序，会随机产生一些解（只产生大于等于23的解），我的机器太慢了，而且最近编程总是犯错误，所以请大家测试一下。
直接运行就可以了，我这里一般1小时产生一个23的解。

是产生问题二的解吧?
问题在于边数比较多的时候,问题二的解是问题一的解的概率非常低.
以前面17颗树情况为例子,我曾用贪心法产生了数万个16行的问题二的解,结果没有一个是问题一的解,这也是为什么我前面会猜测17颗树时最多15行

zgg___ · 发表于 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，其它的解没有。

mathe · 发表于 2008-11-13 11:32:52

我建议与其搜索20颗树情况，不如现在先搜索18颗19颗树的问题。
你判断是否能够满足问题一用什么方法？如果有比较高效的方法很重要，我觉得我现在的程序太慢了一些。
另外对于各种情况，通常平均多少个问题2的结果可以有对应的问题2的解呢？

无心人 · 发表于 2008-11-13 11:49:20

是否能简化问题二的解
把同构的去掉

另外，是否总有一些模式无解
如果有很多模式
能快速的淘汰一批解

zgg___ · 发表于 2008-11-13 11:50:12

我把代码贴上来吧。编写的比较乱。上面发的可执行文件去掉了写盘的部分。
其中conf()和ssn()是用来判断的部分。
现在还是不敢确定算法判断是不是正确，但是如果和mathe程序的判断结果一致就比较对了。呵呵。

// n-13.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<conio.h>
#include<stdlib.h>
#include<time.h>
#define M 4845
unsigned ddy[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};
unsigned z_xs[1000],z_ans[1000],z_z[M],z_x;
int z_xsn,z_ansn,z_zn;
int show(unsigned d)
{
unsigned i;
for(i=0;i<20;i++)if(d&ddy[i])printf("%c",'A'+i);
return 0;
}
int shows(unsigned *d,int dn)
{
int i;
printf("[");
if(dn>0)
{
for(i=0;i<dn-1;i++){show(d[i]);printf("-");}
show(d[i]);
}
printf("]\n");
return 0;
}
int fshow(FILE *fp,unsigned d)
{
unsigned i;
for(i=0;i<20;i++)if(d&ddy[i])fprintf(fp,"%c",'A'+i);
return 0;
}
int fshows(FILE *fp,unsigned *d,int dn)
{
int i;
fprintf(fp,"[");
if(dn>0)
{
for(i=0;i<dn-1;i++){fshow(fp,d[i]);fprintf(fp,"-");}
fshow(fp,d[i]);
}
fprintf(fp,"]\n");
return 0;
}
int init()
{
int i1,i2,i3,i4;
z_zn=0;
for(i1=0;i1<17;i1++)
for(i2=i1+1;i2<18;i2++)
for(i3=i2+1;i3<19;i3++)
for(i4=i3+1;i4<20;i4++)
{
z_z[z_zn]=ddy[i1]|ddy[i2]|ddy[i3]|ddy[i4];
z_zn++;
}
return 0;
}
int ssn(unsigned *qtx,int qtxn,unsigned *ans)
{
unsigned lxz[1000],sxz1,sxz2,sxz3,sjx[3000],sjd1,sjd2,sjxl1[3000],sjxl2[3000],sjxl3[3000];
int i,i1,i2,i3,k1,k2,lxzn,sjxn,ansn;
unsigned z,zz,z1,z2,z3,sa1,sa2,sa3,sb1,sb2,sb3;
ansn=0;
for(z=1;z<=524288;z*=2)
{
lxzn=0;for(i=0;i<qtxn;i++)if(z&qtx[i]){lxz[lxzn]=qtx[i]^z;lxzn++;}
for(i1=0;i1<lxzn-2;i1++)
for(i2=i1+1;i2<lxzn-1;i2++)
for(i3=i2+1;i3<lxzn;i3++)
{
sxz1=lxz[i1];sxz2=lxz[i2];sxz3=lxz[i3];
sjxn=0;
for(z1=1;z1<=524288;z1*=2)
{ if((z1&sxz1)==0)continue;
for(z2=1;z2<=524288;z2*=2)
{ if((z2&sxz2)==0)continue;
for(z3=1;z3<=524288;z3*=2)
{ if((z3&sxz3)==0)continue;
zz=z1|z2|z3;
for(i=0;i<qtxn;i++)if(zz==(zz&qtx[i]))break;if(i<qtxn)continue;
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;
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;
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;
sjx[sjxn]=zz;sjxn++;
}}}
for(k1=0;k1<sjxn-1;k1++)
for(k2=k1+1;k2<sjxn;k2++)
{
sjd1=sjx[k1];sjd2=sjx[k2];
if(sjd1&sjd2)continue;
sa1=sjxl1[k1];sa2=sjxl2[k1];sa3=sjxl3[k1];
sb1=sjxl1[k2];sb2=sjxl2[k2];sb3=sjxl3[k2];
if((sa1&sb1)!=0&&(sa2&sb2)!=0&&(sa3&sb3)!=0){zz=(sa1&sb1)|(sa2&sb2)|(sa3&sb3);
for(i=0;i<qtxn;i++)if(zz==(zz&qtx[i]))break;if(i==qtxn){ans[ansn]=zz;ansn++;}}
}
}
}
return ansn;
}
int ztoz(unsigned *z0,unsigned *z,int zn)
{
int i;
for(i=0;i<zn;i++)z[i]=z0[i];
return zn;
}
int sdcd(unsigned *z,int zn)
{
int i,j,rn;
if(zn<=1)return zn;
rn=1;
for(i=1;i<zn;i++)
{
for(j=0;j<rn;j++)if(z[i]==z[j])break;
if(j==rn){z[rn]=z[i];rn++;}
}
return rn;
}
int nu(unsigned z)
{
int i,r;
r=0;
for(i=0;i<20;i++)if(ddy[i]&z)r++;
return r;
}
int doz()
{
int i,j,zn;
unsigned x,z[M];
zn=0;
for(j=0;j<z_zn;j++)
{
x=z_z[j];
for(i=0;i<z_xsn;i++)if(nu(x&z_xs[i])>=2)break;
if(i<z_xsn)continue;
for(i=0;i<z_ansn;i++)if(nu(x&z_ans[i])==2)break;
if(i<z_ansn)continue;
z[zn]=x;zn++;
}
z_zn=ztoz(z,z_z,zn);
return 0;
}
int dozf()
{
int i,j,zn;
unsigned x,z[M];
zn=0;
for(j=0;j<z_zn;j++)
{
x=z_z[j];
for(i=0;i<z_xsn;i++)if(nu(x&z_xs[i])>=2)break;
if(i<z_xsn)continue;
z[zn]=x;zn++;
}
z_zn=ztoz(z,z_z,zn);
return 0;
}
int doz1()
{
int i,rn;
rn=0;
for(i=0;i<z_zn;i++)
if(z_x!=z_z[i]){z_z[rn]=z_z[i];rn++;continue;}
z_zn=rn;
return rn;
}
int conf()
{
unsigned room[1000],ans[1000],imp[1000];
int roomn,ansn,impn,i,j;
Begin:
roomn=ztoz(z_xs,room,z_xsn);
roomn+=ztoz(z_ans,room+roomn,z_ansn);
// printf("the input of ssn is(roomn=%d):\n",roomn);
// shows(room,roomn);
ansn=ssn(room,roomn,ans);
if(ansn>0)
{
// printf("Add z_zans to ansn.\n");
ansn+=ztoz(z_ans,ans+ansn,z_ansn);
// printf("\nThere is %d(ansn) ans, and they are:\n",ansn);
// shows(ans,ansn);
ansn=sdcd(ans,ansn);
// printf("Get rid of the same ans, there is %d(ansn) ans lest, and they are:\n",ansn);shows(ans,ansn);
// printf("Cal imp of ans..\n");
impn=0;
for(i=0;i<ansn;i++)
for(j=i+1;j<ansn;j++)
if(nu(ans[i]&ans[j])==2){imp[impn]=ans[i]|ans[j];
// printf("There is 2 ans to 1 imp: [");show(ans[i]);show(ans[j]);show(imp[impn]);printf("]]].\n");
impn++;}
if(impn>0)
{
// printf("There is %d imp. check imp if or not conf with z_xs?\n",impn);
for(i=0;i<impn;i++)
{
for(j=0;j<z_xsn;j++)
if(nu(imp[i]&z_xs[j])>=2){
// printf("Conf...with ");show(imp[i]);show(z_xs[j]);
return -1;}
z_xs[z_xsn]=imp[i];z_xsn++;
}
// printf("No, there is no conf in imp. and new z_xsn is %d.\n",z_xsn);
// printf("Get rid of ans in the imp, and put to z_ans.\n");
z_ansn=0;
for(i=0;i<ansn;i++)
{
for(j=0;j<impn;j++)if(ans[i]==(ans[i]&imp[j]))break;
if(j!=impn){
// printf("GEtridof ans>>>");show(ans[i]);
continue;}
z_ans[z_ansn]=ans[i];z_ansn++;
}
}
else
{
// printf("There is no imp.\n");
z_ansn=ztoz(ans,z_ans,ansn);
}
// printf("Check conf with z_ans and all z_xs...\n");
for(i=0;i<z_ansn;i++)
for(j=0;j<z_xsn;j++)
if(nu(z_ans[i]&z_xs[j])==2){
// printf("Conf...with");show(z_ans[i]);show(z_xs[j]);
return -1;}
// printf("No, there is no conf in z_ans and z_xs.\n");
// printf("Now z_ans (number is %d):",z_ansn);shows(z_ans,z_ansn);
// printf("$$$$$$$$$$Recal ssn...$$$$$$$$$\n");
// _getch();
goto Begin;
}
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned xs[1000],ans[1000],z[M];//,aa[1000];
int kkk[30];
// int key[1000],zn[1000],sn[1000],xsl[1000],ansl[1000],aal[1000],n,aan;
int loop,xsn,ansn,k,i,zn;//,j;
int r,tn;
FILE *fp;
printf("The program is running...\n");
fopen_s(&fp,"d:\\xt.txt","w");
for(i=0;i<30;i++)kkk[i]=0;
// aan=0;
srand((unsigned)time(NULL));
init();
zn=ztoz(z_z,z,z_zn);
for(i=0;i<500000;i++)
{
// n=0;
z_xsn=z_ansn=0;
xsn=ansn=0;
z_zn=ztoz(z,z_z,zn);
for(loop=0;loop<500;loop++)
{
// printf("\n\n\nLoop %d:\n",loop);
if(z_xsn<10)
{
k=((unsigned)rand())%z_zn;z_x=z_z[k];
z_xs[z_xsn]=z_x;z_xsn++;
dozf();
continue;
}
if(z_xsn==10)tn=z_zn;
xsn=ztoz(z_xs,xs,z_xsn);
ansn=ztoz(z_ans,ans,z_ansn);
// aan=0;
// for(j=0;j<ansn;j++)
// for(k=0;k<z_zn;k++)if(ans[j]==(ans[j]&z_z[k])){aa[aan]=z_z[k];aan++;}
// if(aan>0){k=((unsigned)rand())%aan;z_x=aa[k];}
// else {k=((unsigned)rand())%z_zn;z_x=z_z[k];}
k=((unsigned)rand())%z_zn;z_x=z_z[k];
// printf("Get a x:\n");show(z_x);
z_xs[z_xsn]=z_x;z_xsn++;
// printf("====Input=================================\n");
// printf("Now z_xs (number is %d):",z_xsn);
// shows(z_xs,z_xsn);
// printf("Now z_ans (number is %d):",z_ansn);
// shows(z_ans,z_ansn);
// printf("-------------------------------------------\n");
r=conf();
// printf("\nr=%d.\n",r);
// if(r==0){
// printf("====Output=================================\n");
// printf("Now z_xs (number is %d):",z_xsn);
// shows(z_xs,z_xsn);
// printf("Now z_ans (number is %d):",z_ansn);
// shows(z_ans,z_ansn);
// printf("-------------------------------------------\n");
// }else printf("-1\n");
if(r==0)
{
// printf("@@@@@@@ r=0, and doz() it....\n");
doz();
}
else
{
// printf("&&&&&&& r=-1, recover z_xsn x_ans and doz1() it...\n");
z_xsn=ztoz(xs,z_xs,xsn);
z_ansn=ztoz(ans,z_ans,ansn);
doz1();
}
// printf("z_zn[%d]=%d.\n",n,z_zn);
// key[n]=k;sn[n]=z_xsn;zn[n]=z_zn;xsl[n]=z_xsn;ansl[n]=z_ansn;aal[n]=aan;n++;
if(z_zn==0)break;
// printf("-------------------------------------------\n");
}
kkk[z_xsn]++;
if(z_xsn>22)
{
printf("\n\nFinish(@%d)[%d]... %d\n**********************************************\n",loop,tn,z_xsn);
printf("Now z_xs's number is %d):\n",z_xsn);
shows(z_xs,z_xsn);
printf("**********************************************\n");
// if(z_xsn>0)printf("%d,",z_xsn);
// for(j=0;j<n;j++)
// {
// 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]);
// }
printf("=================================================================================\n\n");
// _getch();
fprintf(fp,"\n\nFinish(@%d)... %d\n**********************************************\n",loop,z_xsn);
fprintf(fp,"Now z_xs's number is %d):\n",z_xsn);
fshows(fp,z_xs,z_xsn);
fprintf(fp,"**********************************************\n");
// if(z_xsn>0)printf("%d,",z_xsn);
// for(j=0;j<n;j++)
// {
// 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]);
// }
fprintf(fp,"=================================================================================\n\n");
// _getch();
}
}
printf("\nEnd\n");
for(i=0;i<30;i++)printf("%d,",kkk[i]);;
for(i=0;i<30;i++)fprintf(fp," %d,",kkk[i]);;
_getch();
return 0;
}

复制代码

mathe · 发表于 2008-11-13 12:05:21

代码挺难看懂的，还是大概介绍一下思路吧。
我的方法是不能完全运行时判断的，只能运行时淘汰部分解。

账号		自动登录	找回密码
密码			欢迎注册

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