获得达到目标概率的算法

Question

好的，我会在这里尽可能详细。

假设用户经历了一组他可以选择的“选项”。每次他选择时，他都会得到，比如说，4 个不同的选项。在这 4 个“插槽”中可以出现更多选项。其中每一个都有一定的确定和已知的出现概率。并非所有选项出现的可能性都相同，并且某些选项要求其他选项之前已经被选中——在一个复杂的相互依赖树中。 (这个我已经定义好了)

当用户选择 4 个中的一个时，他会看到另一个 4 个选项的选择。选项池被再次定义，并且可以取决于用户之前选择的内容。

在所有可能出现的“选项”中，有一些特别的选择，称之为关键选项。

程序启动时，会向用户显示前 4 个选项。对于这 4 个中的每一个，程序需要计算用户在(可变的)N 个选择期间“实现”所有关键选项的总概率。

例如如果总共有 4 个选项，则实现其中任何一个的概率恰好为 1，因为它们都出现在开头。

如果有人可以建议我应该从什么逻辑开始，我将不胜感激。 我正在考虑计算所有可能的选择序列，并计算导致在 N 个“步骤”内选择关键选项的序列，但问题是所有这些选项出现的概率并不统一，而且选项池也会随着用户选择并累积他的选项。

我很难将选项的明确定义的概率和依赖性实现到可以给出合理总概率的算法中。因此，用户每次都知道这 4 个中的哪一个使他处于最终获得 KEY 选项的最佳位置。

有什么想法吗？

编辑: 这是一个例子:

假设池中有 7 个选项。选项 1，...，选项 7 选项 7 需要选项 6； option6需要option4和option5； option1 through 5 不需要任何东西，可以立即出现，具有各自的概率 option1.p, ..., option5.p; KEY 选项是 option7； 用户在 1-5 中随机(但加权)选择 4 个选项，程序需要这样说: “如果你选择(第一个)，你有 ##% 的机会在最多 N 次尝试中获得选项 7。”与其他 3 个选项类似。

自然，对于一些低N不可能得到option7，而对于一些大N是肯定的。 N可以选择但固定。

编辑:所以，这里的重点不是用户随机选择。重点是 - 程序会建议选择哪个选项，以最大限度地提高最终在 N 步之后为用户提供所有关键选项的可能性。

对于上面的例子； say we choose N = 4. so the program needs to tell us which of the first 4 options that appeared (any 4 among option1-5), which one, when chosen, yields the best chance of obtaining option7.因为对于 option7 你需要 option6，为此你需要 option4 和 option5，很明显你必须在第一组选项中选择 option4 或 option5。当然，其中之一肯定会出现。 假设我们为第一个选择 {option3, option5, option2, option4} 得到这个。然后程序说: 如果您选择选项 3，您将永远不会在 4 个步骤中获得选项 7。 p = 0; 如果你选择option5，你可能会得到option7，p=....; ... 选项 2，p = 0； ... option4, p = ...;

无论我们选择什么，对于接下来的 4 个选项，都会重新计算 p。显然，如果我们选择选项 3 或选项 2，则每个进一步的选择都有 0 的概率让我们进入选项 7。但是对于option4和option5，p > 0;

现在更清楚了吗？我不知道如何获得这些概率 p。

Answer 1

这听起来像是一个比较复杂的马尔可夫链类型问题。为每个状态创建一个节点；一个状态没有历史，只依赖于可能的路径(每个路径都有一定的概率)。你在每个节点上设置一个概率，即用户处于该状态的机会，因此，对于第一步，他的起始节点将是 1，其他任何地方都是 0。然后，根据哪些节点相邻以及到达它们的机会，通过更新每个顶点上的概率迭代到下一步。因此，您可以轻松计算出用户可以在 15 步内到达哪些状态，以及相关的概率。如果您对渐近行为感兴趣(如果他可以永远玩下去会发生什么)，您可以制作一大堆线性联立方程并直接求解它们，或者如果您的树或图形具有整洁的形式，则使用一些技巧。您通常会以循环解决方案告终，用户可能会陷入循环，等等。