一维空间中的吃豆子问题

mathe

听说$19#$的策略会越过一个豆子吃另外一个豆子，立马打个补丁重新运行。 目前已运行$4$小时，结果为： $p=0.47\pm0.03$ $t=0.219102\pm0.000004$ 其中$p$是$1/2$的权重，$t$是吃一个豆的平均时长。 KeyTo9_Fans 发表于 2013-3-11 16:40

p就是代码中的w?我算出来在0.7左右最优

mathe

49# KeyTo9_Fans 这是不是 意味着zgg的就是终极答案了？ wayne 发表于 2013-3-11 17:06

显然不是

mathe

....最后，按照mathe提出的说法，w总去吃最近的豆，这就是最优策略。 ... zgg___ 发表于 2013-3-11 12:20

这个策略应该是不对的。

KeyTo9_Fans

wayne在$12#$中提到： $11#$的$Sco re$函数里面有个$1/2$，不是很和谐。 于是把$1/2$改成参数$a$，重新做实验。 结果$a=0.523\pm0.005$时，吃豆最快，期望时长为$0.2194662\pm0.0000005$。 但还是比zgg____的策略慢。

KeyTo9_Fans

修改zgg____的策略， 令$g(x_1,x_2)=\frac{x_1+x_2+1/2*p*|x_1-x_2|}{2+p*|x_1-x_2|}$， 可以吃得更快。 结果是： $p=1.753\pm0.005$ $t=0.2189915\pm0.0000005$

mathe

修改zgg____的策略， 令$g(x_1,x_2)=\frac{x_1+x_2+1/2*p*|x_1-x_2|}{2+p*|x_1-x_2|}$， 可以吃得更快。 结果是： $p=1.75\pm0.03$ $t=0.218990\pm0.000004$ KeyTo9_Fans 发表于 2013-3-12 17:06

你模拟多少次，在Windows还是Linux?需要注意，Windows上伪随机数周期比较小

shshsh_0510

好久没来，凑凑热闹 题目很有意思，提一点想法。前面结果很多，不知是否已被各位提到或讨论过了。 我们设两个点分为$x$,$y$ , wayne的位置为$w$, 1. 上来先考虑最直接的策略，称之为M1: 向两个点中最近的一个走,其下一步步长期望为 $f0(x,y,w)=min(|w-x|,|w-y|)$ 2.现在固定$x$,希望研究当$y$随机出现时，下一步的长度期望 $g_{1}(x,w)=\int{f0(x,y,w)}$ 展开一下，设$d1=xd3? {d1*d2+d3*d3+(d2-d3)*(d2+d3)/2}:{d1*d2+d2*d2+(d3-d2)*(d2+d3)/2}$ 有了$g1$，就可以考虑更深一步的策略M2了，只需比较两步的期望之和 对于$x$,$y$,$w$ 策略 M1的下一步期望为 $f1(x,y,w)=min(|w-x|+g1(y,w),|w-y|+g1(x,w))$ 3.继续可以类似考虑3步最优策略M3,只是式子复杂只能用数值解了 这个问题动力系统的味道很浓，也许不同的起始位置会有不同的结果呢

KeyTo9_Fans

列一下之前的结果： 策略 结果 $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)$ $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)=(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)$ 有空再评价一下楼上的策略，看看是否把我们打败了。

mathe

听说$19#$的策略会越过一个豆子吃另外一个豆子，立马打个补丁重新运行。 目前已运行$24$小时，结果为： $p=0.48\pm0.01$ $t=0.2191032\pm0.0000005$ 其中$p$是$1/2$的权重，$t$是吃一个豆的平均时长。 KeyTo9_Fans 发表于 2013-3-11 16:40

我试着用硬件随机数运行10^10,产生结果在0.21904左右，对于p在0.47~0.52之间数都在这个值

KeyTo9_Fans

继续修改zgg____的策略， 令$g(x_1,x_2)=\frac{x_1+x_2+1/2*p*|x_1-x_2|^q}{2+p*|x_1-x_2|^q}$， 可以吃得更快。 结果是： $p=1.28\pm0.03$ $q=0.72\pm0.02$ $t=0.2189685\pm0.0000005$ 与之前的结果对比，可以看到我们又一次刷新了记录： 策略 结果 $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)$ $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)=(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)$