algorithm - 随机提前终止的游戏中元素的最佳顺序

Question

我有 n 件元素。每个项目都有一个值 v_i 和一个连续概率 p_i。我打算玩一个游戏，在这个游戏中我选择一个项目，获得它的值(value)，然后继续玩它相应的概率。如果我要继续，我可以拿起任何剩余的元素，将其值(value)加到我的总和中，并再次受到其继续概率的影响。如果幸运的话，我可以一直玩到没有剩余元素。我想选择一个排序来最大化我的期望值。

是否有有效的算法来解决这个问题？

Answer 1

你的观察是正确的!您应该按 v_i/(1 - p_i) 排序并按该顺序列出项目。

要了解其工作原理，让我们从查看两项的情况开始。假设您有两个项目 (v1, p1) 和 (v2, p2)。我们的目标是定义某种排序关系 ≥ 使得 (v1, p1) ≥ (v2, p2) 如果首先选择 (v1, p1) 的预期奖励优于选择 (v2, p2) 的预期奖励首先。

如果你先选择(v1, p1)，你的期望返回是v1 + p1 v2，如果你先选择(v2, p2)，你的期望返回是v2 + p2 v1。我们想确定必须发生什么

v1 + p1 v2 ≥ v2 + p2 v1

发生。通过一些代数，我们知道当且仅当

v1 - p2 v1 ≥ v2 - p1 v2

v1 (1 - p2) ≥ v2 (1 - p1)

v1 / (1 - p1) ≥ v2 / (1 - p2)

这是你之前发现的。

现在，想象一下您可以按照自己喜欢的顺序选择元素。让我们根据它们出现的顺序将它们编号为 v1、v2、...、vn。现在假设您已经选择了这些项目，因此它们不会根据上面给出的顺序按降序排列。这意味着必须在某处存在两个乱序的相邻项。让 v_i 成为第一次发生这种情况。那么预期的奖励将是

v1 + p1(v2 + p2(v3 + p3(...(v_i + p_i(v_{i+1} + p_{i+1}X))...)

其中 X 是剩余项的值。想象一下，您交换项目 v_{i+1} 和 v_i 并保留其他所有内容。那么你的奖励将是

v1 + p1(v2 + p2(v3 + p3(...(v_{i+1} + p_{i+1}(v_i + p_i X))...)

由于这里的前导项是相等的并且都是非负的，我们现在可以忽略它们并专注于核心项

v_i + p_i(v_{i+1} + p_{i+1} X)

和

v_{i+1} + p_{i+1}(v_i + p_i X)

我们知道v_i和v_{i+1}是乱序的，所以

v_i + p_i v_{i+1} ≤ v_{i+1} + p_{i+1} v_i

因此，假设我们执行交换，我们看到

v_i + p_i(v_{i+1} + p_{i+1} X)

= v_i + p_i v_{i+1} + p_i p_{i+1} X

≤ v_{i+1} + p_{i+1} v_i + p_i p_{i+1} X

= v_{i+1} + p_{i+1}(v_i + p_i X)

这意味着期望值只能随着我们对序列进行更多排序而上升，因此按 v_i/(1 - p_i) 降序排序的贪心解决方案确实是最优解!

所以，是的。按 v_i/(1 - p_i) 排序并按此顺序列出内容。