[每月新项目]PCP@home试用报告

fwjmath

本文参与了每月新项目计划。

PCP@home是一个关于算法的项目。严格来说这并不能算是一个项目，只能说是让每个人都有机会去找找一个有趣问题的解。这个项目研究的是Post's一致问题。这个问题的大意就是说，你有两个表，分别是一个英文字母代替一段二进制数字，求最短的英文字串，使两个表翻译出来的二进制一样。当然，问题并没有看起来那么简单，这可是个NP问题。这个项目的目的是找到在一定条件约束之下，不同的表求出来的这种字符串最长的是多少。

下载和参与
这个项目有多个平台下的程序，都在 Contribute 页中，做得最烂的是 Windows 的，会有内存泄露。还要自己根据自己想计算的东西自己写批处理程序，计算结果还需要用户去自己查看上报，非常麻烦。对于不同目标，建议的批处理如下：
pcpsieve 4 4 40000 2000 >result.txt
这才能将结果储存到文件当中，否则在屏幕上是看不及的。后两个数字的设置主要是控制程序的运算，你也可以自己试一下别的设置。

总结
这是个有趣的问题，可惜程序写得太烂，不便于用户。建议初级与中级用户参与别的组合数学的项目，如 SZDG 或者 Distributed.net 的 OGR-25。高级用户可以自己编写程序计算。

以下是程序的一些结果：

1. 
   
2. PcpSieve 0.05 - (c) 2000, 2001 Heiko Stamer <[email]stamer@informatik.uni-leipzig.de[/email]>
   
3. ((1010,1101),(1,1000),(1,011),(10,0110))
   
4.        (  0 -3 -2 -2 )
   
5. diff = ( +1 -3 -1 -1 )
   
6.        ( -1  0 -1 -1 )
   
7. l_diff WRONG - TRIVIAL
   
8. ((0110,0110),(0110,0),(1,01),(1111,1001))
   
9.        (  0 +3 -1  0 )
   
10. diff = (  0 +1 -1 -2 )
    
11.        (  0 +2  0 +2 )
    
12. s1_diff WRONG - TRIVIAL
    
13. ((0100,1101),(0,0),(10,1),(0,1))
    
14.        (  0  0 +1  0 )
    
15. diff = ( +2  0 +1 +1 )
    
16.        ( -2  0  0 -1 )
    
17. l_diff WRONG - TRIVIAL
    
18. ((1110,101),(0010,100),(01,1001),(001,11))
    
19.        ( +1 +1 -2 +1 )
    
20. diff = (  0 +1 -1 +2 )
    
21.        ( +1  0 -1 -1 )
    
22. LEA: A = 2
    
23. A0 = 0 A1 = 1
    
24. A0 = 1 A1 = 0
    
25. A0 = 2 A1 = -1
    
26. LEA: E[i] = -1 1 3
    
27. NO SOLUTION
    
28. ((1000,0),(0000,000),(1000,010),(111,110))
    
29.        ( +3 +1 +1  0 )
    
30. diff = ( +2 +1 +1 -1 )
    
31.        ( +1  0  0 +1 )
    
32. l_diff WRONG - TRIVIAL
    
33. ((1101,110),(1,100),(000,0100),(011,0))
    
34.        ( +1 -2 -1 +2 )
    
35. diff = (  0 -2  0  0 )
    
36.        ( +1  0 -1 +2 )
    
37. s0_diff WRONG - TRIVIAL
    
38. ((0101,00),(01,0100),(0001,0100),(110,001))
    
39.        ( +2 -2  0  0 )
    
40. diff = (  0 -2  0 -1 )
    
41.        ( +2  0  0 +1 )
    
42. s0_diff WRONG - TRIVIAL
    
43. ((0001,101),(11,0001),(111,10),(100,0))
    
44.        ( +1 -2 +1 +2 )
    
45. diff = ( +2 -3 -1 +1 )
    
46.        ( -1 +1 +2 +1 )
    
47. LEA: A = 0
    
48. A0 = 1.5 A1 = 1
    
49. A0 = 0.5 A1 = 2
    
50. A0 = -0.5 A1 = 1
    
51. LEA: E[i] = 0.5 -1.5 -1.5
    
52. o = 111 not in u-language
    
53. TRIVIAL
    
54. ((1110,11),(0,0),(000,0011),(01,1101))
    
55.        ( +2  0 -1 -2 )
    
56. diff = ( +1  0 +1  0 )
    
57.        ( +1  0 -2 -2 )
    
58. s0_diff WRONG - TRIVIAL
    
59. ((0101,1),(01,110),(10,00),(10,1100))
    
60.        ( +3 -1  0 -2 )
    
61. diff = ( +2  0 -1 -1 )
    
62.        ( +1 -1 +1 -1 )
    
63. LEA: A = 0
    
64. A0 = -0 A1 = 1
    
65. A0 = 0.5 A1 = -1
    
66. A0 = 0.5 A1 = 1
    
67. LEA: E[i] = -1 1.5 -0.5
    
68. o = 0101 not in u-language
    
69. TRIVIAL
    
70. ((1001,0),(110,001),(0000,0010),(0,00))
    
71.        ( +3  0  0 -1 )
    
72. diff = ( +1 -1 +1 -1 )
    
73.        ( +2 +1 -1  0 )
    
74. LEA: A = 0
    
75. A0 = 1 A1 = -0.5
    
76. A0 = -1 A1 = 0.5
    
77. A0 = 1 A1 = -0
    
78. LEA: E[i] = 1.5 -1.5 1
    
79. o = 110 not in u-language
    
80. TRIVIAL

复制代码

[ Last edited by fwjmath on 2006-12-15 at 18:05 ]

Real

pcpsieve 4 4 40000 2000这个测试数据是什么意思？

fwjmath

原帖由 Real 于 2007-2-20 22:48 发表
pcpsieve 4 4 40000 2000这个测试数据是什么意思？

Our program generates random PCPs of a specified class and try to solve them. There are several commandline parameters: pcp_size stands for the size of a problem class. pcp_width is the length limitation of the words. sieve_size and sieve_length bound the solution algorithm. sieve_size = 10000 corresponds approximatly to 10 MB main memory and with sieve_length = 500 we reach a maximum depth of 500 in the bread-first search. You can increment this values if your computer system has sufficient (real) main memory (RAM). In such a case the program may find longer candidates, but consumes more CPU time and RAM space.

也就是说，程序随机生成字母表，然后计算最短匹配二进制串。第一个参数代表字母的个数，第二个参数代表每个字母最多代表几个二进制位，第三个就是在广度优先搜索里边最多出现多少结点，第四个就是广度优先搜索的深度。后两个参数可以自己调节，越大的话占用的内存就越多。

Real

原帖由 fwjmath 于 2007-2-21 08:25 发表

Our program generates random PCPs of a specified class and try to solve them. There are several commandline parameters: pcp_size stands for the size of a problem class. pcp_width is the length  ...

哦，了解！


那么输出数据又是什么意思？跟官方网站给的例子有什么联系？

fwjmath

输出数据里边没有一个是有有效解的...
这个输出数据也实在太不好懂~~~我曾经钻研过很久也只能钻研出一些来~~~不算十分的了解~~~但有一个很显然能看出来的就是：有TRIVIAL字样的就是没有有效解的~~~

Real

哦，昨天运行了一下PcpSieve，才运行了20分钟，就用了我100多mb的内存，输出数据有300多k