为此使用图论编写算法

Question

不知道这里是不是问这个问题的好地方。所以，如果我进错论坛了，我很抱歉。

我怎样才能用算法的方式解决下面的问题？

一个房间里有n个盒子。除了一个，所有的里面都有一个橘子。 Mr.X想找到空盒子而不打开它（即如果他打开空盒子，他将输掉比赛！）。每个框内可能有一些关于其他框的信息，如果 Mr.X 读取这些信息可以找出另一个框是否为空。我们（作为知情的第三方）写了一份关于箱子和里面的信息的 table 并交给 Mr.X。 table 是一个矩阵，如果 M(i, j) = 'Y' 表示第 i 个盒子里有第 j 个盒子的信息，打开第 i 个盒子可以知道它是否为空, 如果 M(i, j) = 'N' 表示盒子 i 中没有关于盒子 j 的信息。 想象一下 Mr.X 使用 table 以最佳方式打开盒子（即他打开盒子的次数越少越好）。现在计算在不打开空盒子的情况下找到空盒子的概率。 注：所有盒子为空或不为空的概率相同

示例 1：

YYYYY
NYNNN
NNYNN
NNNYN
NNNNY

概率：0.8

示例 2：

YYNNY
NYNNY
NNYYY
NNNYY
NNNNY

概率：0.6

希望有人能帮助我。 非常感谢。

更新： 做到最好意味着尽可能少地打开他不知道的盒子（即，如果你知道它，你可以简单地打开它。）。

Answer 1

构建一个有向图，使每个框都是一个顶点，如果框 i 包含关于框 j 和 i!=j 的信息，则存在从 i 到 j 的边。

您现在正在寻找从中可以到达所有其他顶点的最小顶点数，可以找到此问题的解决方案here。

为了找到空盒子，您必须打开与上面找到的最小顶点数一样多的盒子，因此概率为 1-(最小顶点数)/(#boxes)

请注意，如果有一个盒子只指向它自己，我们不必打开它，因为我们可以先打开所有其他盒子，如果没有找到空盒子，我们知道它是最后一个，如果有这样一个盒子那么概率实际上更高 1/#boxes.

感谢您的帮助Paul。