algorithm - 寻找更好的算法来解决这种概率/组合游戏

Question

假设我们有从 1 到 10 的 10 个整数。

我们也有一些玩家，他们每个人都从这个集合中获得了不同的随机数。

现在玩家开始说出有关他或她的号码的信息:我的号码在 a subset of initial 1 to 10 set 中。例如 我的号码是 8,9 或 10。

我们想对尚未发表任何言论的玩家的数量做出假设(当然，对于给定初始信息的每个沉默玩家的假设也是相同的)

假设我们有 5 个玩家，前 3 个玩家一一说:

1. 我的是 8、9 或 10
2. 我的是 7 或 6
3. 我的是 7、6、9 或 10

现在我们需要计算下一位玩家有特定数字的几率(概率)是多少，比如下一位玩家有7中的数字的几率是多少。

当然这只是一个示例，每个玩家可以以任何形式提供信息(例如1 or 10、1 through 10 等)

这是某种众所周知的问题还是有人发现了一个好的方法？ 我真的希望它具有高性能，所以暴力破解并不好。我认为它可以直接与贝叶斯定理相关联，但不能 100% 确定它可以在这里应用。

示例:

简单案例 2 玩家和 12345 个号码。第一位玩家有 4 或 5。 然后对于第二位玩家，他有 25% 的概率有 1 个，但只有 12.5% 的概率有 4 个，因为在第一位玩家说出关于他手牌的信息后有 2 种可能的结果。

1234或1235，我们可以看出1是(1/4 * 2)/2 =1/4 4是(1/4 * 1)/2= 1/8 这就是我所说的蛮力解决方案，计算所有可能的组合并通过分析它们中的每一个来推导出数字概率。

更新

Mr.Wizard 建议的解决方案有效。

如果你对它的外观感到好奇，这里是代码:

class Program
    {
        static void Main()
        {
            int length = 5;
            double[][] matrix = new double[length][];
            for (int i = 0; i < length; i++) {
                matrix[i] = new double[length];
            }

            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    matrix[i][j] = 1;
                }
            }

            matrix[0] = new double[] { 0, 0, 0, 1, 1 };
            matrix[1] = new double[] { 0, 0, 1, 1, 0 };
            matrix[2] = new double[] { 0, 0, 0, 0, 1 };

            DumpMatrix(matrix);
            while(true)
            {
                NormalizeColumns(matrix);
                DumpMatrix(matrix);
                NormalizeRows(matrix);
                DumpMatrix(matrix);
                Console.ReadLine();
            }
        }

        private static void NormalizeRows(double[][] matrix)
        {
            for (int i = 0; i < matrix.Length; i++)
            {
                double sum = matrix[i].Sum();
                for (int j = 0; j < matrix.Length; j++) {
                    matrix[i][j] = matrix[i][j] / sum;
                }
            }
        }

        private static void NormalizeColumns(double[][] matrix)
        {
            for (int j = 0; j < matrix.Length; j++)
            {
                double columnSum = 0;
                for (int i = 0; i < matrix.Length; i++)
                {
                    columnSum += matrix[i][j];
                }
                for (int i = 0; i < matrix.Length; i++) {
                    matrix[i][j] = matrix[i][j] / columnSum;
                }
            }
        }

        private static void DumpMatrix(double[][] matrix)
        {
            for (int i = 0; i < matrix.Length; i++) {
                for (int j = 0; j < matrix.Length; j++) {
                    Console.Write(matrix[i][j].ToString("0.#####").PadRight(8));
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }

    }

虽然从这个例子中很明显它接近最终结果的速度不是很快。

这里玩家 3 正好有 5，玩家一和玩家二可以分别有 4 或 5 和 3 或 4，这意味着玩家一有 4，因为玩家 3 得到了5 和玩家 2 有 3，因为玩家 2 有 4。但是经过多次迭代后，我们在匹配列中接近 1 的玩家 1 和 2 的值。

Answer 1

尝试构建一个图表，一侧是球员，另一侧是数字。当且仅当玩家可以根据他们所说的内容获得该数字时，玩家和数字之间才有优势。对于每条边，您需要均匀随机完美匹配包含该边的概率。

不幸的是，如果这个问题有一个精确的多项式时间算法，那么#P ，一个包含 NP 的类(实际上是整个 polynomial hierarchy ，通过 Toda's theorem )等于 P。

由于Jerrum, Sinclair, and Vigoda，至少在理论上，可以通过复杂的算法估计概率。 .我不确定是否有人实现过该算法。