毒酒问题(加强版)

shshsh_0510

不好意思，原来没注意15#已经讲解过原理了，感谢mathe的再次解说

mathe

现在写了个程序来简单搜索1000桶酒的解,看看能否找到41个囚徒的解: 不过程序运行挺慢的.

2. #include <vector>
3. #define TARGET_COUNT 1000
4. #define N 41
5. #define WEIGHT 7
6. #define MIN_DISTANCE 8
7. #define MAX_OVERLAP (WEIGHT-(MIN_DISTANCE+1)/2)
8. #define DISP_SIZE ((N+3)/4)
9. using namespace std;
10. //#define SHOW_COUNT
11. vector<long long> data;
12. void init()
13. {
14. long long u=(1LL<<MAX_OVERLAP)-1;
15. int j=(N-MAX_OVERLAP)/(WEIGHT-MAX_OVERLAP);
16. long long s=(1LL<<(WEIGHT-MAX_OVERLAP))-1;
17. int i;
18. for(i=0;i<j;i++){
19. int k=i*(WEIGHT-MAX_OVERLAP)+MAX_OVERLAP;
20. long long r=u|(s<<k);
21. data.push_back(r);
22. printf("%0*llX",DISP_SIZE,r);
23. #ifdef SHOW_COUNT
24. printf("::%d",data.size());
25. #endif
26. printf("\n");
27. }
28. fflush(stdout);
29. }
31. int bitcount(long long x)
32. {
33. int bc=0;
34. int i;
35. for(i=0;i<64;i++){
36. if(x&(1LL<<i))bc++;
37. }
38. return bc;
39. }
41. bool try_next_bit(long long r, int nb, int bc)
42. {
43. int i,j;
44. if(bc>=WEIGHT){
45. data.push_back(r);
46. printf("%0*llX",DISP_SIZE,r);
47. #ifdef SHOW_COUNT
48. printf("::%d",data.size());
49. #endif
50. printf("\n");
51. fflush(stdout);
52. return true;
53. }
54. for(i=nb;i<N;i++){
55. r|=(1LL<<i);
56. for(j=0;j<data.size();j++){
57. if(bitcount(r&data[j])>MAX_OVERLAP)
58. break;
59. }
60. if(j<data.size()){
61. r&=~(1LL<<i);
62. continue;
63. }
64. if(try_next_bit(r,i+1,bc+1))
65. return true;
66. r&=~(1LL<<i);
67. }
68. return false;
69. }
72. int _tmain(int argc, _TCHAR* argv[])
73. {
74. init();
75. while(try_next_bit(0LL,0,0));
76. printf("Total %d\n",data.size());
77. return 0;
78. }

复制代码

shshsh_0510

29#给出的是一个上界，这个问题需要下界，对于A(n,d,w)的上下界可参照 下界：http://www.research.att.com/~njas/codes/Andw/index.html 上界：http://webfiles.portal.chalmers.se/s2/research/kit/bounds/cw.html 没仔细看，不知mathe的上界对其是否有改善 另外对于1000瓶酒，感觉用Constant-weight code的方法，41就是极限了，用A(n,10,9)已经不如A(n,8,7)了，所以知道更多的A(n,d,w)也没有用了

mathe

我的bound肯定很不好.我主要是希望能够有一个用公式表示的下界,这样就可以比较可信的估计出k和n的关系是不是对数关系了.现在的结果还是不够可信

mathe

上面的程序挺慢的,所以我修改了一下main函数,让程序运行的快一些:

3. int _tmain(int argc, _TCHAR* argv[])
4. {
5. int nb=0;
6. int newnb;
7. init();
8. while(try_next_bit(0LL,nb,0)){
9. nb=firstone(data[data.size()-1]);
10. }
11. printf("Total %d\n",data.size());
12. return 0;
13. }

复制代码

其中函数firstone返回输入数据的最低为1的比特位(0~63) 现在程序对于41个囚犯,已经搜索出超过1000桶酒的方案了,不过还没有算完. 等算完了我再将数据贴出来(不知道能够搜索出多少桶酒的方案)

mathe

呵呵,结果出来了,结果也是1095,就是说同上面表格给出的结果相同,基本上花了一个小时. 附件中给出了源代码和数据 cs.tar.gz (6.08 KB, 下载次数: 8)

2009-6-8 13:29 上传

点击文件名下载附件

其中每行数据是一个41比特的数,用16进制表示表示. 每一行代表一桶酒,如果对应比特位是1,那么就说明那个囚犯需要喝那同酒. 其中每桶酒正好有7个囚犯来喝. 而最终的结果应该有14个囚犯死去.检测方法类似,只要查看每行比特位为1的囚犯是否全部死去(如果是,则这桶酒有毒,不然无毒) 所以这个方案可以用41个囚犯检测不超过1095桶酒(2桶有毒)

mathe

想了一下,shshsh_0510的拆分方法还是挺有用的.不过得到的结果应该是 $f(2x) mathe 发表于 2009-6-7 19:06

现在感觉shshsh_0510的那个结果: $f(2x)<=f(x)+2+g(x)$还是对的. 不过复杂度还是$O(log^2(x))$而不是$O(log(x))$. 其道理在于每次对2x桶酒中找两桶毒酒时,我们可以直接让两个人分别喝掉左边和右边的x桶酒. 那么如果只有一个人毒死,那么就转化为f(x)的问题.而且左边和右边死掉的情况不会同时出现.所以f(x)部分对于左边和右边的情况可以用相同的人来测试. 而这种测试会就相当于将2x写成2进制数,这些囚犯都正好喝掉某个比特位为1对应的所有的酒或某个比特位为0对应的所有的酒. 而余下比较复杂的情况是在某一层开始,左边和右边的人同时死去(对应上面的方法,相当于出现比特位为1和0对应的囚徒都死去的最高比特位h).而由这一层开始,我们只需要左边分支,对这个分支采用$g(2^h)$的方案可以得出这个分支中毒酒的位置.而对于右边的分支,在左边分支的结果确定以后,对于所有低比特位就可以直接确定了(如果对某个比特位,只有1或0对应的囚徒死去,两个分支在这个比特位相同;如果同时1和0对应的囚徒死去,两个分支在这个比特位取值相反).

mathe

然后对于每个数字,在表格中找到不小于这个数字的行号最小的格子.那么行号就是这个方法可以提供的最少的囚徒数.不过可惜我没有找到A(n,d,w)的近似公式,不然我们可以对它有更好的了解. 可以看到在同的数目k mathe 发表于 2009-6-7 18:11

发现我的这个方案中,我们总可以再加一桶酒,所有的人都不喝. 这个对比较小规模问题影响比较明显.比如9个人可以解决13桶问题

mathe

google到一篇很强的文章,对于1000,应该可以消减到31一下: v5i1r39.pdf (140.75 KB, 下载次数: 240)

2009-6-8 22:15 上传

点击文件名下载附件

shshsh_0510

39# mathe 呵呵，还是你快。 我找到erdos那个但没能超过41