1

考虑一个整数序列A = a1, a2, a3, ... an。A的子序列B是一个序列B = b1, b2, .... ,bn ，它是通过删除一些元素但保持顺序从A创建的。给定一个整数序列A，目标是计算一个交替子序列B，即一个序列b1, ... bn使得对于 {2, 3, ... , m-1} 中的所有i，如果 b{i- 1} < b{i} 然后 b{i} > b{i+1} 如果 b{i-1} > b{i} 然后 b{i} < b{i+1}**

考虑该问题的在线版本，其中序列A是逐个元素给出的，并且每次都需要直接决定是否在子序列B中包含下一个元素。是否有可能实现恒定的竞争比率（通过使用确定性在线算法）？要么给出一个达到恒定竞争比的在线算法，要么表明不可能找到这样的在线算法。

假设序列 [9,8,9,8,9,8, .... , 9,8,9,8,2,1,2,9,8,9, ... , 8,9,8, 9,8,9]

我的论点：算法必须立即决定是否将传入的数字插入子序列。如果算法现在得到数字 1 然后 2 然后 2 它将最终确定它们是序列的一部分，因此非线性因子比 n-3 的最优解更差。

-> 没有恒定的竞争力！

这是一个适当的论证吗？

4

1 回答 1

1

如果我理解您的意思，那么您的论点是正确的，但是您在示例中给出的顺序是错误的。例如，算法可以选择所有的 9 和 8。
您可以稍微改变您的论点以使其更准确，例如考虑序列

3,4,3,4,3,4,......, 1/5,2/6,1/5,2/6,....

说明：
您以 etc. 开始序列，3,4,3,4,...直到算法选择两个数字。如果它从来没有，它显然没有竞争力（它0/1退出n）
如果算法选择了 a 3，那么4，算法接下来必须取一个低于 的数字4。通过继续5,6,5,6,...算法不能取另一个数字。
如果算法选择采用 a4那么 a 3，通过类似的共鸣，我们可以很容易地看到 continue with 如何1,2,1,2,...阻止算法采用另一个数字。
因此，在任何情况下，该算法都不能超过2每个 的数字n，正如您所说，这不是一个恒定的竞争比率。

于 2019-08-20T21:08:56.753 回答