02 线搜索问题

线搜索问题(Line Search)

小A位于数轴上的原点，小B位于数轴上的整点$D$。小B位置固定不动，但小A不知道小B的位置。小A每次可以选择向右移动1或向左移动1，每次移动后会得到回答“现在的位置是否已经与小B重合”。设计一个算法，让小A能移动到小B的位置，并且移动的步数尽量少。

如果这个问题允许离线，那么小B的位置就可以认为是已知的，于是小A直接向小B的方向移动$D$步即可。但对于在线的情况，由于不知道小B的位置，小A必须按照某种策略左右搜索（线搜索）才能最终找到小B的位置。

Zig-Zag策略

从小A的视角看，小B出现在左边和右边的概率是相等的。所以一个好的搜索算法应当某种程度是左右对称的，一个一直向右搜索的算法一定不是一个好算法。最简单的策略是：移动到1，再一路移动到-1，再一路移动到2，再一路移动到-2，再到3……这个策略称为Zig-Zag策略，我们来分析它与最优算法（直接移动到$D$）的竞争比：不妨设$D$为正数，那么小A第一次到达$D$时走过的路径是$0\to 1\to -1\to 2\to -2\to \cdots\to -(D-1)\to D$，总路程为$1+2+3+\cdots+2D-1$ $=\dfrac{(1+2D-1)(2D-1)}{2}=D(2D-1)$，因此$\dfrac{\text{ALG}}{\text{OPT}}=\dfrac{D(2D-1)}{D}=2D-1=O(D)$。这是一个不可接受的竞争比，因为这意味着当$D\to \infty$时竞争比也趋向无穷。

我们注意到上面的策略中搜索的效率很低，往返过程中大部分时间都走在已经探索过的点上，只有最后一步才会把范围拓展一格。因此一个自然的想法是提高搜索范围的增长速度，想到了以下这个倍增Zig-Zag策略：$0\to 1\to -2\to$ $4\to -8\to\cdots$。设$2^{k-1}<D\leq 2^k$，那么走过的总路程为$1+(1+2)+(2+4)+(4+8)+\cdots+(2^{k-1}+2^k)+2^k+D$ $=2\cdot \dfrac{2^{k+1}-1}{2-1}+D=2^{k+2}-2+D$。可见竞争比为$\dfrac{\text{ALG}}{\text{OPT}}=\dfrac{2^{k+2}-2+D}{D}=1+2\cdot\dfrac{2^{k+1}-1}{D}<1+\dfrac{2^{k+2}}{2^{k-1}}=9$。竞争比优化到了常数！

对于确定性算法，$9$的竞争比已经是tight的了吗？可以证明确实如此：设$f(i)$表示第$i$次连续同方向移动到达的最右位置或最左位置，若$f(k-2)<D\leq f(k)$，那么可以写出$\dfrac{\text{ALG}}{\text{OPT}}=\dfrac{2(|f(1)|+|f(2)|+\cdots+|f(k-1)|)+D}{D}$ $<1+2\cdot \dfrac{|f(1)|+\cdots +|f(k-1)|}{|f(k-2)|}$。所以我们把问题转化了一个纯数学的问题：是否对于所有函数$f:\mathbb{N}\to\mathbb{Z}$，$|f(n+1)|\geq |f(n)|$，都有$\forall k>0,\dfrac{|f(1)|+\cdots +|f(k-1)|}{|f(k-2)|}\geq 4$？可以证明这是正确的，这里省略。