数学研发论坛

 找回密码
 欢迎注册
查看: 3641|回复: 26

[讨论] 机器人登山问题

[复制链接]
发表于 2014-8-12 20:59:28 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
有$n$个机器人,

每个机器人能携带的最大能量值分别是$e_1$,$e_2$,...,$e_n$,

它们每爬升$1$米所消耗的能量值分别是$c_1$,$c_2$,...,$c_n$。

初始时,所有的机器人都位于$0$米的高度。

如果某些机器人位于同一高度,它们可以无损耗地相互传递能量。

如果某个机器人的能量耗光,这个机器人可以中途停下来。

给定$n$,$e_1$,$e_2$,...,$e_n$,$c_1$,$c_2$,...,$c_n$,

求这些机器人能爬升的最大高度是多少。

例:

当$n=3$,

$e_1=0.84$,$e_2=3$,$e_3=6$,

$c_1=1$, $c_2=2$,$c_3=3$时,

能爬升的最大高度是$2.84$,方案有$3$种:

方案$1$:

$3$个机器人一起爬升,

机器人$3$的能量不断地传递给机器人$1$和$2$,

于是在高度$1$处机器人$3$的能量耗尽,机器人$3$停下,

而机器人$1$和$2$的能量还是满的。

接下来机器人$2$的能量不断地传递给机器人$1$,

于是在高度$2$处机器人$2$的能量耗尽,机器人$2$停下,

而机器人$1$的能量还是满的。

最后机器人$1$可以爬到$2.84$的高度。

方案$2$:

$3$个机器人一起爬升,

机器人$2$的能量不断地传递给机器人$1$和$3$,

于是在高度$0.5$处机器人$2$的能量耗尽,机器人$2$停下,

而机器人$1$和$3$的能量还是满的。

接下来机器人$3$的能量不断地传递给机器人$1$,

于是在高度$2$处机器人$3$的能量耗尽,机器人$3$停下,

而机器人$1$的能量还是满的。

最后机器人$1$可以爬到$2.84$的高度。

方案$3$:

$3$个机器人一起爬升,

机器人$1$的能量不断地传递给机器人$2$和$3$,

于是在高度$0.14$处机器人$1$的能量耗尽,机器人$1$停下,

而机器人$2$和$3$的能量还是满的。

接下来机器人$3$的能量不断地传递给机器人$2$,

于是在高度$1.34$处机器人$3$的能量耗尽,机器人$3$停下,

而机器人$2$的能量还是满的。

最后机器人$2$可以爬到$2.84$的高度。

#####

当$n=100$时,是否有高效的算法求出能爬升的最大高度?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-8-13 16:37:14 | 显示全部楼层
这个题目蛮有趣的。

如果这些机器人最终可达到的高度依次为 \(h_1,h_2,\dots,h_n\),
此时能量耗尽,故有 \(\sum c_i h_i = \sum e_i\)。现要求 \(\max\{h_i\}=?\)

不知楼主所举例子是否为特别精心设计的,所以最佳方案有三种。

但感觉它们都有一个共同规律:
先齐头并进,部分机器人供能直至自身能量耗尽(在该过程中,其它非僵尸机器人,能量保持充沛)。

所以,是否可用递归算法,比如说深度优先搜索(Depth-First Search, DFS)?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-8-13 17:31:06 | 显示全部楼层
这个要看数据模式。给定机器人淘汰顺序后,计算达到最高高度是很容易的。每次只要正好将能量全部传递给所有其它机器(这时其它机器能量都满),停掉这个机器人即可。
所以问题就是确定机器人淘汰顺序问题,最多有n!种。
当然如果一个机器人耗能高,携带能量能到达的高度少,那么显然要优先淘汰。
但是如果总是耗能高的机器人携带的能量更多,那么就比较难判断了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-8-13 22:36:18 | 显示全部楼层
简化为 2机器人模型,`(e_1,c_1)`与`(e_2,c_2)`

1号供能给2号方案, $h_12=e_1/(c_1+c_2)+e_2/c_2$

2号供能给1号方案, $h_21=e_2/(c_1+c_2)+e_1/c_1$

相减比较两方案,$h_12-h_21=(c_1c_2)/(c_1+c_2)(e_2/(c_2^2)-e_1/(c_1^2))$

推断优化策略为:优先保留$e/c^2$较大的机器人,牺牲$e/c^2$较小的机器人。

点评

e/c^2最小的机器人不一定是最先被牺牲的,但一定不是最后的登顶者。  发表于 2014-8-14 01:47
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-8-14 08:05:15 | 显示全部楼层
本帖最后由 zeroieme 于 2014-8-14 22:51 编辑

接着讨论`n`个机器人的情形。
假设得到最大高度的机器人排序为`1,2,\cdots,n`,编号较大的给较小的供能。
记`s_k=c_1+c_2+\cdots+c_k`,那么

$h_max=e_1/s_1+e_2/s_2+\cdots+e_(n-2)/s_(n-2)+e_(n-1)/(s_n-c_n)+e_n/s_n$

将最先停步的`(n-1)`和`n`号机器人交换一下次序,可达高度为

$h_(sec) =e_1/s_1+e_2/s_2+\cdots+e_(n-2)/s_(n-2)+e_n/(s_n-c_(n-1))+e_(n-1)/s_n$

