均匀分布下的最优寻宝策略

作者: 张矩阵 | 来源:发表于2019-02-09 11:40 被阅读0次

均匀分布下的最优寻宝策略
【恋上数据结构与算法二】(六)贪心(Greedy)
(Greedy)贪心策略
囚徒困境下的最优策略
算法--策略-贪心分治
AutoScaling 在Scale in时的实例终止策略
火树科普博弈论-纳什均衡 Nash equilibrium（上）
用时间换钱的最优化策略！
成功的捷径｜找到你基于天赋的最优人生策略
简单贪心(2020-01-11)

源起

2018年9月入职阿里，午饭时和入职半年的同事钱导闲聊说到了这道面试题。题目是钱导2010年面试阿里时面试官出的题目。近十年了，因缘际会，加上之前并未在面试书中见过这道题目，于是将钱导和我的讨论结果记为此文。

问题

现有一条数轴，有一宝藏位于原点到坐标 $L$ 的线段上。寻宝人需要从原点的位置出发，找到宝藏后将宝藏带回原点。

寻宝人在行走路上需要消耗粮食，每走 $1$ 个单位的距离需要消耗粮食量 $C$
在原点处有粮食站可供寻宝人取粮食。

寻宝人可以一次性带足粮食；也可以第一次只带部分粮食、当走了一定距离仍无法找到宝藏时就折返回原点补充粮食、再开始第二次寻宝，以此类推。（注意返程路上也是需要消耗粮食的，不可以到了断粮时才开始返程。而是应该在粮食恰好只够返程、且依然未能寻到宝时返程）

若宝藏位置符合均匀分布，寻宝人使用怎样的寻宝策略，可以使得从粮食站取的粮食量的期望值最小？

猜测

猜测 $1$
在寻宝的折返过程中，如果某一次未能寻到宝、需要回原点粮食站补充粮食，则返程路上消耗的粮食可以说是被“浪费”的，是否应该一步到位，第一次就带足粮食，避免有“浪费”的情况发生？
猜测 $2$
如果宝藏就在离原点很近的地方，那么只带少量粮食就可以寻到宝了。是否应该先带少量粮食“试探”一下能不能偷鸡快速中奖，而不是一上来就all in所有家当？

建模

这道题目的关键，是用合适的数学语言进行刻画。当建模完成后，后面的代数运算都是自然的。

在连续型概率下，单点的概率为 $0$ ，但宝藏依然有可能位于坐标 $0$ 和坐标 $L$ （概率测度为 $0$ 仅为不可能事件的必要不充分条件）

为了讨论的方便（主要为了能够引入无限步策略，对于原问题其实无所谓），我们假设宝藏不会位于坐标 $0$ 和坐标 $L$ ，这不影响问题的实质。

有限步策略

现假设一个策略恰使用了 $n$ 次取粮，每次取粮走的距离为严格递增序列 $a_1, ..., a_n$
其中 $a_n=L$ ，因为必须保证该策略一定能寻宝成功。
注意每次寻宝人会在粮食恰好只够返程、且依然未能寻到宝时返程补粮

为了后续推导记号的便捷性，我们记 $a_0=0$
则一个有限步策略由严格递增序列 $a_0, a_1, ..., a_n$ 构成，其中 $a_0=0,a_n=L$

宝藏位置随机变量 $X$ 为 $[0, L]$ 上的均匀分布，即 $X \sim U(0,L)$
当X=x时，设 $i$ 恰使得 $a_i <= x < a_{i+1}$
则取走的粮食为 $f(x) = \Sigma^{i+1}_{k=0}2Ca_k$
因此，取走的粮食的数学期望为
$\begin{split} E(f(X))&=\int_0^{L}p(x)f(x)dx \\ &= \Sigma_{i=0}^{n-1}\int_{a_i}^{a_{i+1}}p(x)f(x)dx\\ &= \Sigma_{i=0}^{n-1}\int_{a_i}^{a_{i+1}}p(x)(\Sigma^{i+1}_{k=0}2Ca_k)dx \\ &= \Sigma_{i=0}^{n-1}\Sigma^{i+1}_{k=0}2Ca_k\int_{a_i}^{a_{i+1}}p(x)dx \\ &= \frac{2C}{L}\Sigma_{i=0}^{n-1}\Sigma^{i+1}_{k=0}(a_{i+1}-a_i)a_k \end{split} \tag 1$

