毒酒问题(加强版)

shshsh_0510

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

mathe

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

1. 
   
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. }
    
30. 
    
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. }
    
40. 
    
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. }
    
70. 
    
71. 
    
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函数,让程序运行的快一些:

1. 
   
2. 
   
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, 下载次数: 206)

2009-6-8 22:15 上传

点击文件名下载附件

shshsh_0510

39# mathe


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