一维空间中的吃豆子问题

mathe

给定g计算p,可以采用正交函数系来逼近。 为此我们可以假设g用折线逼近，于是h也可以用折线表示。 由于计算区域在三角形I={(x,y)| 0

mathe

假设我们只选择了n个正交函数（多项式）来近似整个函数空间，现在我们要计算$F_g$在这个近似的n维空间中的矩阵表示（n越大精度越高） 我们首先计算$h_i=F_g(u_i)$,（直接计算$F_g(v_i)$也可，但是通常前面的更加容易. 当然由于g分段所以$h_i$是分段多项式。 此后我们可以计算$b_{ij}={(h_i,v_j)}/{(v_j,v_j)}$, 于是$h_i~=\sum b_{ij}v_j$也就是$h=Bv$，然后再根据$u,v$之间的变换公式$v=Au$，我们可以得出 $F_g(u)=h~=BA^-1u=Cu$,于是C的最大特征根会越等于1，接下去，我们就是求C最大特征值对应的特征向量，可以通过迭代法近似得出，比如先任意选择$s_0$,然后$s_n=C^ns_0$,然后将$s_n$归一化（为了防止溢出，可以先选择较小的n,然后计算$r={|s_n|}/{|s_0|}$,然后用${C^n}/r$替换$C$,然后可以在继续选择m,再次迭代$C^ms_n$，多次以后会得出一个高精度的特征向量s 然后设s各个分量为$s_i$,那么$\sum s_iu_i$就是所求的p的近似值，这是p的最佳多项式逼近 而得出p的最佳多项式逼近后，最后一步由于函数h也是分段线性函数，计算平均步长就非常容易了，分段积分累加即可

mathe

最后的问题就是如何表达函数$g(a,b),0<=a<=b<=1$ 我们已经知道的是$g(a,a)=a,g(1/2-t,1/2+t)=1/2,g(1-b,1-a)=1-g(a,b)$ 所以只需要确定g在三角形$0<=a<=b<=1,a+b<=1$中的内容。将它划分成若干个和它相似的小三角形，对于那么未知的小三角形顶点的值可以作为待定系数（不同选择确定了不同的g). 而确定所有顶点的值后，对于某个三角形ABC内部D点,$g(D)={g(A)*S(DBC)+g(B)*S(DCA)+g(C)*S(DAB)}/{S(ABC)}$,其中$S(XYZ)$代表三角形XYZ的面积。

dianyancao

使用如下策略得到的结果 p=0.38 t=0.218766 v1 = Abs[w - rightx] + p*Abs[leftx - xforecast]; v2 = Abs[w - leftx] + p*Abs[rightx - xforecast]; rightx位于w右边，leftx位于w左边，xforecast=1/2 根据v1和v2的大小关系，确定吃右边的豆子还是左边的豆子 mathematica测试代码：

1. Clear["Global`*"];
2. testcount = 10;
3. mcount = 100;
4. vlist = Table[0, {i, 1, mcount + 1}];
6. For[testindex = 1, testindex <= testcount, testindex++,
7. Print[""];
8. For[p = 0, p <= 1, p += 1/mcount,
9. n = 10^5;
10. k = 2;
11. v = s/n;
13. s = 0;
14. w = Random[];
15. x = Table[Random[], {i, 1, k}];
16. xforecast = 1/2;
17. v1 = 0;
18. v2 = 0;
19. leftx = 0;
20. rightx = 0;
22. sumx = Sum[x[[i]], {i, 1, k}];
24. For[i = 1, i <= n, i++,
25. rightx = Max[x];
26. leftx = Min[x];
27. x[[1]] = leftx;
28. x[[2]] = rightx;
30. If[w > rightx,
31. s = s + Abs[w - rightx]; w = rightx; x[[2]] = Random[];
32. sumx = sumx + x[[2]];,
33. If[w < leftx,
34. s = s + Abs[w - leftx]; w = leftx; x[[1]] = Random[];
35. sumx = sumx + x[[1]];,
37. v1 = Abs[w - rightx] + p*Abs[leftx - xforecast];
38. v2 = Abs[w - leftx] + p*Abs[rightx - xforecast];
39. If[v1 < v2,
40. s = s + Abs[w - rightx]; w = rightx; x[[2]] = Random[];
41. sumx = sumx + x[[2]],
42. s = s + Abs[w - leftx]; w = leftx; x[[1]] = Random[];
43. sumx = sumx + x[[1]]
44. ];
45. ];
46. ];
47. ];
48. Print[v];
49. vlist[[p*mcount + 1]] += v;
50. ];
51. ];
52. ListPlot[{Table[{(p - 1)/mcount, vlist[[p]]/testcount}, {p, 1,
53. mcount + 1}]}]
54. minv = Ordering[Table[vlist[[p]]/testcount, {p, 1, mcount + 1}], 1]
55. vlist[[minv]]/testcount

复制代码

