Избегайте конфликта позиций в матричном алгоритме

Предположим, у вас есть матрица n x m. В этой матрице вы будете случайным образом размещать ЧЕТЫРЕ различных объекта, скажем, a, b, c, d. Каждого будет много.

Каков наилучший алгоритм, чтобы при случайном размещении их позиции не конфликтовали?

Мой подход будет заключаться в следующем:

  1. Расположите их случайным образом
  2. Проверить все позиции объекта, и если они конфликтуют, продолжать двигаться, пока не будет найдено пустое место?

Мне просто интересно, есть ли другое эффективное решение.


algorithm matrix nearest-neighbor neighbours
person VideoGamingIOs    schedule 13.05.2015    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Если конечная цель состоит в том, чтобы заполнить доску, вы можете просто выбрать для каждого места в матрице, какой тип будет на нем (выбор случайный).

Чтобы добавить опцию пустого пространства, добавьте пятую опцию NO_TYPE.

Если количество появлений известно, попробуйте следующее:

  1. Создайте список размером n X m (назовите его L) со значениями 1..L.

  2. Для каждого появления выберите случайным образом из списка (что-то вроде pos = rand(L) и удалите это значение из списка (не забудьте уменьшить L).

  3. Сделайте это столько раз, сколько необходимо.

person shapiro yaacov    schedule 13.05.2015
comment
А что, если у вас есть фиксированная сумма, например, если а должно присутствовать пять раз? - person VideoGamingIOs; 13.05.2015

arrow_upward
0
arrow_downward

Вариант другого ответа без создания дополнительной структуры (и с большей временной сложностью):

Предположим, что у вас есть объекты 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

Это будет работать лучше, чем ваш подход, если у вас есть много объектов для размещения, поскольку вы никогда не отказываетесь от размещения. Если вы этого не сделаете, то ваш подход в порядке.

person vib    schedule 13.05.2015

arrow_upward
0
arrow_downward

Если у вас есть алгоритм, который может генерировать последовательность случайных позиций, которые не конфликтуют в вашем массиве, вы можете легко сгенерировать столько позиций, сколько вам нужно для 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++ между двумя пределами

Если p простое, то оно будет взаимно простым с n * m

См. также этот вопрос:

Как я могу случайным образом перебирать большой диапазон?

person samgak    schedule 13.05.2015