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

litaoye 发表于 2008-12-26 03:48:07

不知道这道题有什么新进展了?

我的思路还是先求第二题的集合，然后再代入到第一道题中作验证，判断是否存在对应的直线。
不过求集合也许可以用构造法，具体我也没试过，只是一个想法。

另外还有个思路，就是可能x > 24时，许多解都是同构的，交换集合中的几个数，就能得到另一个集合，
需要设计一个hash算法，这样就不用每个集合都做验证了（如果直线判断程序效率不高的话）。

还是这个思路，也许可以利用同构，证明比如x=28时，所有的解都同构，如果这样的话，
只需求出一个解，并验证就能判断28了。

mathe 发表于 2009-2-19 09:01:29

思路是没有错,不过在"数"的数目比较多时,对应的第二题解的数目会多的无法忍受(也就是这时是第一个问题解的概率会非常非常之低).
我采用的方法基本上都是先构造出n-1棵树时问题1中的一些解.然后通过扩充它们得到一些问题2中n棵树的解,然后再过滤它们.不过即使采用这种方法,在达到16棵树以上时也很难继续下去.所以现在的方法是在n-1棵树到n棵树的过度中,会使用程序判断同时淘汰一些不再问题1中的解(不过判断越精确,判断速度越慢).然后在对这些数据进行排序,去掉同构的解,最后判断是否的确是问题1的解.
不过即使采用这样的方法,也只能解决18棵树的问题.而估计如果给我3到4年的时间,可能可以解决19棵树的问题,但是对于20棵树,还得看看运气:)
另外可以参考链接http://bbs.emath.ac.cn/viewthread.php?tid=1239&page=1&fromuid=20#pid16387 中的代码及说明

mathe 发表于 2009-2-20 17:40:29

找到的18棵树种17/18行的数据（每棵树至少3行）,坐标就不贴出来了,可以用来构造更多树情况的解(果树问题的解):
ABIOACJPAKLQBCMQBKPRCNORDELPDFKODIJREFMREJOQFNPQGHQRGIMPGJLNHIKNHLMO
ABCPADHIAEJKBHLQBJMRCINRCKOQDEQRDMOPELNPFGLMFJNQFKPRGHORGIPQHKMNIJLO
ABFGACHRAIJKBILMBNORCJLPCMNQDEPQDFHMDKLREGKOEJMRFJOQFKNPGHLNGIQRHIOP
ABEFAGHIAJKLBMNOBPQRCEGPCFHQCIJMDEKMDFLNDHOREJOQFIKRGJNRGLMQHKNPILOP
ABCHAIJPAKLQBIMQBJNRCIKRCMOPDEFIDHLPDJOQEHNQELMRFHORFKNPGJKMGLNOGPQR
ABHPACIQAJKRBJLQBKMNCLNRCMOPDELPDFKQDIMREHMQEIJOFHORFJNPGHINGKLOGPQR
ABFGACHIAJKRBHLRBJMNCFMOCPQRDEFRDGIMDKNPEGKLEJOQFLNQGHOPHKMQIJLPINOR
ABGHAIJQAKLRBIMRBNOQCDJKCGPQCHNRDLMQDOPREFQREGKOEHJMFILOFMNPGJLNHIKP
ABCDAEFGAHIJAKLMBEKNBHLOBMPQCEIPCFHMCJQRDEOQDGJKDHNRFINOFKPRGILQGMORJLNP
AEFGAHIJAKLMBEHNBIKOBJPQCELPCFJKCMQRDEOQDGHMDKNRFHPRFLNOGILQGJORIMNP
ABHIACJKADLPBCMQBLNRCHPRDEQRDMNOEIJMEKNPFGMRFHLOFIPQGJOPGKLQHJNQIKOR

无心人 发表于 2009-2-20 23:47:15

:lol

还是看的稀里糊涂啊
有必要买本计算几何的书么？

大家给个意见

mathe 发表于 2009-2-21 09:22:04

要不然先看看射影几何.计算几何没有必要.
用到知识应该有射影几何,解析几何和线性代数

无心人 发表于 2009-2-21 13:42:01

哦， 那就是高等几何了

mathe 发表于 2009-2-21 15:14:24

应该不算,挺简单的规则,只是普通教育不学而已

无心人 发表于 2009-2-21 15:24:07

我看高等几何的书里有这个内容的

无心人 发表于 2009-2-21 15:37:52

你程序也忒复杂了点
上万行

呵呵
我想可能是无法看懂了

mathe 发表于 2009-3-17 16:47:56

现在进度是在
http://bbs.emath.ac.cn/viewthrea ... fromuid=20#pid17510
中给出了19棵树种20行的例子(我总共找到5组不同的解,但是只有一个提供了图片)
https://bbs.emath.ac.cn/data/attachment/forum/month_0903/20090317_f161a3cbb7b2bcb06b1bsf0UFHzFUBy5.gif
而通过射影变换可以将图变换成
https://bbs.emath.ac.cn/data/attachment/forum/month_0904/20090401_2495f0e7c251a16598c9l0YL8Tky0MKe.gif
另外链接
http://bbs.emath.ac.cn/viewthrea ... fromuid=20#pid17137
中给出了一个20棵树种23行的例子
https://bbs.emath.ac.cn/data/attachment/forum/month_0903/20090309_2fc4800fac7e864c86d47NRKxZZwcQgG.gif而在链接
http://bbs.emath.ac.cn/viewthrea ... fromuid=20#pid17254
中,__zgg对这个图片进行等价变化,使得图片看起来更加美观一些:
https://bbs.emath.ac.cn/data/attachment/forum/month_0903/20090311_65bc7300b7736c4664844cdOS0d0Ed4O.gif

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