考察项 $\Sigma^{i+1}_{k=0}(a_{i+1}-a_i)a_k$ ，得
$\begin{split} \Sigma^{i+1}_{k=0}(a_{i+1}-a_i)a_k &=\Sigma^{i+1}_{k=0}a_{i+1}a_k - \Sigma^{i+1}_{k=0}a_ia_k \\ &= (a_{i+1}^2 + a_{i+1}a_i + \Sigma^{i-1}_{k=0}a_{i+1}a_k) - (a_{i+1}a_i + a_i^2 + \Sigma^{i-1}_{k=0}a_{i}a_k) \\ &= (a_{i+1}^2 - a_i^2) + (a_{i+1}-a_i)\Sigma^{i-1}_{k=0}a_k \end{split} \tag 2$

当 $i \ge 2$ 时，因 $a_0, a_1, ..., a_n$ 是严格递增序列且 $a_1>0$
所以 $(a_{i+1}-a_i)\Sigma^{i-1}_{k=0}a_k > 0, \quad i\ge2 \tag 3$

因此，当 $n \ge 3$ 时，将 $(3)$ 代回 $(1)$ 可得
$E(f(X)) > \frac{2C}{L}\Sigma_{i=0}^{n-1}(a_{i+1}^2 - a_i^2) = \frac{2C}{L}a_n^2 = 2CL$

而当 $n=1$ 或 $n=2$ 时，由 $(1)$ 易得 $E(f(X)) = 2CL$ ，为最小期望
当 $n=1$ 时还有 $Var(f(X))=0$ 为最小方差

无限步策略

对于一个无限步的策略，我们沿用在有限步策略中使用的记号和公式。
实际上，一个无限步策略是逐渐逼近坐标 $L$ 的，为使一个无限步策略是合法的，易知 $a_i<L$ 对任意 $i$ 成立且 $\lim_{n \to \infty} a_n= L$

与有限步策略的情形类似，只要任取 $n>3$ 可得
$E(f(X))=\int_0^{L}p(x)f(x)dx \gt \Sigma_{i=0}^{n-1}\int_{a_i}^{a_{i+1}}p(x)f(x)dx \gt 2CL$

更进一步：期望是否可能无穷

由前面有限步策略、无限步策略的讨论，实际上我们已经得到了原问题的答案。这里我们更深入的讨论：一个不好的策略是否可能会导致取粮的数学期望太大（例如正无穷）

我们继续使用前面的记号，将 $(2)$ 代回 $(1)$ 得到
$\begin{split} E(f(X)) &= \frac{2C}{L}\Sigma_{i=0}^{n-1}\Sigma^{i+1}_{k=0}(a_{i+1}-a_i)a_k \\ &= \frac{2C}{L}\Sigma_{i=0}^{n-1}[(a_{i+1}^2 - a_i^2) + (a_{i+1}-a_i)\Sigma^{i-1}_{k=0}a_k] \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}\Sigma_{i=0}^{n-1}[(a_{i+1}-a_i)\Sigma^{i-1}_{k=0}a_k] \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}\Sigma_{i=0}^{n-1}(a_{i+1}\Sigma_{k=0}^{i-1}a_k - a_i\Sigma_{k=0}^{i-1}a_k) \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}[(\Sigma_{i=0}^{n-1}a_{i+1}\Sigma_{k=0}^{i-1}a_k) - (\Sigma_{i=0}^{n-1}a_{i}\Sigma_{k=0}^{i-1}a_k) ] \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}[(\Sigma_{i=0}^{n-1}a_{i+1}\Sigma_{k=0}^{i-1}a_k) - (\Sigma_{i=0}^{n-2}a_{i+1}\Sigma_{k=0}^{i}a_k) ] \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}[(\Sigma_{i=0}^{n-1}a_{i+1}\Sigma_{k=0}^{i-1}a_k) - \Sigma_{i=0}^{n-2}a_{i+1}(\Sigma_{k=0}^{i-1}a_k + a_i) ] \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}(a_n\Sigma_{k=0}^{n-2}a_k - \Sigma_{i=0}^{n-2}a_{i+1}a_{i}) \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}\Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) \\ \end{split} \tag 4$

