获得达到目标概率的算法
好的，我会在这里尽可能详细地说明。
想象一下用户经历了一组他可以选择的“选项”。每次他选择时，他都会得到四种不同的选择。这 4 个“槽位”中还可以出现更多选项。其中每一个都有一定的确定且已知的出现概率。并非所有选项出现的可能性都相同，并且某些选项要求之前已经在复杂的相互依赖树中选择了其他选项。 （这个我已经定义了）
当用户选择 4 个选项之一时，他会看到 4 个选项中的另一个选择。选项池被再次定义，并且可以取决于用户之前选择的内容。
在所有可能出现的“选项”中，有一些是特殊的，称为关键选项。
当程序启动时，用户会看到前 4 个选项。对于这 4 个选项中的每一个，程序需要计算用户在（可变的）N 个选择期间“实现”所有 KEY 选项的总概率。
例如，如果总共有 4 个选项，则实现其中任何一个的概率恰好为 1，因为所有选项都出现在开头。
如果有人可以建议我应该从什么逻辑开始，我将非常感激。 我正在考虑计算所有可能的选择序列，并计算导致在 N 个“步骤”内选择 KEY 选项的序列，但问题是所有这些选项出现的概率并不均匀，而且选项池也会发生变化用户选择并积累他的选项。
我很难将明确定义的概率和选项的依赖性实现到可以给出合理总概率的算法中。因此，用户每次都知道这 4 个选项中的哪一个最适合他最终获得 KEY 选项。
有什么想法吗？
编辑： 这是一个例子：
假设池中有 7 个选项。选项1，...，选项7 选项 7 需要选项 6；选项 6 需要选项 4 和选项 5； option1 到 5 不需要任何东西，可以立即出现，相应的概率为 option1.p, ..., option5.p； 例如，KEY 选项是 option7； 用户在 1-5 中随机（但加权）选择 4 个选项，程序需要这样说： “如果你选择（第一个），你最多有 ##% 的机会在最多 N 次尝试中获得选项 7。”与其他 3 个选项类似。
当然，对于一些低N的情况，不可能得到选项7，而对于一些大N的情况，这是肯定的。 N 可以选择但是固定的。
编辑：所以，这里的重点不是用户随机选择。要点是 - 程序建议选择哪个选项，以最大化最终在 N 个步骤后向用户提供所有关键选项的概率。
对于上面的例子；假设我们选择 N = 4。因此程序需要告诉我们出现的前 4 个选项中的哪一个（选项 1-5 中的任意 4 个），选择哪一个最有可能获得选项 7。因为对于选项 7，您需要选项 6，而对于选项 7，您需要选项 4 和选项 5，因此很明显，您必须在第一组选项中选择选项 4 或选项 5。当然，其中之一肯定会出现。 假设我们得到第一个选择 {option3, option5, option2, option4}。然后程序说： 如果你选择选项3，你将永远不会在4个步骤内得到选项7。 p = 0; 如果你选择选项5，你可能会得到选项7，p=....； ...选项2，p = 0； ...选项4，p = ...；
无论我们选择什么，对于接下来的 4 个选项，p 都会重新计算。显然，如果我们选择选项 3 或选项 2，则每一个进一步的选择使我们选择选项 7 的概率恰好为 0。但对于选项4和选项5，p> 0;
现在清楚了吗？我不知道如何获得这些概率 p。
Okay, I'm gonna be as detailed as possible here.
Imagine the user goes through a set of 'options' he can choose. Every time he chooses, he get, say, 4 different options. There are many more options that can appear in those 4 'slots'. Each of those has a certain definite and known probability of appearing. Not all options are equally probable to appear, and some options require others to have already been selected previously - in a complex interdependence tree. (this I have already defined)
When the user chooses one of the 4, he is presented another choice of 4 options. The pool of options is defined again and can depend on what the user has chosen previously.
Among all possible 'options' that can ever appear, there are a certain select few which are special, call them KEY options.
When the program starts, the user is presented the first 4 options. For every one of those 4, the program needs to compute the total probability that the user will 'achieve' all the KEY options in a period of (variable) N choices.
e.g. if there are 4 options altogether the probability of achieving any one of them is exactly 1 since all of them appear right at the beginning.
If anyone can advise me as to what logic i should start with, I'd be very grateful.
I was thinking of counting all possible choice sequences, and counting the ones resulting in KEY options being chosen within N 'steps', but the problem is the probability is not uniform for all of them to appear, and also the pool of options changes as the user chooses and accumulates his options.
I'm having difficulty implementing the well defined probabilities and dependencies of the options into an algorithm that can give sensible total probability. So the user knows each time which of the 4 puts him in the best position to eventually acquire the KEY options.
Any ideas?
EDIT:
here's an example:
say there are 7 options in the pool. option1, ..., option7
option7 requires option6; option6 requires option4 and option5;
option1 thru 5 dont require anything and can appear immediately, with respective probabilities option1.p, ..., option5.p;
the KEY option is, say, option7;
user gets 4 randomly (but weighted) chosen options among 1-5, and the program needs to say something like:
"if you choose (first), you have ##% chance of getting option7 in at most N tries." analogous for the other 3 options.
naturally, for some low N it is impossible to get option7, and for some large N it is certain. N can be chosen but is fixed.
EDIT: So, the point here is NOT the user chooses randomly. Point is - the program suggests which option to choose, as to maximize the probability that eventually, after N steps, the user will be offered all key options.
For the above example; 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. since for option7 you need option6, and for that you need option4 and option5, it is clear that you MUST select either option4 or option5 on the first set of choices. one of them is certain to appear, of course.
Let's say we get this for the first choice {option3, option5, option2, option4}. The program then says:
if you chose option3, you'll never get option7 in 4 steps. p = 0;
if you chose option5, you might get option7, p=....;
... option2, p = 0;
... option4, p = ...;
Whatever we choose, for the next 4 options, the p's are re calculated. Clearly, if we chose option3 or option2, every further choice has exactly 0 probability of getting us to option7. But for option4 and option5, p > 0;
Is it clearer now? I don't know how to getting these probabilities p.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这听起来像是一个相当复杂的马尔可夫链类型问题。为每个状态创建一个节点；一个状态没有历史，仅取决于可能的退出路径（每个路径都以一定的概率加权）。你在每个节点上放置一个概率，即用户处于该状态的机会，因此，对于第一步，他的起始节点将为 1，其他位置均为 0。然后，根据哪些节点相邻以及到达它们的机会，通过更新每个顶点的概率来迭代到下一步。因此，您可以轻松计算用户在 15 步内可能会到达哪些状态以及相关的概率。如果您对渐近行为感兴趣（如果他可以永远玩下去会发生什么），您可以制作一大堆线性联立方程，然后直接求解它们，或者如果您的树或图具有整齐的形式，则可以使用一些技巧。您通常会得到循环解决方案，用户可能会陷入循环，等等。
This sounds like a moderately fiddly Markov chain type problem. Create a node for every state; a state has no history, and is just dependent on the possible paths out of it (each weighted with some probability). You put a probability on each node, the chance that the user is in that state, so, for the first step, there will be a 1 his starting node, 0 everywhere else. Then, according to which nodes are adjacent and the chances of getting to them, you iterate to the next step by updating the probabilities on each vertex. So, you can calculate easily which states the user could land on in, say, 15 steps, and the associated probabilities. If you are interested in asymptotic behaviour (what would happen if he could play forever), you make a big pile of linear simultaneous equations and just solve them directly or using some tricks if your tree or graph has a neat form. You often end up with cyclical solutions, where the user could get stuck in a loop, and so on.
如果您认为用户随机选择选项，并且总是在节点上向他呈现相同的选项分布，则可以将其建模为图上的随机游走。最近有一篇关于 计算 mathematica 博客上特定随机游走的终止概率。
If you think the user selects the options at random, and he is always presented the same distribution of options at a node, you model this as a random walk on a graph. There was a recent nice post on calculating terminating probabilities of a particular random walks on the mathematica blog.