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

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

  [复制链接]
发表于 2023-3-5 22:22:05 | 显示全部楼层
现在在
https://github.com/emathgroup/se ... tent/attached/trees
上传了Linux下运行的搜索代码:
find3.cpp 编译为find3
csolve.cpp编译为csolve
solve8s.cpp 编译为solve8s
其中find3.cpp会调用csolve,solve8s (代码中设置了路径为/home/zdu,需要修改为对应的路径)
然后将数据文件gen16.zip解压得到gen16.s2f,这个文件共2556714行,可以按行任意拆分成多个文件分别将在不同的目录独立运行。
运行过程会产生临时文件tmpfilef?,tmpfileg?等(所以处理不同数据需要在不同的目录)
并且会产生最终输出在文件out17,out18,out19,out20(大部分情况为空文件)。
我试着处理文件的前100行,花了870s. 所以按这个速度估计,全部处理完大概需要257.4天机时。不知道是否谁有空闲的Linux服务器可用,可以帮忙运行一下。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-3-5 23:30:17 | 显示全部楼层
可以用linux命令 split 切分文件. 比如切割的每个文件是100000行,这样将产生 26 个文件. 分别是
  1. split -l 100000 ./gen16.s2f
复制代码
  1. xaa  xac  xae  xag  xai  xak  xam  xao  xaq  xas  xau  xaw  xay
  2. xab  xad  xaf  xah  xaj  xal  xan  xap  xar  xat  xav  xax  xaz
复制代码

要不 咱们就以这个为标准, 互相认领吧.  差不多每个文件10万行,各自不到10天的时间.  我正在跑 xaa文件,即1-10万行.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-3-6 07:09:29 | 显示全部楼层
补充说明一下,由于csolve.cpp使用了一个比较老的语法,g++编译时需要加上选项 -fpermissive
另外代码处理不同数据时间差别很大,所以虽然同样10万行,但是运行时间可能会区别很大。
建议运行时将标准错误重定位,比如
./find3 < xaa 2>xaa.err
这样可以随时查看文件xaa.err确定代码运行的状态,而且如果运行过程中机器出现意外中断,可以根据xaa.err的状态从文件中间部分开始运行(重新切割文件,或者定义宏USE_INIT编译find3.cpp, 并且将最后一个编号保存在文件文件tag第一行中,然后运行)

我从文件xam开始
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-3-6 07:22:12 | 显示全部楼层
发现find3.cpp里面有一行错了
sprintf(fname,"sed -r \'/^.{,%d}$/d\' tmpfileg%d >> out%d", 4*showd[curnodes+1-INIT_NODES]-2, dep, curnodes+1);
红色部分遗漏了。github上文件我更新过了。
比较奇怪,遗漏了输入文件竟然还能有输出,只是结果不对。
另外由于原先设定输出数据过少,不容易发现问题,调整了一下输出数据的范围。正常情况应该处理一部分数据以后就会有些输出到文件out17,out18,out19等。我们先测试几次。
调整以后,xam.err运行到16行
out17可以产生17棵树15行的输出结果两个。看来至少到17棵没有问题了。
ABFHDEFKAGIKBCJLACDMBDGNAELNCHIOBEMOCFGPDHJPEIJQKLMQNOPQ
ABFHDEFKAGIKBDGLCHIMBCJNAELNACDOBEMOCFGPDHJPEIJQKLMQNOPQ

另外xam的运行速度好像远远慢于前100行:
16(188s)
17(540s)
18(544s)
19(610s)

另外在同样路径我上传了一个Makfile, 把find3.cpp, csolve.cpp, solve8s.cpp, newdef.cpp, Makefile都下载到同一个目录以后
运行make all就应该可以编译出可执行代码来。
然后可以在下面创建几个子目录分别存放数据文件xaa等,然后到子目录下运行比如
../find3<xaa > xaa.out 2>xaa.err&

