一维空间中的吃豆子问题

无心人

提供几个策略：
假设当前处在位置$x$，豆子在两边各有$y_1$, $y_2$个，相对密度分别是$y_1/x$, $y_2/(1-x)$
当前位置分割区间为2部分，相对有2个可选择移动方向
假设当前吃完一个豆子，下个豆子出现的时候总是早于wayne的思考的开始
假设wayne思考时间为0，
假设初始wayne处于0.5位置，且假设初始豆子先于wayne出现

策略1：总向当前豆子数最多的方向移动，如果相等，则向距离边界最短的方向移动，如果距离两边界也相等，则向密度最大方向移动，如果连密度都相等，则保持当前移动方向不变。。。
策略2：总向当前豆子密度最大的方向移动，如果密度相等，则向距离边界最短的方向移动，如果距离两边界也相等，则豆子最多方向移动，如果连豆子数都相等，则保持当前移动方向不变。
策略3：先右，或者先左，直到某方向没有豆子再转向，转向之后，即使身后出现新豆子也不回退
策略4：先右直到边界再转向，或者先左直到边界再转向
策略5：先吃左边然后马上转向右边，或者先吃右边然后马上转向左边

KeyTo9_Fans

楼上的策略在豆子数$k$比较大的时候用。

我现在还在研究$k=2$的策略。

修改$19#$的代码，使其运行时间为$12$小时，

得最佳权重$p=0.45\pm 0.02$，吃$1$个豆的期望时长是$0.219157\pm 0.000002$。

#####

运行时间$48$小时，

得最佳权重$p=0.45\pm 0.01$，吃$1$个豆的期望时长是$0.219156\pm 0.000001$。

mathe

k=2时设最优策略是g(a,b),也就是在豆子位置为$x_1<x_2$，如果$w<g(x_1,x_2)$,选择$x_1$位置的豆子，不然另外一个豆子。那么设稳定时豆子和wayne位置的密度分布函数为$p(x_1,x_2,w)$
记$K(a,b)=\int_0^{g(a,b)} p(a,b,w)dw, F(a,b)=\int_{g(a,b)}^1 p(a,b,w)dw$
对于$w<a<b$,必然有$p(a,b,w)=K(w,b)+F(w,a)$,同样计算$a<w<b$和$a<b<w$情况都是两个函数和的形式。
然后再次代入K,F的定义得出它们的积分表达式，这样就可以变成一个两个变量的积分等式问题，如果用计算机计算，就可以比原问题少一个维数，从而大大降低计算量

zgg___

当k=2时，可以看到两个有趣的点：
第一、就是11层的Fans说的，当w（wayne的简称）距离两个豆子差不多远的时候，应该去吃离中心远的那个豆子。
第二、在w刚刚吃完一个豆子而新豆子还没有出现的那一瞬间（此时0到1之间只有w和一个豆子），假设fw(x)表示此时w分布密度函数，（简称w的分布，fw是x从0到1的函数，随着w吃了好多豆子，fw将稳定下来。）假设f(x)表示此时剩下的豆子的分布（呵呵，已经开始简称了）。那么，不管w吃豆子的策略是什么，w总是均匀分布的，即fw(x)=1。

zgg___

对k=2时情况的计算有了一点进展，呵呵。
假定函数fw是w吃完豆后的分布，f是w没吃的那个豆的分布，ft是新出的豆的分布（题目中ft=1），g是判据。当w刚吃完后，用w表示他的位置，用t表示剩下豆的位置，用x表示新出豆的位置，那么fw(c)是怎样的呢？w吃完豆后要落在c点，有两种可能性，一种是x恰好落在c并且w的位置满足吃x的条件，另一种是t恰好落在c并且w的位置满足吃t的条件。对于第一种可能，又有两种情况，一是x<t且w<g(x,t,p)，另一是x>t且w>g(x,t,p)。对于第一种情况，有图中式1，剩下的三种同理，并且用字母x替换字母c，有图中式2，再同理可以计算f，有图中式3。把2式和3式相加，就可以得到fw=1了。
将fw=1代入2式，并且对x求2次导数，就可以得到微分方程了，如果限定g[x,t]=(x+t+p/2)/(p+2)，那么方程为图中式4（用3式也是一样的）。这个方程是可解的，可以得到式5的结果（注：5式恰好是6式的二阶导数）。然后将5式f的结果代入7式就可以求出预期的吃豆时长了。7式只是依赖于p，当p为特殊值时是有符号解的，例如p=0时（w总去吃最近的豆），得到8式(0.218501)的结果，对7式进行数值计算，可以得到如下图的结果。呵呵。

wayne

25# zgg___
哇，it's amazing ！

mathe

应该有问题，多个变量是相关的，需要使用联合分布才能有正确的结果

wayne

27# mathe
至少得出较优的答案了

KeyTo9_Fans

$25#$zgg___的进展太棒了！

不仅对mathe的想法进行了实现，

而且得到了一个很棒的计算结果。

可是我暂时不敢给$25#$这张贴子加分，

因为$25#$的结果领先$22#$的结果太多了，让我不敢相信。

等我有空了验证一下。

如果计算正确，我准备$5$种积分都给$+12$分。

zgg___

Fans在29层提到22层的结果和试验结果相差大，我认同这个问题，因此，我的计算中应该是存在问题的，呵呵，估计Fans的奖励是得不到了。

1. g=(x+t+p/2)/(p+2);
   
2. f=-((1+p)^2(1+p+6t-6t^2))^(1/3)/4;
   
3. s=Integrate[Integrate[x-w,{w,0,x}]+Integrate[w-t,{w,t,1}]+Integrate[w-x,{w,x,g}]+Integrate[t-w,{w,g,t}],{x,0,t}]+Integrate[Integrate[t-w,{w,0,t}]+Integrate[w-x,{w,x,1}]+Integrate[w-t,{w,t,g}]+Integrate[x-w,{w,g,x}],{x,t,1}];
   
4. f0=D[f,{t,2}];f1=Integrate[f0 s,t];f2=(f1/.t->1)-(f1/.t->0);
   
5. FindMinimum[f2,{p,0}]
   
6. fs=Table[{p,NIntegrate[f0 If[x<t&&w<g||x>t&&w>g,Abs[w-x],Abs[w-t]],{x,0,1},{t,0,1},{w,0,1}]},{p,0,1,0.01}];
   
7. Show[ListPlot[fs],Plot[f2,{p,0,1}]]

复制代码

代码如上，改写了22层的第7式，这样就可以求出期望吃豆时长（f2）和权重p的表达式了，结果是{0.217726,{p->0.276102}}，发现和昨天及试验的结果都有差异，不知道什么环节出了问题，呵呵。