Q1

表格中为一个恶搞的 bingo 游戏，请问你知道他表达出的 bingo 游戏的形式和规则是什么吧。其具体内容含意仅供娱乐和参考，可以不用理会。

Bingo游戏的形式和规则通常是这样的：

• 游戏板：游戏板上有一个5x5的方格矩阵，每个格子里写着一项任务或特征。
• 标记：参与者需要根据自身的实际情况或经历来标记这些方格，如果某一项描述符合自己就可以标记该格子。
• 达成bingo：当标记的格子在一行、列或对角线连成一条直线时，参与者就达成了bingo。

Q2

此表格提出了 25 个答案只能填写是或否的问题，在任意一行或一列中全部填写了「是」选项即完成 bingo 的玩家（或者受试者）将被鉴定为某种属性（或者说表格的结果呈阳性），反之，如果答卷的受试者不能在任意一行或列中全部填写是，则被鉴定为阴性。

这么来看，这种 bingo 形式其实可以是一种根据 25 个二元特征（是/否）对受试者进行二分类的行为。

这种形式类似于一种简单的逻辑测试，通过回答一组二元问题，来确定受试者是否符合某种特定的分类标准。这种方法虽然简单，但在某些情境下可以有效地进行快速分类。

Q3

现在我需要根据以上的 bingo 形式为问卷寻找优化。我首先获取了一大批人（M 个）的分类属性（即是阴性还是阳性），以及这 M 个人对于已经设计好的 25 个问题的回答（即「是」或者「否」）。显然上述材料构成一个数据集。对于 25 个问题的任意一种 5 × 5 网格排序，都能构成一个 bingo 问卷。在任意一个 bingo 问卷中，数据集中受试者的回答达成 bingo 与否构成预测属性，其与实际的分类属性相比较都可以得到一个混淆矩阵（即 TP, FP, TN, FN），就可以计算得到 accuracy、precision 、recall 等分类指标。

最后，这 25 个问题显然存在一个最好的 5 × 5 网格排序即一个 bingo 问卷，就数据集而言它的准确率不低于其他任何问卷。

这个优化问题可以被形式化为一个组合优化问题，目标是在所有可能的5×5网格排序中找到一个最优解，使得分类指标最大化。

解决这个问题的方法可以包括：

• 暴力搜索：遍历所有可能的5×5网格排序，计算每种排序的分类指标，找到最优解。这种方法在计算上可能比较昂贵，因为5×5网格排序的可能性为25!（25的阶乘）。即 15,511,210,043,330,985,984,000,000。
• 启发式算法：使用遗传算法、模拟退火等启发式方法进行搜索，可能在较短时间内找到接近最优的解。
• 机器学习方法：使用机器学习的方法，如优化算法或深度学习，自动学习最佳排序。

Q4

显然，我们要枚举的是一种 5×5 个问题的排列，这种排列还存在一些旋转或翻转的对称性。请问如何针对这样的排列进行优化搜索？

为了针对5×5问题排列的对称性进行优化搜索，你可以采取以下方法：

• 消除对称性：在枚举排列时，通过规则或算法去除对称排列，以减少搜索空间。例如，你可以选择只枚举某一类特定排列（如左上角固定某个问题），然后通过旋转和翻转操作生成其他对称排列，并忽略这些对称排列。
• 启发式搜索算法：使用启发式搜索算法（如遗传算法、模拟退火等），在搜索过程中考虑对称性。例如，在生成新排列时，可以直接跳过已经考虑过的对称排列。
• 局部搜索算法：局部搜索算法（如爬山算法、禁忌搜索）可以从一个初始解开始，通过小范围的调整（如交换两个问题的位置）来改进当前解，同时通过记录已访问的排列来避免重复计算对称排列。

Q5

因为这是在对排列进行优化，它不像一些机器学习问题一样对公式中的连续参数进行优化。如果是要优化公式中的连续参数，假设共 N 个，完全可以将搜索空间定义为一个连续的 N 维空间，在那之中去寻找最优解，这可以通过连续空间的连续性、临近性、导数等工具来进行优化。

对排列进行优化的时候，搜索的全体是所有的排列。这可能就需要研究排列的特征、怎么样的排列是相似的等等，请问离散数学有没有专门研究这部分的内容呢？它大致要研究什么问题，有什么主要的工具呢？

排列空间的坐标表示：

• 一个长度为 n 的排列可以表示为一个由 n 个元素组成的向量。例如，排列 [3,1,2][3, 1, 2][3,1,2] 可以表示为向量 (3,1,2)(3, 1, 2)(3,1,2)。

研究两个排列之间的相似性度量：

• Hamming 距离：两个排列之间的位置上元素不同的个数。例如，排列 [1,2,3] 和 [2,1,3] 的 Hamming 距离是 2，因为前两个位置的元素不同。
• Kendall tau 距离：通过计算排列中元素对之间的逆序数来度量两个排列的距离。例如，排列 [1,3,2] 和 [3,1,2] 的 Kendall tau 距离是 2，因为 (1,3) 和 (3,2) 这两对元素在两个排列中的顺序不同。
• Spearman’s footrule 距离：两个排列之间的位置差的绝对值之和。例如，排列 [1,3,2] 和 [3,1,2] 的 Spearman’s footrule 距离是 ∣1−3∣+∣2−1∣+∣3−2∣=4。

排列空间中的优化搜索：

• 邻域定义：在启发式搜索算法中（如模拟退火、爬山算法等），可以定义邻域结构，即从一个排列到另一个排列的简单变换。例如，交换两个元素的位置（邻近交换）、将某个元素移动到另一个位置等。

Q6 上面这个寻找最优化的 bingo 问卷排列的问题是一个 np 难问题吗？

你提到的寻找最优化的bingo问卷排列的问题确实是一个NP难问题。