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

0→∞ · 发表于 2008-7-31 23:38:32

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

问题1：即20棵树问题
参考:20颗树问题以及英文链接Orchard Planting Problem

问题2：20个字母A-T。取出x组。
　每组4个字母
　每个字母在同一组内只能出现一次，但可以同时包含在多个组内
　所选取的x组中任意两组中至多有一个字母相同，求x的最大值

站内链接:
果树问题讨论
20棵树最优解计算
果树问题最优解大全
果树种植最优解精美图形作法探讨
植树问题王兴君解
植树问题蔡上人解

结果示例：

已添加到A172993， A006065 ， A172992

mathe · 发表于 2008-8-1 07:58:27

应该不等价
－－－－－－－－－－－－－－－－－－－－－－－－－－－
算法简介:
i)搜索算法，主要是去搜索问题二的解的方法去搜索，其中比较重要的一个的方法在259#,它极大的缩小了搜索范围。
ii)问题一方案的判定问题。实际上现在我并没有一个可以完全判断一个问题二方案是否存在对应问题一解的程序。但是51#的方案可以淘汰大部分非法方案。
所以结合i)和ii),我们可以有比较好的方法来搜索问题一的解。
iii)而在搜索过程中，有很多问题一的方案方案实际上是等价的，它们可以通过置换树的字母来相互转换，对于这样的结果，我们也不需要重复搜索它们，为此，我提供了一个程序将每个问题一的方案的字母表示进行标准化（程序中node_edge_set模板类），其主要思路就是如果两个点的度数不同，那么它们必然不同类。然后如果两条边所通过的点集的类别不同，那么边也不同类。再然后如果两个点所过的边的集合的类别不同，这些点又不同类。当然即使这样递归下去，最后还可能有些不同的图无法区分，这时，我们就可以通过对某些点打上一个特殊的标签（于是它可以和原先同类的点区分开），最终得到一个所有点和边的非类都区分开的图。但是标签打在不同的点上，结果会不同，这个就需要我们从所有这些结果中选择一个标准的（字典排列顺序最小的一个）。
iv)最后还有一个加强就是在i)的搜索中，直接和iii)相结合，那么整个搜索空间可以看成一个有向无环图，其中图中每个点是一个问题二的方案。于是对于图中每个点，它可以有多个父节点，这个会导致一个点可以被通过多个父节点重复搜索到。而这时，我们可以对于每个搜索到的节点，判断当前搜索路径是不是通过它的第一个父节点，如果不是，也把分支裁减（另外由于重边的存在，程序会对同时保存每个节点的所有孩子节点，然后将重复的淘汰）

v) 357# 给出了ii)的判定问题一个性能更优的淘汰算法。

附件给出了果树问题14棵树到18棵树的一些候选解（有可能包含一些非法解，但是包含所有合法解）
其中s14all给出14棵树6行以上的所有解。
s15all给出15棵树8行以上并且行数加度数最小的数的度数不小于10，既260#中的$T_15$
   s16.len13.f, s16.len14.f, s16.len15.f 给出了16棵树13～15行的所有候选解
  s17fromm13 给出一例16棵树13行以上候选解构造的17棵树和18棵树的部分解。
  其中包含17棵树16行以上所有解。
  18to20中给出18棵树以上的解，其中包含18,19棵树所有最优解.但是20棵树23行现在只找到2个.

d14to18.tgz (477.97 KB, 下载次数: 15)
这个链接历史过于悠久，已经不能访问:可以从 https://bbs.emath.ac.cn//forum.p ... 1468&fromuid=20 寻找最新结果

0→∞ · 发表于 2008-8-1 08:55:49

是否可证呢

就是说对于问题2，证明平面是否一定存在x条直线对应所选的x组字母

当前计算进度表:

序号	计算人员	开始时间	结束时间	当前文件大小	进度	备注
1	mathe	11.16	11.23	0	完成
2	数学星空	11.19	12.03	0	完成	563#
3	winxos	11.21		0	完成	573#
4	Frankenstein	11.22	12.07	0	完成	575#
5	mathe	11.23	12.01	0	完成
6	mathe	11.24	12.01	0	完成
7	mathe	11.26	12.08	0	完成
8	mathe	12.01	12.10	0	完成
9	mathe	12.01	12.11	0	完成
10	mathe	12.02	12.12	0	完成
11	无心人 mathe	12.04 12.13	12.17		完成
12	数学星空 mathe	12.08 12.10	12.14	0	完成
13	重新划分			0	完成
14	mathe	11.17	12.02	0	完成
15	mathe	11.17	12.03	0	完成
16	mathe	11.17	12.03	0	完成
17	mathe	12.03	12.13	0	完成
18	重新划分			0	完成
19	重新划分			0	完成
20	重新划分			0	完成
21	无心人	11.19	12.04	0	完成	533#
22	liangbch	12.04	12.12	0	完成
23	liangbch	11.19	11.26	0	完成	527#
24	liangbch	11.26	12.04	0	完成	569#
25	sheng_jianguo	12.02	12.09	0	完成	582#
26	sheng_jianguo	11.20	12.02	0	完成	560#
27	sheng_jianguo	11.20	12.02	0	完成	560#
28	sheng_jianguo	11.20	12.09	0	完成	582#
29	sheng_jianguo	11.18	12.02	0	完成	560#
30	sheng_jianguo	11.18	12.09	0	完成	582#

