12345678910... 64
返回列表 回复 发帖 免费玩斗地主,每分钟送Q币
0→∞

小试牛刀

Rank: 3Rank: 3

帖子
39 
精华
1 
积分
619 
鲜花
37 朵 
主题
5 帖 
1#
打印
tT
发表于 2008-7-31 23:38 | 只看该作者    踩窝窝   送礼物   问候Ta

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

相关搜索: 果树问题
加精理由：随着讨论的深入，其价值越发凸显了。
问题1：即20棵树问题
   参考:20颗树问题 以及英文链接Orchard Planting Problem

问题2：20个字母A-T。取出x组。
　每组4个字母
　每个字母在同一组内只能出现一次，但可以同时包含在多个组内
　所选取的x组中任意两组中至多有一个字母相同，求x的最大值
本主题由 mathe 于 2009-11-27 17:26 合并
收藏 分享 评分
回复 引用

订阅 TOP

mathe

管理员

Rank: 12Rank: 12Rank: 12

帖子
4496 
精华
26 
积分
53352 
鲜花
1111 朵 
主题
143 帖 
来自
代数数 

优秀斑竹奖活力擂主奖解题大师奖宣传大使奖原创先锋奖金点子大奖攻擂高手奖社区央行行长
2#
发表于 2008-8-1 07:58 | 只看该作者    踩窝窝   送礼物   问候Ta
应该不等价
－－－－－－－－－－－－－－－－－－－－－－－－－－－
算法简介:
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)

18to20.zip (86.95 KB)

0.54364331210052407755147385529445
回复 引用

TOP

0→∞

小试牛刀

Rank: 3Rank: 3

帖子
39 
精华
1 
积分
619 
鲜花
37 朵 
主题
5 帖 
3#
发表于 2008-8-1 08:55 | 只看该作者    踩窝窝   送礼物   问候Ta
是否可证呢
就是说对于问题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#以及随后几个回复
回复 引用

TOP

mathe

管理员

Rank: 12Rank: 12Rank: 12

帖子
4496 
精华
26 
积分
53352 
鲜花
1111 朵 
主题
143 帖 
来自
代数数 

优秀斑竹奖活力擂主奖解题大师奖宣传大使奖原创先锋奖金点子大奖攻擂高手奖社区央行行长
4#
发表于 2008-8-1 09:01 | 只看该作者    踩窝窝   送礼物   问候Ta
结论应该是否定的，至少对于第二个题目，相对来说，用计算机构造简单很多

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

另外如果再次出现网络异常，可以通过email联系我:
zhao.hui.du@gmail.com
计算表格


序号


计算人员


开始时间


结束时间


当前文件大小


进度


备注


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#

0.54364331210052407755147385529445
回复 引用

TOP

无心人

管理员

Rank: 12Rank: 12Rank: 12

帖子
6744 
精华
21 
积分
52515 
鲜花
784 朵 
主题
287 帖 

优秀斑竹奖活力擂主奖宣传大使奖原创先锋奖灌水天才奖金点子大奖攻擂高手奖
5#
发表于 2008-8-1 09:41 | 只看该作者    踩窝窝   送礼物   问候Ta
问题一自由度太高了
雅兰·水语              ｜      酷 冷
我本昆仑一幽兰   ｜  冰心玉壶藏
为图红尘修仙缘   ｜  秋水映雪妆
千年寂寞若等闲   ｜  渺渺天地间
一朝不慎堕凡间   ｜  凛凛西风狂
学习记录
回复 引用

TOP

无心人

管理员

Rank: 12Rank: 12Rank: 12

帖子
6744 
精华
21 
积分
52515 
鲜花
784 朵 
主题
287 帖 

优秀斑竹奖活力擂主奖宣传大使奖原创先锋奖灌水天才奖金点子大奖攻擂高手奖
6#
发表于 2008-8-1 14:12 | 只看该作者    踩窝窝   送礼物   问候Ta
问题二，得到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>

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

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

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

  73. int main(void)
  74. {
  75.   int i, j, k, l, m, n;
  76.   char c;
  77.   int bool;
  78.   init();
  79.   Circle(0, 0);                                                       
  80. }
复制代码
雅兰·水语              ｜      酷 冷
我本昆仑一幽兰   ｜  冰心玉壶藏
为图红尘修仙缘   ｜  秋水映雪妆
千年寂寞若等闲   ｜  渺渺天地间
一朝不慎堕凡间   ｜  凛凛西风狂
学习记录
回复 引用

TOP

0→∞

小试牛刀

Rank: 3Rank: 3

帖子
39 
精华
1 
积分
619 
鲜花
37 朵 
主题
5 帖 
7#
发表于 2008-8-1 20:26 | 只看该作者    踩窝窝   送礼物   问候Ta
数学吧有个叫“没——问题”的给出过x=24的解

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

TOP

0→∞

小试牛刀

Rank: 3Rank: 3

帖子
39 
精华
1 
积分
619 
鲜花
37 朵 
主题
5 帖 
8#
发表于 2008-8-1 21:39 | 只看该作者    踩窝窝   送礼物   问候Ta
唉，没——问题发给我的那封邮件找不到了
他当时详细的说了这两个问题：
给出了n=1到20时x值得一个列表，并说这是植树（4棵每行）问题的上界

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

TOP

0→∞

小试牛刀

Rank: 3Rank: 3

帖子
39 
精华
1 
积分
619 
鲜花
37 朵 
主题
5 帖 
9#
发表于 2008-8-1 21:47 | 只看该作者    踩窝窝   送礼物   问候Ta
当时他的邮件附件里有个程序，运行之后就一个命令行窗口，什么也不显示，而且电脑风扇狂响，我还以为是病毒，赶紧强行关闭了

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

TOP

无心人

管理员

Rank: 12Rank: 12Rank: 12

帖子
6744 
精华
21 
积分
52515 
鲜花
784 朵 
主题
287 帖 

优秀斑竹奖活力擂主奖宣传大使奖原创先锋奖灌水天才奖金点子大奖攻擂高手奖
10#
发表于 2008-8-1 22:19 | 只看该作者    踩窝窝   送礼物   问候Ta
得到x = 23的就一闪就输出了阿

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

所以有多少不等价置换，似乎就存在多少解
雅兰·水语              ｜      酷 冷
我本昆仑一幽兰   ｜  冰心玉壶藏
为图红尘修仙缘   ｜  秋水映雪妆
千年寂寞若等闲   ｜  渺渺天地间
一朝不慎堕凡间   ｜  凛凛西风狂
学习记录
回复 引用

TOP

12345678910... 64
返回列表