比掷硬币游戏更好的暴力破解算法 [英] Better than brute force algorithms for a coin-flipping game

问题描述

我有一个问题，我觉得应该有一个众所周知的算法来解决它，它不仅比蛮力强，而且我想不到，所以我在这里问.

I have a problem and I feel like there should be a well-known algorithm for solving it that's better than just brute force, but I can't think of one, so I'm asking here.

问题如下:给定 n 个包含 m 个概率的列表(从低到高)，请为每个列表选择一个索引因此所选索引的总和小于 m .然后，对于每个列表，我们掷一个硬币，其中硬币落下的机会等于该列表在选定索引处的概率.最大限度地使硬币降落的机会最大化.

The problem is as follows: given n sorted (from low to high) lists containing m probabilities, choose one index for each list such that the sum of the chosen indexes is less than m. Then, for each list, we flip a coin, where the chance of it landing heads is equal to the probability at the chosen index for that list. Maximize the chance of the coin landing heads at least once.

有没有比暴力破解更好的算法来解决这个问题?

这个问题似乎与背包问题最相似，不同之处在于背包中物品的价值不仅仅是背包中物品的总和.(用Python编写，而不是 sum(p在selected_probabilities中为p的概率)，而是 1-math.prod([1- p在selected_probabilities中的p的概率]))鉴于背包中已包含哪些物品，您可以添加哪些物品的限制.例如，如果背包的特定列表的 index = 3 项目已经在背包中，则不允许为同一列表添加具有 index = 2 的项目(因为您只能为每个列表选择一个索引).因此，根据背包中已有的物品，某些物品可以或不能添加到背包中.

This problem seems most similar to the knapsack problem, except the value of the items in the knapsack isn't merely a sum of the items in the knapsack. (Written in Python, instead of sum(p for p in chosen_probabilities) it's 1 - math.prod([1 - p for p in chosen_probabilities])) And, there's restrictions on what items you can add given what items are already in the knapsack. For example, if the index = 3 item for a particular list is already in the knapsack, then adding in the item with index = 2 for that same list isn't allowed (since you can only pick one index for each list). So there are certain items that can and can't be added to the knapsack based on what items are already in it.

线性优化将不起作用，因为列表中的值不是线性增加的，最终硬币概率相对于所选概率而言不是线性的，并且我们的约束条件是索引的总和，就像David指出的那样，如果您使用二进制变量来选择索引并使用对数来处理非线性，则线性优化 会起作用

Linear optimization won't work because the values in the lists don't increase linearly, the final coin probability isn't linear with respect to the chosen probabilities, and our constraint is on the sum of the indexes, rather than the values in the lists themselves. As David has pointed out, linear optimization will work if you use binary variables to pick out the indexes and a logarithm to deal with the non-linearity.

我发现解释这个问题背后的动机可能有助于理解它.想象一下，您有10秒的时间来解决问题，并且有三种不同的解决方法.给定您尝试该方法多少秒的时间，您就可以确定每种方法解决该问题的可能性的模型，但是如果切换方法，您将失去之前尝试的方法的所有进度.您应该尝试哪种方法，并持续多长时间?

I've found that explaining the motivation behind this problem can be helpful for understanding it. Imagine you have 10 seconds to solve a problem, and three different ways to solve it. You have models of how likely it is that each method will solve the problem, given how many seconds you try that method for, but if you switch methods, you lose all progress on the one you were previously trying. What methods should you try and for how long?

推荐答案

最大化 1-math.prod([1- p表示selected_probabilities中的p]] 等效于最小化 math.prod([1-p在selected_probabilities中为p的概率])，这等效于最小化该目标的对数，它是0-1个指标变量的线性函数，因此您可以按照这种方式进行整数编程

Maximizing 1 - math.prod([1 - p for p in chosen_probabilities]) is equivalent to minimizing math.prod([1 - p for p in chosen_probabilities]), which is equivalent to minimizing the log of this objective, which is a linear function of 0-1 indicator variables, so you could do an integer programming formulation this way.

我不能保证这会比蛮力好得多.问题在于，当 p 接近于零时， math.log(1- p)被 -p 很好地近似.我的直觉是，对于非平凡的实例，它在质量上将类似于使用整数编程来求解子集总和，但效果并不理想.

I can't promise that this will be much better than brute force. The problem is that math.log(1 - p) is well approximated by -p when p is close to zero. My intuition is that for nontrivial instances it will be qualitatively similar to using integer programming to solve subset sum, which doesn't go particularly well.

如果您愿意采用双标准近似方案(得到一个答案，使得所选索引的总和小于m，则至少与最佳答案总和小于(1 −ε)一样好.)m)，然后可以将概率四舍五入为ε的倍数，然后使用动态规划得到一种算法，该算法可以在n，m，1/ε的时间多项式中运行.

If you're willing to settle for a bicriteria approximation scheme (get an answer such that the sum of the chosen indexes is less than m, that is at least as good as the best answer summing to less than (1 − ε) m) then you can round up the probability to multiples of ε and use dynamic programming to get an algorithm that runs in time polynomial in n, m, 1/ε.

这篇关于比掷硬币游戏更好的暴力破解算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！