两相比较,$\Deltah=h_max-h_(sec)=(e_(n-1)/(s_n-c_n)+e_n/s_n)-(e_n/(s_n-c_(n-1))+e_(n-1)/s_n)=(c_{n-1}c_n)/(s_n(s_n-c_{n-1})(s_n-c_n))[e_{n-1}(s_n/c_{n-1}-1)-e_n(s_n/c_n-1)]$

由`\Delta h\ge0`得$\e_n(s_n/c_n-1)\le e_{n-1}(s_n/c_{n-1}-1)$  感谢某位管理员的整理,这里2个都是

同理, 当`n`号机器人竭尽能量停步后,在剩下的`(n-1)`个机器人中可得$ e_{n-1}(s_{n-1}/c_{n-1}-1)\le e_{n-2}(s_{n-1}/c_{n-2}-1)$

由此我们得到了一种最优排序的算法:计算$e_k(s_n/c_k-1)$,取最小者先淘汰,然后在剩下的机器人中重复这种策略,直到全部排好序。

点评

这只是说明,e(s/c-1)最大的不会首先被淘汰。  发表于 2014-8-14 23:04
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-8-14 08:29:42 | 显示全部楼层
本帖最后由 zeroieme 于 2014-8-14 23:12 编辑

验算一下。以楼主的`(0.84,1), (3,2), (6,3)`为例.

记$v_(n,k)=e_k(s_n/c_k-1)$

1、$s_3=1+2+3=6,v_(3,1)=0.84(6/1-1)=4.2, v_(3,2)=3(6/2-1)=6, v_(3,3)=6(6/3-1)=6$,所以可以首先淘汰`1`号机器人。
2、$s_2=2+3=5,v_(2,2)=3(5/2-1)=4.5,v_(2,3)=6(5/3-1)=4$,所以次淘汰`3`号机器人,让`2`号机器人登顶。

只得到1种方案?


该 方案假设了n-2个机器人队列已经最优化,只比较了末2个机器人的差异。
分析出即将淘汰 n-1号,n号2个时, 先淘汰n号比先淘汰n-1号优胜一些。
当前队列未优化时,不能确保存在第i号、j号机器人组合放队尾会比 i、n组合或者 j、n组合更优。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-8-15 13:07:11 | 显示全部楼层
4#和5#给出了2个不需要组合计算的筛选条件,对 n! 个全排列,最多可以筛掉其中的3/4,剩下n!/4.

记$u_k=e_k/c_k^2,v_k=e_k(s_n/c_k-1)$,当`u_k`各不相等,`v_k`亦各不相等时,对于排列
`1,2,(3,..., n-2), n-1, n`,
保持括号中的部分不动,头尾变化的有3个相伴排列:
`1,2,(3,..., n-2), n, n-1`
`2,1,(3,..., n-2), n-1, n`
`2,1,(3,..., n-2), n,n-1`
这四个排列中, 只有满足${u_1>u_2,v_(n-1)>v_n}$(这里的标号是位置号)的高度最大,其它3个可以筛掉。
全部排列可以这样`4`个一组地分成`n!/4`组,每组中可以确定 1 个满足筛选条件的高度最大者,故可缩减至`n!/4`个.

5#的最优算法,得到不一定是最值。

点评

@zeroieme 能筛这么多?精确么,n!/2^(n-2)不一定是整数啊。我漏哪些了?  发表于 2014-8-15 18:23
可缩减至n!/2^(n-2),刚才怎么数多了  发表于 2014-8-15 17:08
可缩减至n!/2^(n-1)  发表于 2014-8-15 17:02
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-8-15 16:59:41 | 显示全部楼层
5#给出的是最优解中相邻两个机器人必要条件,4#是当 m=2时5#的特例。
2≤m≤n,每对 m-1号与m号机器,必须$\e_m(s_m/c_m-1)\le e_{m-1}(s_m/c_{m-1}-1)$

当然必要条件不是充分要条件
不相邻机器人如何简便分析还没思路。

点评

将5#的这个筛选条件普及到任意两个相邻机器人,所得结果涉及组合计算,意义不大了。  发表于 2014-8-15 18:01
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-8-15 21:30:48 | 显示全部楼层
hujunhua 发表于 2014-8-15 13:07
4#和5#给出了2个不需要组合计算的筛选条件,对 n! 个全排列,最多可以筛掉其中的3/4,剩下n!/4.

记$u_k= ...

以分段的观点看爬升高度公式
$e_1/s_1+e_2/s_2+\cdots+(e_i/s_i+\cdots+e_j/s_j)+\cdots+e_(n-2)/s_(n-2)+e_(n-1)/s_(n-1)+e_n/s_n$

把行动方案分成X段考虑,每段能达到的最大高度跟前方能耗水平的和与本段个体特征有关。而与前后方的排列次序无关。

7#的筛选其实是分了(2、n-4、2)3段,并只优化了前后段,中段依然是穷尽。
如果穷尽的内容改为  分段为(2、2、2……2、(n为奇数有1)),则每段2可以使用5#公式优化。这样的确能减少相当开销。 跨段的约束可以作为某方案非优,提前结束计算的判断。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-8-15 21:41:29 | 显示全部楼层
不过既然连n!同阶都考虑穷尽,不如考虑添加n个机器人分别当头位,n个方案。
逐次方案在尾部增加机器人,分拆成$n(n-1)$组。对比含有相同机器人的方案,保留最好
反复增加机器人到全部进入队列
这样最多 方案数为 C(n,n/2),操作次数为n^2/2。
  

点评

面对n=100依然是大数据  发表于 2014-8-15 21:42
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-6-3 14:40 , Processed in 0.083813 second(s), 22 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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