机器人登山问题

KeyTo9_Fans

有$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$时，是否有高效的算法求出能爬升的最大高度？

gxqcn

这个题目蛮有趣的。

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

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

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

所以，是否可用递归算法，比如说深度优先搜索（Depth-First Search, DFS）？

mathe

这个要看数据模式。给定机器人淘汰顺序后，计算达到最高高度是很容易的。每次只要正好将能量全部传递给所有其它机器（这时其它机器能量都满），停掉这个机器人即可。
所以问题就是确定机器人淘汰顺序问题，最多有n!种。
当然如果一个机器人耗能高，携带能量能到达的高度少，那么显然要优先淘汰。
但是如果总是耗能高的机器人携带的能量更多，那么就比较难判断了。

zeroieme

简化为 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$较小的机器人。

zeroieme

接着讨论`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)$,取最小者先淘汰，然后在剩下的机器人中重复这种策略，直到全部排好序。

zeroieme

验算一下。以楼主的`(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组合更优。

hujunhua

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

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)$

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

zeroieme

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#公式优化。这样的确能减少相当开销。 跨段的约束可以作为某方案非优，提前结束计算的判断。

zeroieme

不过既然连n!同阶都考虑穷尽，不如考虑添加n个机器人分别当头位，n个方案。
逐次方案在尾部增加机器人，分拆成$n(n-1)$组。对比含有相同机器人的方案，保留最好
反复增加机器人到全部进入队列
这样最多 方案数为 C(n,n/2)，操作次数为n^2/2。