警察和小偷

倪举鹏

谁用计算机仿真一下，我觉得能够抓住

mathe

风云剑 发表于 2021-4-15 17:36
如果警察只能在圆周上，小偷一直贴近圆周内缘跑，似乎总是能找到机会逃脱。
小偷比警察快，那么甩掉的警察 ...

关键是小偷可以故意让两个（甚至多个）警察充分接近以后，快速平移，利用警察速度不如小偷的特性，打破警察们和小偷距离相同的性质，然后再前进

uk702

倪举鹏 发表于 2021-4-16 09:05
谁用计算机仿真一下，我觉得能够抓住

抛砖引玉：写了一段 c 的代码，可能有 bug，初步测试似表明小偷没被抓住的话，通常在100多步内跑出包围圈（至少100步，至多估计是142步）。
请大家检查。

参考 #7 的图，假设小偷位于原点(0,0)，6个警察分别占据弧AC的 6 个等分位置：
1）将单位时间分成 100 片;
2) 在每一个时间片内，小偷可以做 3 种操作之一：向上跑（OC的方向），向左跑（OA的方向），45°左上斜向跑，每次跑上0.01个单位长度。
3）警察比较笨，每次他总是设法跑向弧线中离小偷最近的那个点（候选位置是不动，顺时针全速，顺时针半速，逆时针全速，逆时针半速 5 个点之一），警察每次最多只能走 (1/1.1)*(2/Pi) * 0.01 个弧度

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <time.h>
   
4. #include <math.h>
   
5. 
   
6. #define N 5       // 警察的数目
   
7. #define Pi 3.14159265358979
   
8. #define part (1.0/100)  // 小偷每步的长度
   
9. #define halfsqrt2 (1.4142135623730950488016887/2.0)
   
10. 
    
11. char traces[1024*1024];
    
12. int main() {
    
13. 
    
14.   // 初始化随机种子
    
15.   srand((unsigned)time(NULL));
    
16. 
    
17.   int num = 0, catch = 0;
    
18.   while(1) {
    
19.     double p[2];    // 小偷的坐标
    
20.     double a[N+1];    // 警察的坐标（弧度，0=0，1=Pi/2）
    
21. 
    
22.     p[0] = 0.0; p[1] = 0.0;
    
23.     for(int k = 0; k <= N; ++k) {
    
24.       a[k] = ((double) k) / N;
    
25.     }
    
26. 
    
27.     ++num;
    
28. 
    
29.     int step = 0;
    
30.     while(1) {
    
31.       // 计算每个警察和小偷的距离
    
32.       for (int k=0; k <= N; ++k) {
    
33.         double d = (sin(a[k]*Pi/2)-p[0])*(sin(a[k]*Pi/2)-p[0]) + (cos(a[k]*Pi/2)-p[1])*(cos(a[k]*Pi/2)-p[1]);
    
34.         printf("step = %d, 警察[%d] = (%.7f, %.7f), 小偷 = (%.7f, %.7f), 距离 = %.7f \n", step, k, sin(a[k]*Pi/2), cos(a[k]*Pi/2), p[0], p[1], sqrt(d));
    
35. 
    
36.         if (d < (part/1.1) * (part/1.1)) {
    
37.           ++catch;
    
38.           printf("num = %d, catch thief on step %d, percent = %.7f\n", num, step, ((double) catch)/num);
    
39. 
    
40.          // for (int t=0; t<step; ++t) { printf("%d ", traces[t]); if (t % 10 == 1) printf("\n"); }
    
41.          // printf("\n");
    
42.          goto _next;
    
43.         }
    
44.       }
    
45. 
    
46.       // 小偷跑一步
    
47.       char di = rand() % 3;
    
48.       traces[step] = di;
    
49. 
    
50.       // 递增步数
    
51.       ++step;
    
52. 
    
53.       switch (di) {
    
54.       case 0: p[0] += part; break;
    
55.       case 1: p[1] += part; break;
    
56.       case 2: p[0] += part*halfsqrt2; p[1] += part*halfsqrt2;break;
    
57.       }
    
58. 
    
59.       // 检查小偷是否跑出包围圈
    
60.       if (p[0] * p[0] + p[1]*p[1] > 1.0) {
    
61.           printf("num = %d, thief run away on step %d, percent = %.7f\n", num, step, 1.0 - ((double) catch)/num);
    
62.           for (int t=0; t<step; ++t) { printf("%d ", traces[t]); if (t % 10 == 9) printf("\n"); }
    
63.           printf("\n");
    
64.           //goto _next;
    
65.           exit(0);
    
66.       }
    
67. 
    
68.       // 每个警察都跑一步，每一个step，警察最多只能走 (1/1.1)*(2/Pi) * part 个弧度
    
69.       // 警察总是跑向离小偷最近的那个点（为简单起见，只考虑不动，顺时针全速，顺时针半速，逆时针全速，逆时针半速 5 个点）
    
70.       {
    
71.         for (int k=0; k <= N; ++k) {
    
72.           double dist = 100.0;
    
73. 
    
74.           int select = -2;
    
75.           for (int t=-2; t<=2; ++t) {
    
76.             double x = a[k] + (1.0/1.1)*(2.0/Pi) * part * (t/2.0);
    
77.             double d = (sin(x*Pi/2)-p[0])*(sin(x*Pi/2)-p[0]) + (cos(x*Pi/2)-p[1])*(cos(x*Pi/2)-p[1]);
    
78.             if (d < dist) {
    
79.               dist = d;
    
80.               select = t;
    
81.             }
    
82.           }
    
83. 
    
84.           // 更新警察的位置
    
85.           a[k] = a[k] + (1.0/1.1)*(2.0/Pi) * part * (select/2.0);
    
86.         }
    
87. 
    
88.         // 如果警察扎堆，则强制要求一个跑动的距离
    
89.         // for (int t = 0; t < N/2; ++t)
    
90.         //   if ((a[N/2]-a[t]) < t) a[t] = a[N/2]-((double) t/N);
    
91.         // for (int t = N/2+1; t < N; ++t)
    
92.         //   if ((a[t]-a[N/2]) < t) a[t] = a[N/2]+(t-N/2);
    
93.       }
    
94.     }
    
95. 
    
96. _next:
    
97.     //break;
    
98.     ;
    
99.   }
    
100. 
     
101.   return 0;
     
102. }

复制代码

mathe

这种有限分辨率情况只要警察充分多总是可以堵住小偷的。
假设在一个由全等正三角形构成的网络中，小偷在网络中心，初始若干个警察较均匀分布在一个以小偷为中心的圆周上并且均匀分成红黑两组，双方只能沿着小正三角形的边每次正好移动一条边长的长度。
双方可以以对弈的形式移动，每轮小偷可以移动一步（但是不可以移动到警察占用的位置），警察需要红黑两组轮流移动，如果警察移动到小偷的位置就代表逮住小偷了，警察可以自由选择初始在圆周上的分布位置。
这样就可以模拟出一个小偷移动能力是警察两倍的模型了。
很显然，如果警察多到完全遍布这个圆周，那么小偷是肯定无法逃离的，但是如果警察数目不够多，就可以被小偷逃离了。
比如圆周半径为1时，两个警察（一红一黑）是不够的，但是三个警察（两红一黑）就够了。但是半径为2时，三个警察应该就不够了。
如果我们能够得出半径充分大时，需要的警察数目也是无限增长的，也可以说明充分高分辨率时，任意多个警察也肯定是逮不住小偷的