algorithm - 在说谎者-真相出纳员问题中解决说谎者的上限和下限

Question

我正在尝试解决说真话者/说谎者的问题。对类(class)进行调查。答案采用矩阵 A 的形式，其中 A[i][j] 表示第 i 个学生对第 j 个学生的回答。如果那个字符是“L”——这意味着他/她是个骗子；如果是“T”——则表示该学生是一位讲真话的人。

Truth-Speaker ('T'):他/她的所有回复都是真实的。骗子 (‘L’) : (S)他至少做出了一次虚假回复。

例如。 1

TLLL  

LTLL                                                                   

LLTL  

LLLT

类包含最少3个最多4个说谎者，3是说谎者的下界，4是上界。

例如。 2

TLTLT 

TTTTT

LLTLL

LLLLL

TLTLT

类包含至少 4 个和最多 4 个说谎者

我不确定如何找到下限和上限，如有任何帮助，我们将不胜感激。

Answer 1

对于您提供的示例，您只需遵循逻辑并查看假设特定人是 T 的结果。通常，您可以设置一个混合整数规划问题。

如果人 i 是 L，则设 x_i=1，如果他是 T，则设 x_i=0。然后根据每个人的陈述创建一个线性函数。例如，从 TLTLT 创建:

f_1 = (x_1) + (1-x_2) + (x_3) + (1-x_4) + (x_5)

您可以看到图案。对于任何可行的分配(即 x 值与人们的陈述之间不存在矛盾的 x 变量的设置)当且仅当 f_1=0 时，您必须具有 x_1=0，并且当且仅当 x_1=1如果 f_1>0，或者，因为一切都是整数，f_1>=1。这相当于 f_i>=x_i 和 f_i<=(N+1)x_i(其中 N 是人数)。所以现在你有了系统:

For all i=1,...,N
    f_i>=x_i
    f_i<=(N+1)x_i
    x_i is 0 or 1

这个系统的每个可行解都对应一个可行的分配，反之亦然。

有了这些约束，只需最小化和最大化 sum x_i 即可获得说谎者数量的下限和上限。