2

假设您有一个nxm 矩阵。在这个矩阵中，您将随机定位四个不同的对象，例如a、b、c、d。每个都会有很多。

现在什么是最好的算法，这样当它们被随机放置时，它们的位置不会发生冲突？

我的方法是：

  1. 随机放置它们
  2. 检查所有物体的位置，如果它们发生冲突，继续移动直到找到一个空白空间？

我只是想知道是否有任何其他有效的解决方案。

4

3 回答 3

1

如果最终目标是填满棋盘，您可以为矩阵上的每个空间选择其上的类型（选择是随机的）。

要添加空格选项，请添加 NO_TYPE 的第五个选项。

如果已知出现次数，请尝试以下操作：

  1. 创建一个大小为n X m（称为L）的列表，其值为 1.. L。

  2. 对于每个外观，从列表中随机选择（类似的东西pos = rand(L)并从列表中删除该值（不要忘记减少L）。

  3. 根据需要多次执行此操作。

于 2015-05-13T11:57:02.100 回答
0

另一个答案的变体，没有创建额外的结构（并且具有更好的时间复杂度）：

假设您有对象 a_1、..、a_K（在您的情况下为 K=4），并且它们中的每一个都必须存在 n_k 次，其中 n_1 + .. + n_K <= n*m。您可以在伪代码中按如下方式填充矩阵：

Initialize X as an empty n*m matrix
Initialize n as a vector of length l with n[l] = n_l
Set N = 0
For i = 1; i <= n; i++
    For j = 1; j <= m; j++
        Draw t at random uniformly on [0,1]
        For l = 1; l <=k; l++
            Set x_l = n[l] / (n*m-N)
            If (t <= x_l)
                Set X[i][j] = a_l
                Set n[l] = n[l]-1
                Escape the loop on l
     Set N = N+1

如果您要放置许多对象，因为您从不拒绝放置，这将比您的方法更好。如果你不这样做，那么你的方法很好。

于 2015-05-13T12:48:50.903 回答
0

如果您有一个算法可以生成一系列随机位置，这些位置不会在您的数组中发生冲突，那么您可以轻松地为a然后b然后c然后d等生成所需的任何位置。

您可以使用此算法完成此操作：

Generate a random prime number p that is greater than n * m
Generate a random number r in the range [0, n * m)
while(need more numbers)
{
    // output a position:
    yield x = r % n, y = r / n

    // generate the next position:
    r = (r + p) % (n * m)
}

这些位置永远不会重叠，因为 p 和 n * m 之间没有公因数。它将在 n * m 上产生一个完整的循环

有关如何生成随机素数，请参阅此 StackOverflow 问题：

在 C/C++ 中生成 2 个限制之间的随机素数

如果 p 是素数，那么它将是与 n * m 互素的

另请参阅此问题：

如何随机迭代一个大范围？

于 2015-05-13T13:36:48.867 回答