论坛 › 难题征解 › 果树问题讨论:这两个问题等价么？

mathe 发表于 2023-3-5 22:22:05

现在在
https://github.com/emathgroup/selectedTopics/tree/master/content/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服务器可用，可以帮忙运行一下。

wayne 发表于 2023-3-5 23:30:17

可以用linux命令 split 切分文件. 比如切割的每个文件是100000行,这样将产生 26 个文件. 分别是
split -l 100000 ./gen16.s2f
xaaxacxaexagxaixakxamxaoxaqxasxauxawxay
xabxadxafxahxajxalxanxapxarxatxavxaxxaz
要不 咱们就以这个为标准, 互相认领吧.差不多每个文件10万行,各自不到10天的时间.我正在跑 xaa文件,即1-10万行.

mathe 发表于 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开始

mathe 发表于 2023-3-6 07:22:12

发现find3.cpp里面有一行错了
sprintf(fname,"sed -r \'/^.{,%d}$/d\' tmpfileg%d >> out%d", 4*showd-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

mathe 发表于 2023-3-6 14:44:46

实际运行过程抽查了部分数据，发现运行的太慢了，这是因为我调大了部分搜索空间，希望能找到更多20树的最优解。
现在更新了一下，将18棵树lb从18改为19，另外20棵树lb原先设置27太大了（设置错误），改成24.修改后测试结果发现运行速度可以提高很多很多：
int lb[]={11,15,19,22,24};
实际参数可以参考 260#

mathe 发表于 2023-3-16 07:03:41

重新运行的结果出来了，和以前结果相比，19棵树20行从9个结果增加到了14个，新增了如下5个（三组复数解，两组实数解）:
ADGIBFIJCEILHIKMCFGNAEJNBDLNDHJOAFKOBGMOEGKPAHLPCDMPBEHQCJKQFLMQNOPQABCRDEFSGHRS
si=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=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=l2+l+1
si=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=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;


BDEGCGIJEHIKADHMCFKMEJLMFGHNBCHODILOAJNOACEPBFLPDKNPAFIQBJKQAGLRBMNRCDQREFOSGPQS
si=l3-l+1
si=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棵树20行所有结果

另外20棵树23行还是只有以前找到的3个解，而且我们现在可以证明只有这三组解了

mathe 发表于 2023-8-28 15:49:33

关于21棵树，现在还是只能找到24行的数据，没有找到25行的数据。现在运行了几个月时间，大概遍历了1/6左右的搜索空间，只找到
ABHIAGJLDEKLCFJMBGKMFHKNCILNEHJODIMOBDNPBCEQADFQHLMQCDGRAENRBFORACOSGIPSEFGTAKPTBJSTCHPUIJQUKRSU
ACFGDGHJBCIJBFHKADIKBEGMFJLMBDLNCENODEFPGKNPAJOPAELQCKMQCHLRDMORFIQRAHNSGIOSBPQSEHITABRTCDSTEJKU
ADEGBEHJFGIJAFHKBDIKCEFLBCGNEIMNGHLOBFMOACMPDHNPAILQCDOQDJMREKPRFNQRAJOSBLPSGKQSCHITABRTCJKUDLTU
ADFGEGHJBDIJBFHKAEIKBELMBCGNDHMNCFLOCDEPGILPAHOPACMQFINQFJMRENORDKQRAJLSGKOSBPQSCHITABRTCJKUDLTU
CFIJBCGKBFHLADJMDILNGHMNDEKOBJNOEGJPHIOPAELQFKPQAHKRCLMRGIQRDFGSBEMSACNSCEHTAFOTBDPTABIUCDQUEFRU
这几个候选解，其中第一个验证以后非法。
而2～4发现已经在链接中很久以前都找到了。
而最后一组CFIJBCGKBFHLADJMDILNGHMNDEKOBJNOEGJPHIOPAELQFKPQAHKRCLMRGIQRDFGSBEMSACNSCEHTAFOTBDPTABIUCDQUEFRU等价于
FGKPEILQDHJRHKSUIJSTGLTUDLNSFJMUEKOTLOPRJNPQKMQRDIMOFHNOEGMNCHPTBGQSAIRUBEPUCFRSADQTAMPSCOQUBNRT
以前在另一个链接中也已经找到了。

查看完整版本: 果树问题讨论:这两个问题等价么？