现在xaa~xae保留给wayne, xam~xat保留给mathe
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-3-6 14:44:46 | 显示全部楼层
实际运行过程抽查了部分数据,发现运行的太慢了,这是因为我调大了部分搜索空间,希望能找到更多20树的最优解。
现在更新了一下,将18棵树lb从18改为19,另外20棵树lb原先设置27太大了(设置错误),改成24.修改后测试结果发现运行速度可以提高很多很多:
int lb[]={11,15,19,22,24};
实际参数可以参考 260#
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-3-16 07:03:41 | 显示全部楼层
重新运行的结果出来了,和以前结果相比,19棵树20行从9个结果增加到了14个,新增了如下5个(三组复数解,两组实数解):
ADGIBFIJCEILHIKMCFGNAEJNBDLNDHJOAFKOBGMOEGKPAHLPCDMPBEHQCJKQFLMQNOPQABCRDEFSGHRS
si[1]=4k2-2k+1
list nn1=0,-1+2k,1;
list nn2=2-2k,0,1;
list nn3=1,2-2k,0;
list nn4=0,1,1;
list nn5=-1+2k,1,1;
list nn6=1,0,0;
list nn7=0,1,0;
list nn8=1/2,1/2,1;
list nn9=0,0,1;
list nn10=1,0,1;
list nn11=-1+2k,-1+2k,1;
list nn12=1,2-2k,1;
list nn13=2-2k,2-2k,1;
list nn14=1,1-2k,0;
list nn15=2-2k,-1+2k,1;
list nn16=-1+2k,2,1;
list nn17=2,2-2k,1;
list nn18=1/2,k,1;
list nn19=1/2,1,1;

ADGICFHIBFGLAEHLCEGMBDHMGJKNEIKOAJMOCDNOAFKPDJLPBINPBEJQCKLQFMNQHOPQABCRDEFSGHRS
si[1]=4k2-2k+1
list nn1=1,-2k,0;
list nn2=1,0,1;
list nn3=0,2k,1;
list nn4=1,-1,0;
list nn5=-2k,2k,1;
list nn6=0,0,1;
list nn7=1,0,0;
list nn8=0,1,1;
list nn9=0,1,0;
list nn10=2-4k,-1+2k,1;
list nn11=-2k,-1+2k,1;
list nn12=1-2k,0,1;
list nn13=1-2k,2k,1;
list nn14=1,-1+2k,1;
list nn15=-2k,4k,1;
list nn16=1,-2k,1;
list nn17=1/2-1k,k,1;
list nn18=2k,1,1;
list nn19=-1,1,1;

ADGIEHIKBFGLCEGMAHJMCDHNGJKNCFIOAELOBDMOAFKPDJLPBINPBEJQCKLQFMNQHOPQABCRDEFSGHRS
si[1]=l2+l+1
si[2]=k+l+1
list nn1=1,0,1;
list nn2=1/3-1/3l,1/3-1/3l,1;
list nn3=0,-1l,1;
list nn4=-1l,0,1;
list nn5=0,1,0;
list nn6=-1l,-1l,1;
list nn7=0,0,1;
list nn8=1,-1,0;
list nn9=1,0,0;
list nn10=1/3-1/3l,2/3+1/3l,1;
list nn11=1,1+1l,0;
list nn12=1,1,1;
list nn13=0,1,1;
list nn14=-1/3-2/3l,1/3-1/3l,1;
list nn15=1,-1l,1;
list nn16=2/3-2/3l,1/3-1/3l,1;
list nn17=1/3-1/3l,2/3-2/3l,1;
list nn18=-1k,k,1;
list nn19=-1l,l,1;

