数学研发论坛

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

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

  [复制链接]
发表于 2008-12-26 03:48:07 | 显示全部楼层
不知道这道题有什么新进展了?

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

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

还是这个思路,也许可以利用同构,证明比如x=28时,所有的解都同构,如果这样的话,
只需求出一个解,并验证就能判断28了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-19 09:01:29 | 显示全部楼层
思路是没有错,不过在"数"的数目比较多时,对应的第二题解的数目会多的无法忍受(也就是这时是第一个问题解的概率会非常非常之低).
我采用的方法基本上都是先构造出n-1棵树时问题1中的一些解.然后通过扩充它们得到一些问题2中n棵树的解,然后再过滤它们.不过即使采用这种方法,在达到16棵树以上时也很难继续下去.所以现在的方法是在n-1棵树到n棵树的过度中,会使用程序判断同时淘汰一些不再问题1中的解(不过判断越精确,判断速度越慢).然后在对这些数据进行排序,去掉同构的解,最后判断是否的确是问题1的解.
不过即使采用这样的方法,也只能解决18棵树的问题.而估计如果给我3到4年的时间,可能可以解决19棵树的问题,但是对于20棵树,还得看看运气
另外可以参考链接/viewthrea ... fromuid=20#pid16387 中的代码及说明
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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 | 显示全部楼层


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

大家给个意见
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-21 09:22:04 | 显示全部楼层
要不然先看看射影几何.计算几何没有必要.
用到知识应该有射影几何,解析几何和线性代数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-21 13:42:01 | 显示全部楼层
哦, 那就是高等几何了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-21 15:14:24 | 显示全部楼层
应该不算,挺简单的规则,只是普通教育不学而已
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-21 15:24:07 | 显示全部楼层
我看高等几何的书里有这个内容的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-21 15:37:52 | 显示全部楼层
你程序也忒复杂了点
上万行

呵呵
我想可能是无法看懂了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-17 16:47:56 | 显示全部楼层
现在进度是在
/viewthrea ... fromuid=20#pid17510
中给出了19棵树种20行的例子(我总共找到5组不同的解,但是只有一个提供了图片)

而通过射影变换可以将图变换成

另外链接
/viewthrea ... fromuid=20#pid17137
中给出了一个20棵树种23行的例子
而在链接
/viewthrea ... fromuid=20#pid17254
中,__zgg对这个图片进行等价变化,使得图片看起来更加美观一些:
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-6-18 08:27 , Processed in 0.912106 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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