数学研发论坛

 找回密码
 欢迎注册
查看: 86389|回复: 642

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

[复制链接]
发表于 2008-7-31 23:38:32 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

问题2:20个字母A-T。取出x组。
 每组4个字母
 每个字母在同一组内只能出现一次,但可以同时包含在多个组内
 所选取的x组中任意两组中至多有一个字母相同,求x的最大值
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-1 07:58:27 | 显示全部楼层
应该不等价
---------------------------
算法简介:
i)搜索算法,主要是去搜索问题二的解的方法去搜索,其中比较重要的一个的方法在260#,它极大的缩小了搜索范围。
ii)问题一方案的判定问题。实际上现在我并没有一个可以完全判断一个问题二方案是否存在对应问题一解的程序。但是51#的方案可以淘汰大部分非法方案。
所以结合i)和ii),我们可以有比较好的方法来搜索问题一的解。
iii)而在搜索过程中,有很多问题一的方案方案实际上是等价的,它们可以通过置换树的字母来相互转换,对于这样的结果,我们也不需要重复搜索它们,为此,我提供了一个程序将每个问题一的方案的字母表示进行标准化(程序中node_edge_set模板类),其主要思路就是如果两个点的度数不同,那么它们必然不同类。然后如果两条边所通过的点集的类别不同,那么边也不同类。再然后如果两个点所过的边的集合的类别不同,这些点又不同类。当然即使这样递归下去,最后还可能有些不同的图无法区分,这时,我们就可以通过对某些点打上一个特殊的标签(于是它可以和原先同类的点区分开),最终得到一个所有点和边的非类都区分开的图。但是标签打在不同的点上,结果会不同,这个就需要我们从所有这些结果中选择一个标准的(字典排列顺序最小的一个)。
iv)最后还有一个加强就是在i)的搜索中,直接和iii)相结合,那么整个搜索空间可以看成一个有向无环图,其中图中每个点是一个问题二的方案。于是对于图中每个点,它可以有多个父节点,这个会导致一个点可以被通过多个父节点重复搜索到。而这时,我们可以对于每个搜索到的节点,判断当前搜索路径是不是通过它的第一个父节点,如果不是,也把分支裁减(另外由于重边的存在,程序会对同时保存每个节点的所有孩子节点,然后将重复的淘汰)

附件给出了果树问题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)

18to20.zip

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

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-1 08:55:49 | 显示全部楼层
是否可证呢
就是说对于问题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#以及随后几个回复
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-1 09:01:14 | 显示全部楼层
结论应该是否定的,至少对于第二个题目,相对来说,用计算机构造简单很多

************
现在将上面还没有人参与计算的4个文件重新划分成24个文件,放入下面的附件中
以后的计算我们采用这些新的附件,这样就可以让更加多的人可以同时计算了
nid1.tar.gz (314.25 KB, 下载次数: 5)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-1 09:41:07 | 显示全部楼层
问题一自由度太高了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-1 14:12:49 | 显示全部楼层
问题二,得到23个的解
  1. 0:  ABCD
  2. 1:  AEFG
  3. 2:  AHIJ
  4. 3:  AKLM
  5. 4:  ANOP
  6. 5:  AQRS
  7. 6:  BEHK
  8. 7:  BFIL
  9. 8:  BGJM
  10. 9:  BNQT
  11. 10:  CEIM
  12. 11:  CFHN
  13. 12:  CGKO
  14. 13:  CJLP
  15. 14:  DEJN
  16. 15:  DFKP
  17. 16:  DGHL
  18. 17:  DIOQ
  19. 18:  DMRT
  20. 19:  ELOR
  21. 20:  EPST
  22. 21:  FJOS
  23. 22:  GINR
  24. 23:  HMPQ
复制代码
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. #define max 256
  5. char Result[max][5];
  6. char CH[21] = "ABCDEFGHIJKLMNOPQRST";
  7. char TEMP[5];
  8. int m = 0;

  9. void init(void)
  10. {
  11.   int i;
  12.   for (i = 0; i < max; i ++)
  13.     Result[i][5] = '\0';
  14.   TEMP[5] = '\0';
  15. }

  16. void Circle(int level, int position)
  17. {
  18.   int i, j, k, l;
  19.   int bool;
  20.   int sum;
  21.   char c;
  22.   if (level == 4)
  23.   {
  24.     printf("%d:  ", m);
  25.     for (i = 0; i < 4; i ++)
  26.     {
  27.       Result[m][i] = TEMP[i];
  28.       printf("%c", TEMP[i]);
  29.     }
  30.     m ++;
  31.     printf("\n");
  32.   }
  33.   else
  34.   {
  35.     if (position < 20)
  36.     for (i = position; i < 20; i ++)
  37.     {
  38.       TEMP[level] = CH[i];
  39.       bool = 1;
  40.       if (level > 0)
  41.         for (l = 0; l < level; l ++)
  42.           if (bool == 1)
  43.             if (TEMP[l] == TEMP[level])            
  44.               bool = 0;
  45.       if (bool == 1)
  46.       {
  47.         if (m > 0)
  48.         {
  49.           bool = 1;
  50.           for (j = 0; j < m; j ++)
  51.             if (bool == 1)
  52.             {
  53.               sum = 0;
  54.               for (l = 0; l <= level; l ++)
  55.                 if (strchr(Result[j], TEMP[l]) != NULL)
  56.                  sum ++;
  57.               if (sum > 1)
  58.                 bool = 0;
  59.             }
  60.           if (bool == 1)
  61.             Circle(level + 1, position + 1);                       
  62.         }
  63.         else
  64.           Circle(level + 1, position + 1);
  65.       }
  66.     }
  67.   }
  68. }

  69. int main(void)
  70. {
  71.   int i, j, k, l, m, n;
  72.   char c;
  73.   int bool;
  74.   init();
  75.   Circle(0, 0);                                                       
  76. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-1 20:26:37 | 显示全部楼层
数学吧有个叫“没——问题”的给出过x=24的解

这个问题是他和我说的,当时没在意,现在怎么也联系不上他了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-1 21:39:11 | 显示全部楼层
唉,没——问题发给我的那封邮件找不到了
他当时详细的说了这两个问题:
给出了n=1到20时x值得一个列表,并说这是植树(4棵每行)问题的上界

所以我才怀疑这两个问题是等价的
还有一些其他的结论,我想不起来了,邮件应该没删,我再去找囧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-1 21:47:09 | 显示全部楼层
当时他的邮件附件里有个程序,运行之后就一个命令行窗口,什么也不显示,而且电脑风扇狂响,我还以为是病毒,赶紧强行关闭了

结果好几天后在根目录下发现一个1M大的文本文件.....里面全是问题二x=24的解囧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-1 22:19:23 | 显示全部楼层
得到x = 23的就一闪就输出了阿

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

所以有多少不等价置换,似乎就存在多少解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-3-19 10:23 , Processed in 0.061849 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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