数，树，肚子， 无心

mathe

突然想到这个问题应该能够用深度优先的方法遍历所有的方案(而不是采用过去的广度优先的方法).
当然使用深度优先的方法需要有合适的剪枝方法来避免重复访问同一个子树.
而好处是不需要大量的磁盘空间来缓存中间数据,而且父结点的一些计算结果可以在子结点中继续利用,从而加快计算速度.
不过要实现这个功能,又要花费不少时间

无心人

d6的完全算完了
你新修改的现在没心情测试
等等吧

mathe

这个帖子里面提到的方法用有限域来替代有理数域进行计算.原先我觉得丢失真正的解的概率应该挺小的.但是现在发现原先忽略了一个问题:
比如我们查看18棵数18行的一个结果:

这个图里面的坐标无法用有理数来表示,而是使用了一个参数t,其中t是方程$t^2+3t+1=0$的一个实数解.
这个方法实质上是将坐标范围改为有理数域Q的扩展域Q[t].
而$t^2+3t+1=(t+3/2)^2-5/4={(2t+3)^2-5}/4$
所以如果我们改为在有限域$F_p$里面计算,如果5是关于素数p的平方剩余,那么$t^2+3t+1$在$F_p$中就可以因子分解了,而导致所有坐标最终还是落在$F_p$而不是其扩展域中.而由于有理数范围内合法的解必须在扩展域,这个表明在对应的$F_p$中这个解必然会被淘汰.
比如说如果p=11,那么由于$4^2-=5(mod 11)$,所以5是关于素数11的平方剩余,也就是$t^2+3t+1-=(t-6)(t-2)(mod 11)$,也就是如果是在有限域$F_11$中,那么t必然是6或2,无论哪种,对应的结果都是有理系数解,必然不符合条件.

无心人

这么说，必须换一种思路了

你使劲想吧

mathe

一种方法是换不同的有限域,不断的试.
另外一种方法就还是用原先的计算方法,但是改善一些计算(这也是为什么我想用LiDIA,可以直接在代数数域而不是有理数域内进行计算).另外,搜索过程可以改成深度优先的方法.

mathe

现在试着写了一个深度优先搜索的代码.而且全部在某个有限域上计算.
不知道是否还存在bug.
速度还是挺慢的.最好还是能够在很多机器上运行.
附件中zip文件包含两个子目录,ocd_src是源代码,ocd_run是运行路径.
如果要在某个机器上运行部分数据,将ocd_run拷贝到那个机器中,修改文件tag.txt(改变程序开始运行的数据,参数可以从0到1157(文件all14s的行的数目)),运行restartsm.exe将安装好程序为后台运行(要求有管理员的权限).
然后重新启动机器就会运行了.
运行的结果将在文件sm.out中.
但是程序运行速度非常慢.主要是对于all14s中每一行数据还需要处理很长时间,而现在中间如果出现中断,就需要从头开始
ocdf.zip (89.91 KB, 下载次数: 5)

2009-10-20 14:23 上传

点击文件名下载附件

mathe

计算速度还是太慢。现在发现主要瓶颈在于解方程过滤数据部分，实在太慢了。而仅仅通过搜索产生一些候选解速度可以非常之快。