BCDICEGKDFJLFGIMBELMEHJNAFKNCFHOAGJOAILPDHMPBGNPABHQIKOQADERBJKRCLQRACMSDNOSEPQS
si[1]=k2-k-1
list nn1=1,-1+1k,1;
list nn2=1,-1,0;
list nn3=0,1,0;
list nn4=1,-2+1k,0;
list nn5=0,1,1;
list nn6=2,0,1;
list nn7=0,0,1;
list nn8=2,-2+1k,1;
list nn9=1,0,0;
list nn10=4-2k,-6+4k,1;
list nn11=0,-2+2k,1;
list nn12=2-1k,-1+1k,1;
list nn13=1,0,1;
list nn14=-2k,2k,1;
list nn15=2,-2+2k,1;
list nn16=1-1k,-1+1k,1;
list nn17=2-1k,-2+2k,1;
list nn18=2-1k,-4+3k,1;
list nn19=1,k,1;
19.1.png

BDEGCGIJEHIKADHMCFKMEJLMFGHNBCHODILOAJNOACEPBFLPDKNPAFIQBJKQAGLRBMNRCDQREFOSGPQS
si[1]=l3-l+1
si[2]=k+l2-l
list nn1=1k-1l,1,1;
list nn2=1,1k-2l,0;
list nn3=0,1,1;
list nn4=1,-2-1k+1l,0;
list nn5=1,0,0;
list nn6=1-1l,1l,1;
list nn7=0,1,0;
list nn8=1-1l,0,1;
list nn9=0,0,1;
list nn10=0,-1k+2l,1;
list nn11=1,0,1;
list nn12=1k-1l,-1k+2l,1;
list nn13=1+1k-2l,-1k+2l,1;
list nn14=1-1l,1+1l,1;
list nn15=1-1k-1l,1l,1;
list nn16=1k,1,1;
list nn17=1k,-1k+1l,1;
list nn18=1k-1l,1-1k+2l,1;
list nn19=k,l,1;
19.2.png

19棵树20行所有结果

另外20棵树23行还是只有以前找到的3个解,而且我们现在可以证明只有这三组解了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-8-28 15:49:33 | 显示全部楼层
关于21棵树,现在还是只能找到24行的数据,没有找到25行的数据。现在运行了几个月时间,大概遍历了1/6左右的搜索空间,只找到
ABHIAGJLDEKLCFJMBGKMFHKNCILNEHJODIMOBDNPBCEQADFQHLMQCDGRAENRBFORACOSGIPSEFGTAKPTBJSTCHPUIJQUKRSU
ACFGDGHJBCIJBFHKADIKBEGMFJLMBDLNCENODEFPGKNPAJOPAELQCKMQCHLRDMORFIQRAHNSGIOSBPQSEHITABRTCDSTEJKU
ADEGBEHJFGIJAFHKBDIKCEFLBCGNEIMNGHLOBFMOACMPDHNPAILQCDOQDJMREKPRFNQRAJOSBLPSGKQSCHITABRTCJKUDLTU
ADFGEGHJBDIJBFHKAEIKBELMBCGNDHMNCFLOCDEPGILPAHOPACMQFINQFJMRENORDKQRAJLSGKOSBPQSCHITABRTCJKUDLTU
CFIJBCGKBFHLADJMDILNGHMNDEKOBJNOEGJPHIOPAELQFKPQAHKRCLMRGIQRDFGSBEMSACNSCEHTAFOTBDPTABIUCDQUEFRU
这几个候选解,其中第一个验证以后非法。
而2~4发现已经在链接中很久以前都找到了。
而最后一组CFIJBCGKBFHLADJMDILNGHMNDEKOBJNOEGJPHIOPAELQFKPQAHKRCLMRGIQRDFGSBEMSACNSCEHTAFOTBDPTABIUCDQUEFRU等价于
FGKPEILQDHJRHKSUIJSTGLTUDLNSFJMUEKOTLOPRJNPQKMQRDIMOFHNOEGMNCHPTBGQSAIRUBEPUCFRSADQTAMPSCOQUBNRT
以前在另一个链接中也已经找到了。

评分

参与人数 1威望 -3 金币 -3 贡献 -3 经验 -3 鲜花 -3 收起 理由
nyy -3 -3 -3 -3 -3 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-6-13 06:29 , Processed in 0.046475 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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