3

我正在尝试创建一个带有 n 个单独标签的网格，其中每个单元格都标有 n 个标签之一，这样所有标签都与网格中某处的所有其他标签相邻（边缘）（我不在乎在哪里）。标签可以根据需要自由出现多次，我希望网格尽可能小。例如，这是一个包含 1 到 5 个标签的网格：

3 2 4
5 1 3
2 4 5

虽然手动生成对于少量标签来说并不算太糟糕，但对于大量标签来说似乎很难生成合理大小的网格，所以我正在寻找一个程序来生成它们，而不必求助于蛮力搜索。我想这一定是以前调查过的，但我发现的最接近的是 De Bruijn tori，这不是我想要的。任何帮助，将不胜感激。

编辑：感谢 Benawii 提供以下改进的描述：

“给定一个整数 n，生成可能的最小矩阵，其中对于 x≠y 和 x,y ∈ {1,...,n} 的每一对 (x,y)，矩阵中存在一对相邻单元格，其值是 x 和 y。”

4

1 回答 1

0

您可以尝试一个简单的贪心算法。

我不认为我能给你一个严格的数学证明，至少因为这个问题没有严格定义，但算法是相当直观的。

首先，如果您有 1...K 个数字（K 个标签），那么您至少需要 K*(K-1)/2 个相邻单元（连接）才能完全覆盖。大小为 NxM 的矩阵生成 (N-1)*M+(M-1)*N=2*N*M-(N+M) 个连接。

由于您没有在“最小矩阵”下提及您所理解的内容，因此我们假设您指的是该区域。在这种情况下，很明显对于给定的区域，方阵将产生更多的连接，因为它有更多的“内部”单元与其他 4 个相邻。例如，对于区域 16，矩阵 4x4 优于 2x8。“更好”是直观的——更多的联系和更多的机会达到目标。因此，让我们使用目标方阵并在需要时对其进行扩展。上面的公式将变为 2*N*(N-1)。

然后我们可以尝试下面的贪心算法：

  1. 对于输入数 K，找到 N 使得 2*N*(N-1)>K*(K-1)/2。一个简单的学校方程。
  2. 保持邻接矩阵 M，对所有 i 设置 M[i][i]=1，对其余的对设置 0。
  3. 初始化大小为 NxN 的结果矩阵 R，填充“空值”标记，例如 -1。

  4. 从左上角开始并从右向下迭代：

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
                R[i][j];
  5. 对于每个这样的 R[i][j]（现在是 -1），找到一个“最适合”的值。同样，“最适合”是一个直观的定义，在这里我们理解这样一个值，它将有助于一个新的未使用的连接。出于这个原因，创建一组已填充的单元格邻居数 - S，其大小最多为 2（上邻居和左邻居）。然后找到第一个 k 使得 S 中的两个数字 x 的 M[x][k]=0。如果没有这样的数字，则尝试至少一个新的连接，如果甚至没有一个数字，那么两个邻居都被完全覆盖，输入一些数字从这里发现 - 可能是“最坏情况”中的一个 - 这样的 x 其中 Sum(M[x][i]) 是最小的。在任何情况下都有多个可供选择的情况下，您还应该选择“最坏情况”中的一个。
  6. 设置 R[i][j] 的值后，不要忘记用 S - M[R[i][j]][x] = M[x][R[i] 中的数字 x 标记新连接[j]] = 1。
  7. 如果矩阵已填充且 M 中仍有未标记的连接，则将另一行附加到矩阵并继续。如果在结束之前找到所有连接，则删除多余的行。

你可以检查这个算法，看看会发生什么。第 5 步是玩耍的地方，尤其是在相同情况下猜测选择哪一个（几个数字可能处于同样“最坏情况”）。

例子：

对于 K=6，我们需要 15 个连接：

N=4，我们需要 4x4 方阵。理论说 4x3 矩阵有 17 个连接，所以它可能适合，但我们将尝试 4x4。

这是上述算法的输出：

1234
5615
2413
36**

我不确定您是否可以通过 4x3 完成，也许可以... :)

于 2013-08-21T00:29:23.987 回答