Порядок независимого взвешенного случайного выбора

Question

Допустим, у меня есть пул элементов, которые нужно выбрать случайным образом.

И я использую для этого простой алгоритм взвешенного выбора:

1. Вычислить сумму веса элементов;
2. Выберите случайное число от 0 до суммы веса;
3. Перебирайте элементы и уменьшайте его по весу, выбирайте элемент, когда <0 </li>

А пока что ограничение алгоритм распространения обновляет пул доступных элементов.

• Например, скажем, у нас есть сетка N на N, каждая ячейка может выбрать число.
• Выбор осуществляется посредством взвешенного выбора , используя алгоритм, описанный выше.
• Когда ячейка выбирает свой номер, она также ограничивает доступные номера соседних ячеек, используя некоторые правила.

И вот моя проблема:

• Скажем, ячейки A и B являются соседями.
• Сначала скажем, оба они могут выбирать из пула чисел.
• Но если A или B являются определяется, в другой ячейке будет меньшее число для выбора.
• Таким образом, даже для одного и того же ввода случайного числа взвешенный выбор может дать другой результат (потому что сумма весов и вероятность элемента изменились).
• Таким образом, процесс выбора не зависит от порядка, даже если случайное число не зависит от порядка.

Как мы можем гарантировать, что результаты A и B являются случайными и независимыми, сохраняя при этом возможность распространять ограничения? (Возможно ли это в моем случае?)

Обновление:

Алгоритм, на котором я основываю свою идею, - WaveFunctionCollapse , из-за Как это работает, мы не можем гарантировать порядок наблюдения, потому что он всегда выбирает ячейку с наименьшей энтропией.

Я считаю, что мое начальное ограничение изменяет результат непредсказуемым образом, потому что доступная энтропия теперь другая , поэтому порядок наблюдения меняется, и результат наблюдения для той же ячейки также изменяется.

Answer 1

Вы можете попробовать назначить отдельную таблицу весов для каждой ячейки. В этом случае случайный выбор происходит в обход, где на каждом проходе вы выбираете случайное число для каждой ячейки, а затем удаляете выбранное число из рассмотрения в каждой ячейке. (Подумайте, как обновляются ячейки в «Игре жизни» Конвея.) Однако это может занять много памяти, особенно если есть много элементов на выбор или размер сетки большой. Пожалуйста, попробуйте эту идею; если это недостаточно быстро, измерьте, чтобы найти узкие места, и соответствующим образом отредактируйте свой вопрос.