有限步策略是否可能取粮期望过大

由 $(4)$ 式，有限步策略的期望总是有限的。
因此，我们考虑的问题为：对于任意给定的正数 $A$ ，是否总存在足够差的策略使 $E(f(X))>A$

考虑一个“试探型”的 $n$ 步策略，对于 $i=1,2,...,n$ , 有 $a_i = i\frac{L}{n}$
我们用 $\Theta(n^p)$ 表示与 $n^p$ 为同阶无穷大
则
$\begin{split} \Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) &= \Sigma_{i=0}^{n-2}i\frac{L}{n}[L-(i+1)\frac{L}{n}]\\ &= \frac{L^2}{n^2}\Sigma_{i=0}^{n-2}[in-(i+1)i] \\ &= \frac{L^2}{n^2}[(n-1)\Sigma_{i=0}^{n-2}i-\Sigma_{i=0}^{n-2}i^2 ]\\ &= \frac{L^2}{n^2}[\frac{1}{2}(n-1)^2(n-2) - \frac{1}{6}(n-2)(n-1)(2n-3) ]\\ &= \frac{L^2}{n^2}\Theta(n^3)\\ &= L^2\Theta(n)\\ \end{split}$
代回 $(4)$ 式得 $E(f(X))=2CL + 2CL\Theta(n)$
当 $n \rightarrow \infty$ 时，有 $E(f(X)) \rightarrow \infty$ （注意这个表述并不代表无限步的策略）
即对于任意给定的正数 $A$ ，总存在足够大的 $n$ 使得 $E(f(X))>A$

无限步策略是否可能取粮期望过大

当策略为无限步时，我们考虑：此时的期望是有限还是无限？
注意 $(4)$ 式在无限步策略下的写法略有不同：
$\begin{split} E(f(X)) &= \lim_{n \to +\infty} \frac{2C}{L}a_n^2 + \frac{2C}{L}\Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) \\ &= 2CL + \frac{2C}{L}\lim_{n \to +\infty}\Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) \end{split} \tag{5}$

调和级数

考虑一个无限步的策略：对于 $i=1,2,...$ 有 $a_i = L(1-\frac{1}{i})$
易证这是一个合法的寻宝策略。
则
$\begin{split} \Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) &= L^2\Sigma_{i=0}^{n-2}(1-\frac{1}{i})(-\frac{1}{n}+\frac{1}{i+1})\\ &=L^2(-\Sigma_{i=0}^{n-2}\frac{1}{n} + \Sigma_{i=0}^{n-2}\frac{1}{i+1} + \Sigma_{i=0}^{n-2}\frac{1}{ni} - \Sigma_{i=0}^{n-2}\frac{1}{i(i+1)}) \end{split}$
其中，
$\Sigma_{i=0}^{n-2}\frac{1}{i+1}$ 为调和级数，当 $n \rightarrow \infty$ 时趋于正无穷。其余三项均易证 $n \rightarrow \infty$ 有有限极限值。
因此由 $(5)$ 式知此时 $E(f(X))=+\infty$

几何级数

考虑一个无限步的策略：对于 $i=1,2,...$ 有 $a_i = L(1-\frac{1}{2^i})$
易证这是一个合法的寻宝策略。
则
$\begin{split} \Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) &= L^2\Sigma_{i=0}^{n-2}(1-\frac{1}{2^i})(-\frac{1}{2^n}+\frac{1}{2^{i+1}})\\ &=L^2(-\Sigma_{i=0}^{n-2}\frac{1}{2^n} + \Sigma_{i=0}^{n-2}\frac{1}{2^{i+1}} + \Sigma_{i=0}^{n-2}\frac{1}{2^i2^n} - \Sigma_{i=0}^{n-2}\frac{1}{2^i2^{i+1}}) \end{split}$
由几何级数的性质，易证上式四项级数均有有限极限
因此由 $(5)$ 式知此时 $E(f(X))$ 为有限值

