果树问题讨论:这两个问题等价么？
随着讨论的深入，其价值越发凸显了。问题1：即20棵树问题参考:20颗树问题 以及英文链接Orchard Planting Problem
问题2：20个字母A-T。取出x组。
每组4个字母
每个字母在同一组内只能出现一次，但可以同时包含在多个组内
所选取的x组中任意两组中至多有一个字母相同，求x的最大值
站内链接:
果树问题讨论
20棵树最优解计算
果树问题最优解大全
果树种植最优解精美图形作法探讨
植树问题王兴君解
植树问题蔡上人解
结果示例：
https://bbs.emath.ac.cn/data/attachment/forum/month_1201/1201181648cdcb9fcde04c4c06.png
https://bbs.emath.ac.cn/data/attachment/forum/month_1201/1201171137cbe9073ac035e25f.jpeg
https://bbs.emath.ac.cn/forum.php?mod=attachment&aid=OTQxM3xlZDljYTZiYnwxNjAxMzM1ODMwfDIwfDM5NTM%3D&noupdate=yes
已添加到A172993， A006065 ， A172992 应该不等价
－－－－－－－－－－－－－－－－－－－－－－－－－－－
算法简介:
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个.
这个链接历史过于悠久，已经不能访问:可以从 https://bbs.emath.ac.cn//forum.php?mod=redirect&goto=findpost&ptid=703&pid=81468&fromuid=20 寻找最新结果 是否可证呢:Q:
就是说对于问题2，证明平面是否一定存在x条直线对应所选的x组字母
当前计算进度表:
序号计算人员开始时间结束时间当前文件大小进度备注1mathe11.1611.230完成
2数学星空11.1912.030完成563#
3winxos11.210完成573#
4Frankenstein 11.2212.070完成575#
5mathe11.2312.010完成
6mathe11.2412.010完成
7mathe11.2612.080完成
8mathe12.0112.100完成
9mathe12.0112.110完成
10mathe12.0212.120完成
11无心人
mathe
12.04
12.13
12.17完成
12数学星空
mathe
12.08
12.10
12.140完成
13重新划分0完成
14mathe11.1712.020完成
15mathe11.1712.030完成
16mathe11.1712.030完成
17mathe12.0312.130完成
18重新划分0完成
19重新划分0完成
20重新划分0完成
21无心人11.1912.040完成533#
22liangbch12.0412.120完成
23liangbch11.1911.260完成527#
24liangbch11.2612.040完成569#
25sheng_jianguo12.0212.090完成582#
26sheng_jianguo11.2012.020完成560#
27sheng_jianguo11.2012.020完成560#
28sheng_jianguo11.2012.090完成582#
29sheng_jianguo11.1812.020完成560#
30sheng_jianguo11.1812.090完成582#
可执行程序下载链接:406#(注意binary*.zip里面的s8m.exe无法解压，需要同时使用s8m.zip文件）
数据文件在363#
使用说明在370#以及随后几个回复 结论应该是否定的，至少对于第二个题目，相对来说，用计算机构造简单很多
************
现在将上面还没有人参与计算的4个文件重新划分成24个文件，放入下面的附件中
以后的计算我们采用这些新的附件，这样就可以让更加多的人可以同时计算了
计算表格
序号
计算人员
开始时间
结束时间
当前文件大小
进度
备注
1
mathe12.1012.130完成2
mathe12.1012.130完成3
mathe12.1112.150完成4
mathe12.1112.150完成5
mathe12.1312.150完成6
mathe12.1312.160完成7
mathe12.1312.160完成8
mathe12.1412.150完成9
mathe12.1412.150完成10
winxos12.1112.170完成11
winxos12.110完成631＃12
sheng_jianguo12.1412.150完成612#13
sheng_jianguo12.1412.160完成14
sheng_jianguo12.1412.150完成612#15
sheng_jianguo12.1412.150完成612#16
sheng_jianguo12.1412.150完成612#17
sheng_jianguo12.1112.140完成18
sheng_jianguo12.1112.140完成19
sheng_jianguo12.1112.140完成20
sheng_jianguo12.0912.110完成594#21
sheng_jianguo12.0912.140完成22
sheng_jianguo12.0912.110完成594#23
sheng_jianguo12.0912.110完成594#24
sheng_jianguo12.0912.140完成594#
问题一自由度太高了 问题二，得到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;
char CH = "ABCDEFGHIJKLMNOPQRST";
char TEMP;
int m = 0;
void init(void)
{
int i;
for (i = 0; i < max; i ++)
Result = '\0';
TEMP = '\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 = TEMP;
printf("%c", TEMP);
}
m ++;
printf("\n");
}
else
{
if (position < 20)
for (i = position; i < 20; i ++)
{
TEMP = CH;
bool = 1;
if (level > 0)
for (l = 0; l < level; l ++)
if (bool == 1)
if (TEMP == TEMP)
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, TEMP) != 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);
} 数学吧有个叫“没——问题”的给出过x=24的解
这个问题是他和我说的，当时没在意，现在怎么也联系不上他了 唉，没——问题发给我的那封邮件找不到了:L
他当时详细的说了这两个问题：
给出了n=1到20时x值得一个列表，并说这是植树（4棵每行）问题的上界
所以我才怀疑这两个问题是等价的
还有一些其他的结论，我想不起来了，邮件应该没删，我再去找囧 当时他的邮件附件里有个程序，运行之后就一个命令行窗口，什么也不显示，而且电脑风扇狂响，我还以为是病毒，赶紧强行关闭了:L
结果好几天后在根目录下发现一个1M大的文本文件.....里面全是问题二x=24的解囧 得到x = 23的就一闪就输出了阿
另外，对任何A－－T的置换排列
对我的解作相应置换
则得到另外一个解
所以有多少不等价置换，似乎就存在多少解