可执行程序下载链接:406#(注意binary*.zip里面的s8m.exe无法解压，需要同时使用s8m.zip文件）
数据文件在363#
使用说明在370#以及随后几个回复

mathe · 发表于 2008-8-1 09:01:14

结论应该是否定的，至少对于第二个题目，相对来说，用计算机构造简单很多

************
现在将上面还没有人参与计算的4个文件重新划分成24个文件，放入下面的附件中
以后的计算我们采用这些新的附件，这样就可以让更加多的人可以同时计算了

nid1.tar.gz (314.25 KB, 下载次数: 5)

nid9.tar.gz (319.38 KB, 下载次数: 7)

nid13.tar.gz (323.85 KB, 下载次数: 7)

计算表格

序号	计算人员	开始时间	结束时间	当前文件大小	进度	备注
1	mathe	12.10	12.13	0	完成
2	mathe	12.10	12.13	0	完成
3	mathe	12.11	12.15	0	完成
4	mathe	12.11	12.15	0	完成
5	mathe	12.13	12.15	0	完成
6	mathe	12.13	12.16	0	完成
7	mathe	12.13	12.16	0	完成
8	mathe	12.14	12.15	0	完成
9	mathe	12.14	12.15	0	完成
10	winxos	12.11	12.17	0	完成
11	winxos	12.11		0	完成	631＃
12	sheng_jianguo	12.14	12.15	0	完成	612#
13	sheng_jianguo	12.14	12.16	0	完成
14	sheng_jianguo	12.14	12.15	0	完成	612#
15	sheng_jianguo	12.14	12.15	0	完成	612#
16	sheng_jianguo	12.14	12.15	0	完成	612#
17	sheng_jianguo	12.11	12.14	0	完成
18	sheng_jianguo	12.11	12.14	0	完成
19	sheng_jianguo	12.11	12.14	0	完成
20	sheng_jianguo	12.09	12.11	0	完成	594#
21	sheng_jianguo	12.09	12.14	0	完成
22	sheng_jianguo	12.09	12.11	0	完成	594#
23	sheng_jianguo	12.09	12.11	0	完成	594#
24	sheng_jianguo	12.09	12.14	0	完成	594#

无心人 · 发表于 2008-8-1 09:41:07

问题一自由度太高了

无心人 · 发表于 2008-8-1 14:12:49

问题二，得到23个的解

0: ABCD
1: AEFG
2: AHIJ
3: AKLM
4: ANOP
5: AQRS
6: BEHK
7: BFIL
8: BGJM
9: BNQT
10: CEIM
11: CFHN
12: CGKO
13: CJLP
14: DEJN
15: DFKP
16: DGHL
17: DIOQ
18: DMRT
19: ELOR
20: EPST
21: FJOS
22: GINR
23: HMPQ

复制代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max 256
char Result[max][5];
char CH[21] = "ABCDEFGHIJKLMNOPQRST";
char TEMP[5];
int m = 0;
void init(void)
{
int i;
for (i = 0; i < max; i ++)
Result[i][5] = '\0';
TEMP[5] = '\0';
}
void Circle(int level, int position)
{
int i, j, k, l;
int bool;
int sum;
char c;
if (level == 4)
{
printf("%d: ", m);
for (i = 0; i < 4; i ++)
{
Result[m][i] = TEMP[i];
printf("%c", TEMP[i]);
}
m ++;
printf("\n");
}
else
{
if (position < 20)
for (i = position; i < 20; i ++)
{
TEMP[level] = CH[i];
bool = 1;
if (level > 0)
for (l = 0; l < level; l ++)
if (bool == 1)
if (TEMP[l] == TEMP[level])
bool = 0;
if (bool == 1)
{
if (m > 0)
{
bool = 1;
for (j = 0; j < m; j ++)
if (bool == 1)
{
sum = 0;
for (l = 0; l <= level; l ++)
if (strchr(Result[j], TEMP[l]) != NULL)
sum ++;
if (sum > 1)
bool = 0;
}
if (bool == 1)
Circle(level + 1, position + 1);
}
else
Circle(level + 1, position + 1);
}
}
}
}
int main(void)
{
int i, j, k, l, m, n;
char c;
int bool;
init();
Circle(0, 0);
}

复制代码

0→∞ · 发表于 2008-8-1 20:26:37

数学吧有个叫“没——问题”的给出过x=24的解

这个问题是他和我说的，当时没在意，现在怎么也联系不上他了

0→∞ · 发表于 2008-8-1 21:39:11

唉，没——问题发给我的那封邮件找不到了

他当时详细的说了这两个问题：
给出了n=1到20时x值得一个列表，并说这是植树（4棵每行）问题的上界

所以我才怀疑这两个问题是等价的
还有一些其他的结论，我想不起来了，邮件应该没删，我再去找囧

0→∞ · 发表于 2008-8-1 21:47:09

当时他的邮件附件里有个程序，运行之后就一个命令行窗口，什么也不显示，而且电脑风扇狂响，我还以为是病毒，赶紧强行关闭了

结果好几天后在根目录下发现一个1M大的文本文件.....里面全是问题二x=24的解囧

无心人 · 发表于 2008-8-1 22:19:23

得到x = 23的就一闪就输出了阿

另外，对任何A－－T的置换排列
对我的解作相应置换
则得到另外一个解

所以有多少不等价置换，似乎就存在多少解

账号		自动登录	找回密码
密码			欢迎注册

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

相关帖子