结论

有两种策略可以使得提取粮食的期望值最小

只走一次，一次带够可以抵达终点的粮食 (即猜测 $1$ 的方案)
走两次，第一次带不足以抵达终点的粮食（具体数量任意），第二次带够可以抵达终点的粮食

不好的策略

有限步的策略虽然期望值为有限，但可以要多差有多差 (例如猜测 $2$ 的方案)
无限步的策略也可能期望值为有限，它比某些有限步策略还更好。

继续扩展的方向

在写这篇文章时，我的大部分精力实际上花在了没有写出来的部分——针对一般概率分布的讨论。最初，我考虑了常见的连续型分布，但解析形式的复杂性（例如正态分布无原函数等）让我转而研究较为简化的分段均匀分布的性质。实际上，由于分段均匀分布可以分任意多段，可以任意逼近一般的概率分布（想象一下直方图），因此如果能研究好这类分布，对一般的概率分布也能有一个大致的认识。

但即使在这种情形下，我依然没有得出较有价值的结论。推出的表达式复杂，且试了一些具体数值后发现结果依赖于具体的参数设置，这使得整个问题的分类讨论更加繁复。最终我只推出了某些无关痛痒的性质（例如如果临近原点处概率极高的话可以先试探等显而易见的结论），对最优策略的推导并无显著帮助。

这个问题如果继续扩展，一般的概率分布确是一个方向。但未必会得出比较精巧的结果。实际上在原问题的讨论中我们也已经发现，很多不等号放缩都很“松”、很随意。

感兴趣的同学可以继续研究。

一点唠叨

熟悉数学分析的同学会发现，文中对定积分拆为无穷个分段的叙述较为含糊。该处直接以分段概率算期望的方式切入可能会更清晰一些。该处尽管直觉上没有问题，但仍需要更严格的表述。
原题最核心的地方是用数学语言建模，一旦建模完成，后续的推导实际没有太大难度。这也是我自己学数学、学算法时常陷入的困惑：直接看解法总觉得很简单，一盖上书本又什么都想不起来。事后诸葛亮永远容易、追根溯源才能成为自己的东西。
每一次相聚都是阔别重逢。珍惜那些没有见过的面试题

均匀分布下的最优寻宝策略
源起 2018年9月入职阿里，午饭时和入职半年的同事钱导闲聊说到了这道面试题。题目是钱导2010年面试阿里时面试官...
【恋上数据结构与算法二】(六)贪心(Greedy)
贪心(Greedy) ◼ 贪心策略，也称为贪婪策略每一步都采取当前状态下最优的选择(局部最优解)，从而希望推导出全...
(Greedy)贪心策略
贪心策略是一种每一步都采取当前状态下最优的选择(局部最优解)，从而希望推导出全局最优解的一种策略。在我们之前文章里...
囚徒困境下的最优策略
博弈本意是：下棋。引申义是：在一定条件下，遵守一定的规则，一个或几个拥有绝对理性思维的人或团队，从各自允许选择的行...
算法--策略-贪心分治
贪心贪心策略, 也叫作贪婪策略每一步都采取当前状态下最优解, 从而推导出全局最优解应用, 哈夫曼树, 最小生...
AutoScaling 在Scale in时的实例终止策略
默认终止策略此默认终止策略可帮助确保您的网络架构均匀分布到多个可用区。使用默认终止策略时，Auto Scalin...
火树科普博弈论-纳什均衡 Nash equilibrium（上）
回顾一下昨天的主要内容介绍了博弈时的两种策略：占优策略和最佳应对。占优策略是针对对方所有策略均有效的最优策略；最...
用时间换钱的最优化策略！
用时间换钱的最优化策略！
成功的捷径｜找到你基于天赋的最优人生策略
几乎每个人，都想找到自己的人生最优策略。但是，人生到底有没有最优策略呢？答案是：有的。 —1 — 两种人生策略...
简单贪心(2020-01-11)
贪心算法是指，在对问题求解中，对问题的每一步决策都采取当前意义下最优策略的算法，即问题的整体最优性可以由局部最优性...