Geo*_*ery 8 algorithm r mathematical-optimization
假设我们有一个 5x5 的矩阵，其中填充了 0。
myMatrix <- matrix(rep(0, 25), ncol = 5)
现在，让我们选择 1 到 5 之间的整数三元组。
triplet <- c(1,2,3)
对于这个三元组的所有组合，我们现在在矩阵中添加 1，使用以下函数：
addCombinationsToMatrix <- function(.matrix, .triplet){
indexesToChange <- as.matrix(expand.grid(.triplet, .triplet))
.matrix[indexesToChange] <- .matrix[indexesToChange] + 1
.matrix
}
使用该函数，我们从
myMatrix
[,1] [,2] [,3] [,4] [,5]
[1,] 0 0 0 0 0
[2,] 0 0 0 0 0
[3,] 0 0 0 0 0
[4,] 0 0 0 0 0
[5,] 0 0 0 0 0
到
myMatrix <- addCombinationsToMatrix(myMatrix, triplet)
myMatrix
[,1] [,2] [,3] [,4] [,5]
[1,] 1 1 1 0 0
[2,] 1 1 1 0 0
[3,] 1 1 1 0 0
[4,] 0 0 0 0 0
[5,] 0 0 0 0 0
如果我们选择另一个三胞胎，我们继续
nextTriplet <- 2:4
myMatrix <- addCombinationsToMatrix(myMatrix, nextTriplet)
myMatrix
[,1] [,2] [,3] [,4] [,5]
[1,] 1 1 1 0 0
[2,] 1 2 2 1 0
[3,] 1 2 2 1 0
[4,] 0 1 1 1 0
[5,] 0 0 0 0 0
因此，行列组合表示两个整数在三元组中一起显示的频率：3 和 4 一起显示一次，2 和 3 一起显示两次。
问题：如何选择三元组，使得每个组合（1-2、1-3、1-4...）至少被选择一次并且三元组的数量最小化。
我在这里寻找一种算法来选择下一个三元组。
理想情况下可以扩展到
例子：
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, 1:3)
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, 3:5)
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, c(1,4,5))
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, c(2,4,5))
myMatrix
编辑：只是为了确定：答案不一定是R代码。它也可以是其他语言，甚至是伪代码。
编辑 2：我现在想到，有不同的方法来衡量效率。我的意思是，算法应该尽可能少地迭代。算法很快也很酷，但不是这里的主要目标。
好问题！这出现在调查设计中，您需要几个不同版本的调查，每个版本只包含问题的一个子集，但您希望每对（或 t 元组）问题至少被问过一次。
这称为覆盖设计，是经典集合覆盖问题的变体。正如您在关于该主题的优秀数学堆栈交换帖子中所读到的那样，人们使用符号 C(v, k, t) 表示您需要从 v -element 集（在您的情况下为 v=5），这样整个集合中的每个 t 元素子集（在您的情况下为 t=2）都包含在您选择的子集中之一中。人们已经为许多不同的 (v, k, t) 元组评估了这个函数；例如，请参阅https://ljcr.dmgordon.org/cover/table.html。我们可以从该表中看出 C(5, 3, 2) = 4，其中一种可能的设计如下：
1 2 3
1 4 5
2 3 4
2 3 5
首先，这个问题是 NP-hard 问题，因此所有已知的精确算法将在输入 v、k 和 t 中呈指数级扩展。因此，虽然您可能能够通过枚举或一些更聪明的精确方法（例如整数规划）精确地解决小实例，但随着问题规模变得非常大，您可能需要求助于启发式方法。
这个方向的一种可能性是字典覆盖，如https://arxiv.org/pdf/math/9502238.pdf 中提出的（您会注意到上面链接的站点上的许多解决方案都列出了“lex覆盖”作为建造）。基本上，您按字典顺序列出所有可能的 k 元组：
123
124
125
134
135
145
234
235
245
345
然后，您贪婪地添加覆盖最先发现的 t 元组的 k 元组，使用字典顺序打破联系。
以下是算法在我们的案例中的工作原理：
开始时每个 3-tuple 覆盖了 3 个不同的 2-tuple，所以我们添加，123因为它在字典上是最早的。
这样做之后，12, 13, 和的二元组23已经被覆盖，而所有剩余的二元组都没有被覆盖。许多 3 元组覆盖了另外 3 个 2 元组，例如145和245。我们选择145，因为它是按字典顺序排列的，覆盖14, 45, 和15。
现在我们有4剩余破获2元组- ，24，25，34和35。没有三元组覆盖其中的 3，但有几个覆盖 2，例如234和345。我们选择234字典序最早的。
我们还有两个未发现的 2 元组 -25和35. 我们选择235唯一一个涵盖两者的三元组。
我们最终得到了上面显示的确切解决方案。重要的是，这只是一种启发式方法——它不能保证 4 是覆盖具有 5 个元素的集合中的所有对所需的最小 3 元组数。在这种情况下，Schönheim 的下限（在上面的链接文章中提供了参考）使我们相信，事实上，C(5, 3, 2) 不能小于 4。我们得出的结论是，字典覆盖的解决方案是事实上最优。
您需要进行调整以将每个 t 元组覆盖一定次数 r。一个明显的方法是将每个要覆盖的元组重复“r”次，然后像往常一样运行 lex 覆盖（例如，在上面的第一步中，每个 3 元组将覆盖 9 个 2 元组，其中 r=3）。当然，由于使用了 lex 覆盖，这对于您的整体问题仍然是一种启发式方法。