找回密码
 欢迎注册
楼主: KeyTo9_Fans

[讨论] 一维空间中的吃豆子问题

[复制链接]
发表于 2013-3-11 17:44:27 | 显示全部楼层
听说$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左右最优
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-3-11 17:44:43 | 显示全部楼层
49# KeyTo9_Fans
这是不是 意味着zgg的就是终极答案了?
wayne 发表于 2013-3-11 17:06

显然不是
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-3-11 17:45:30 | 显示全部楼层
....最后,按照mathe提出的说法,w总去吃最近的豆,这就是最优策略。 ...
zgg___ 发表于 2013-3-11 12:20

这个策略应该是不对的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-3-11 23:46:55 | 显示全部楼层
wayne在$12#$中提到:

$11#$的$Sco re$函数里面有个$1/2$,不是很和谐。

于是把$1/2$改成参数$a$,重新做实验。

结果$a=0.523\pm0.005$时,吃豆最快,期望时长为$0.2194662\pm0.0000005$。

但还是比zgg____的策略慢。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-3-12 17:06:32 | 显示全部楼层
修改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$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-3-12 18:45:56 | 显示全部楼层
修改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上伪随机数周期比较小

评分

参与人数 1经验 +3 收起 理由
KeyTo9_Fans + 3 在Linux下,模拟$10^11$次以上

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-3-12 22:48:35 | 显示全部楼层
好久没来,凑凑热闹
题目很有意思,提一点想法。前面结果很多,不知是否已被各位提到或讨论过了。

我们设两个点分为$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=x<w?x:1-x$ ,$d2=|x-w|$ ,$d3=1-d1-d2$(即x,w把线段分为3段的长度)
于是 $g1(x,w)= d2>d3? {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,只是式子复杂只能用数值解了

这个问题动力系统的味道很浓,也许不同的起始位置会有不同的结果呢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-3-12 23:57:47 | 显示全部楼层
列一下之前的结果:

策略                                           结果
$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)$

有空再评价一下楼上的策略,看看是否把我们打败了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-3-13 17:36:07 | 显示全部楼层
听说$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之间数都在这个值
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-3-14 01:27:14 | 显示全部楼层
继续修改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)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 21:49 , Processed in 0.057454 second(s), 22 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表