果树问题讨论:这两个问题等价么？

mathe

你可以贴几个你否定和通过的解，我让我的程序判断一下看看结果是否匹配

zgg___

我想求20个点，满足问题二，而且本质上不同的解的个数，也是一个有趣的问题。 所谓本质上不同，可以定义为通过字母的置换，不能相互得到。因此，判断两组解是不是相同，相当于判断图的同构。这样的效率或许不高。 我想或许可以采用一些统计量作为一组解的标示，而这个统计量对于字母的置换是不变的。比如说某个解中各个字母出现的次数，然后排序；在比如说解和置换不变的集合（从20个字母中任取5个的集合）各个元素相重合个数为2的元素的个数；也可以是解的置换不变群（这个难算）；也可以是这些量的组合（愿意MD5也可以，呵呵）；再用这些标示来区分解是否同构。这样或许能够比较高效的排除一些同构的解。

zgg___

好的，谢谢mathe。 附件是随机1000组解。

zgg___

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

问题二的可以由71层的程序产生。

zgg___

原帖由 mathe 于 2008-11-13 11:32 发表 我建议与其搜索20颗树情况，不如现在先搜索18颗19颗树的问题。 你判断是否能够满足问题一用什么方法？如果有比较高效的方法很重要，我觉得我现在的程序太慢了一些。 另外对于各种情况，通常平均多少个问题2的结果可 ...

按照267层的步骤，当发现某个节点不满足问题1时，就不往下展开了，这样可以加快搜索，但是没法知道两个问题解的比例。 关于判断方法，我把方法整理一下，再贴上来。这里面有一个挺有意思的数学问题。呵呵。

mathe

原帖由 zgg___ 于 2008-11-13 12:15 发表 好的，谢谢mathe。 附件是随机1000组解。

我挑选了第1,2,4个，都不是问题1的解。

无心人

问题二的解如果能转化成某个置换群来讨论 因为置换群可分解成若干子群 可借此判定是否同构

zgg___

虽然结果不对（先郁闷一下，呜呜……，不会用表情），但是，还是说明一下算法的思路吧。顺便也提出一个问题。呵呵。 对于一个给定关系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是什么呢？

mathe

D1判断是最基本的。而仅仅对于原问题产生的那些点线关系是不需要D1判断的。当然通过D2产生的一些结果可以让D1再去判断，这个我过去也考虑过，但是后来发现远远不够。 不过你的规则中说除了给定那些关系以外，其他三点共线都不允许，在问题一中是没有这个限制的（也就是我们是允许3点共线的，只是这个共线不记在总行数里面；其实5点共线也是允许的，只是这个也不算，所以通常它不可能得到最优解）

没——问题

特来恭喜2^8楼