KeyTo9_Fans

如果考虑误差，那么楼上的结果是 $p=0.4\pm0.1$ $t=0.2188\pm0.0004$ 由于误差较大，不能确定是否比已有的策略好。 所以我将模拟吃豆的数量增大了$10^6$倍， 于是测试结果的误差就足够小了， 于是就可以判断是否比已有的策略好了。 比较结果如下： 策略 结果 $g(x_1,x_2)=(x_1+x_2)/2$ $t=0.220408(1)$ $Sco re(x)=(|x-1/2|+a)/(|w-x|)$ $a=0.523(5),\ t=0.2194662(5)$ $Sco re(x)=|w-x'|+p*|x-1/2|$ $p=0.311(5),\ t=0.2191733(5)$ $g(x_1,x_2)=(x_1+x_2+1/2*p)/(2+p)$ $p=0.478(5),\ t=0.2191031(5)$ $g(x_1,x_2)={\max\{x_1,x_2\}}/(1+|x_1-x_2|)$ $t=0.2190061(5)$ $g(x_1,x_2)=(x_1+x_2+1/2*p*|x_1-x_2|)/(2+p*|x_1-x_2|)$ $p=1.753(5),\ t=0.2189915(5)$ $g(x_1,x_2)=(x_1+x_2+1/2*p*|x_1-x_2|^q)/(2+p*|x_1-x_2|^q)$ $p=1.28(3),\ q=0.72(2)\ t=0.2189685(5)$ 传说中的最佳策略 $t=0.21889630(1)$ 其中，第$3$个策略是楼上的策略， 比$11#$的策略好， 基本上与$19#$的策略（debug之前）持平， 但比$19#$的策略（debug之后）差。 ##### 通过某种神奇的方法， 我终于得到了最佳策略下的平均吃豆时长， 为$0.21889630(1)$， 但该策略具体是什么还不知道。 我将该结果列在了上表的最后一行， 可以看到目前已知的最好的策略的平均吃豆时长已经与最佳策略的平均吃豆时长很接近了。 ##### 于是，楼主的第$1$问终于有一个近似的答案了： 当$k=2$时，wayne吃豆子的平均速率是$4.5683732(2)$个每秒。 可是，传说中的最佳策略到底是怎样的策略呢？ 我有空会再次出马，揭开最佳策略的神秘面纱，请静候佳音

dianyancao

k=2时的最佳t有理论值了？期待证明过程呀

dianyancao

用Mathematica乱算一通，得到t的下限值 t=0.20833' 下限值和当前的t较接近，不知道计算是否正确 其中选择的每个策略都是1步内的局部最优解

1. s1 = Sum[Sum[Sum[x1 - w, {w, 0, x1}], {x2, x1 + 1, m}], {x1, 0, m}]
2. s2 = Sum[Sum[
3. Sum[w - x1, {w, x1 + 1, (x1 + 1 + x2)/2}], {x2, x1 + 1, m}], {x1,
4. 0, m}]
5. s3 = Sum[Sum[
6. Sum[x2 - w, {w, (x1 + 1 + x2)/2 + 1, x2}], {x2, x1 + 1, m}], {x1,
7. 0, m}]
8. s4 = Sum[Sum[Sum[w - x2, {w, x2 + 1, m}], {x2, x1 + 1, m}], {x1, 0, m}]
10. s5 = Sum[Sum[Sum[x2 - w, {w, 0, x2}], {x2, 0, x1}], {x1, 0, m}]
11. s6 = Sum[Sum[
12. Sum[w - x2, {w, x2 + 1, (x2 + 1 + x1)/2}], {x2, 0, x1}], {x1, 0, m}]
13. s7 = Sum[Sum[
14. Sum[x1 - w, {w, (x2 + 1 + x1)/2 + 1, x1}], {x2, 0, x1}], {x1, 0, m}]
15. s8 = Sum[Sum[Sum[w - x1, {w, x1 + 1, m}], {x2, 0, x1}], {x1, 0, m}]
17. sum1 = s1 + s2 + s3 + s4
18. sum2 = s5 + s6 + s7 + s8
19. t = Limit[(sum1 + sum2)/m/(m + 1)^3, m -> Infinity]
20. N[t]

复制代码

KeyTo9_Fans

为了展示吃$2$个豆子的最佳策略（该策略指的是$75$楼里的【传说中的最佳策略】）

我把这个问题做成了一个游戏。

下载这个附件：

best_collect.rar (698.72 KB, 下载次数: 15)

2015-6-29 17:28 上传

点击文件名下载附件

解压后运行“best_collect.exe”，就可以看到【传说中的最佳策略】了。

注意：

要把“solution.txt”和“best_collect.exe”放在同一个文件夹里，不要分开了。

#####

美中不足的是，我们只有【传说中的最佳策略】的一些离散的数据。

能否根据这些离散的数据找到函数$g(x_1,x_2)$的解析式呢？