数学研发论坛

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

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

  [复制链接]
发表于 2008-11-13 12:06:02 | 显示全部楼层
你可以贴几个你否定和通过的解,我让我的程序判断一下看看结果是否匹配
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 12:09:25 | 显示全部楼层
我想求20个点,满足问题二,而且本质上不同的解的个数,也是一个有趣的问题。
所谓本质上不同,可以定义为通过字母的置换,不能相互得到。因此,判断两组解是不是相同,相当于判断图的同构。这样的效率或许不高。
我想或许可以采用一些统计量作为一组解的标示,而这个统计量对于字母的置换是不变的。比如说某个解中各个字母出现的次数,然后排序;在比如说解和置换不变的集合(从20个字母中任取5个的集合)各个元素相重合个数为2的元素的个数;也可以是解的置换不变群(这个难算);也可以是这些量的组合(愿意MD5也可以,呵呵);再用这些标示来区分解是否同构。这样或许能够比较高效的排除一些同构的解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 12:15:35 | 显示全部楼层
好的,谢谢mathe。
附件是随机1000组解。

xt.rar

45.16 KB, 下载次数: 3, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 12:43:36 | 显示全部楼层
原帖由 mathe 于 2008-11-13 09:28 发表

是产生问题二的解吧?
问题在于边数比较多的时候,问题二的解是问题一的解的概率非常低.
以前面17颗树情况为例子,我曾用贪心法产生了数万个16行的问题二的解,结果没有一个是问题一的解,这也是为什么我前面会猜测17 ...


问题二的可以由71层的程序产生。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 12:55:53 | 显示全部楼层
原帖由 mathe 于 2008-11-13 11:32 发表
我建议与其搜索20颗树情况,不如现在先搜索18颗19颗树的问题。
你判断是否能够满足问题一用什么方法?如果有比较高效的方法很重要,我觉得我现在的程序太慢了一些。
另外对于各种情况,通常平均多少个问题2的结果可 ...


按照267层的步骤,当发现某个节点不满足问题1时,就不往下展开了,这样可以加快搜索,但是没法知道两个问题解的比例。
关于判断方法,我把方法整理一下,再贴上来。这里面有一个挺有意思的数学问题。呵呵。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 12:57:01 | 显示全部楼层
原帖由 zgg___ 于 2008-11-13 12:15 发表
好的,谢谢mathe。
附件是随机1000组解。

我挑选了第1,2,4个,都不是问题1的解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 13:55:12 | 显示全部楼层
问题二的解如果能转化成某个置换群来讨论
因为置换群可分解成若干子群
可借此判定是否同构
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 14:12:06 | 显示全部楼层
虽然结果不对(先郁闷一下,呜呜……,不会用表情),但是,还是说明一下算法的思路吧。顺便也提出一个问题。呵呵。

对于一个给定关系M,设这个关系M规定了哪些点共线,(例如我们可以把M表示成:{{1,2,3,4},{1,5,6}...},也可以是:[ABCD-AEF-...]。凡是任意三点或更多点没有规定共线的,就必须不共线。)我们如何判断M是否对应于真实的情况?我们规定如果能按照M画出图来,那么P(M)=1,否则P(M)=0。

我们知道:通过ABC和BCD共线,可以推出ABCD共线,而M中可能规定ABD不共线。出现了这种情况,我们可以断定P(M)=0。可以看到M中不存在这种冲突是P(M)=1的必要条件,但不是充分条件。我们称这种判据为D1判据。(这样,lz的问题就是对于某类M,D1判据是不是全部判据?如大家所说,答案是否定的。但是,对于M中点的个数小于10的情况,D1或许就是全部判据。)

D2判据或许就是Desargues' theorem,由M中的点线关系,通过Desargues' theorem,可以得到一些新的共线的关系,这些共线关系如果不在M中,就可以得到P(M)=0。(我的程序中就是用的这种判断方法。取一个点,取过它的三条线,每条线上的取两个点,组成两个三角形,判断三条对应边的交点是不是属于这20个点,这样就得到一组新的共线关系,然后看它是不是和已有的关系冲突。这个过程还是蛮快的。)

我猜测在点数比较少的时候只用D1和D2判据就足够了。

其实,真正有趣的是:D3是什么呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 14:28:51 | 显示全部楼层
D1判断是最基本的。而仅仅对于原问题产生的那些点线关系是不需要D1判断的。当然通过D2产生的一些结果可以让D1再去判断,这个我过去也考虑过,但是后来发现远远不够。
不过你的规则中说除了给定那些关系以外,其他三点共线都不允许,在问题一中是没有这个限制的(也就是我们是允许3点共线的,只是这个共线不记在总行数里面;其实5点共线也是允许的,只是这个也不算,所以通常它不可能得到最优解)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-14 17:35:19 | 显示全部楼层

回复 259# mathe 的帖子

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

本版积分规则

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

GMT+8, 2020-12-4 16:45 , Processed in 0.080402 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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