Взвешенная случайная карта

Question

Предположим, у меня большой двумерный массив значений в диапазоне [0,1], где 0 означает "невозможно", а 1 означает "очень вероятно".

Как выбрать случайный набор точек вэтот массив в соответствии с вероятностями, описанными выше?

Answer 1

Один из способов взглянуть на проблему - на данный момент игнорировать тот факт, что вы имеете дело с двумерной сеткой. Что у вас есть набор взвешенных предметов. Стандартный способ случайного выбора из такого набора:

1. сумма весов, назовите сумму s
2. выберите равномерное случайное значение 0 <= u < s
3. перебирайте элементы, сохраняя промежуточную сумму t весов предметов, которые вы изучили
4. как только t >= u, выберите предмет, который вы сейчас просматриваете (тот, чей вес вы только что добавили).

Это можно изменить, чтобы сделать множественный выбор без замены, добавив следующие шаги:

• После каждого выбора вычитайте вес выбранного элемента из s (если ваши веса - это числа с плавающей запятой, а стабильность - проблема, вы, возможно, предпочтете пересчитать ее с нуля, хотя бы изредка).

• повторите с 2, но на шаге 3 пропустите элементы, которые были ранее выбраны.

Если суммирование весов невозможно или нежелательно (что может быть, если ваш массив особенно велик), существуют другие варианты. Первое, что приходит на ум, это выборка отклонения, которая является довольно широкой темой, поэтому я просто отсылаю вас к Google и Википедии по этому вопросу, поскольку их охват довольно хороший.

EDIT: забыл вернуться к тому факту, что у вас есть 2D-массив. Вы можете значительно ускорить процесс, предварительно вычислив (в стиле MIPMAP) суммы весов иерархии регионов на карте, поэтому вы можете быстро перейти к местоположению фактического выбранного веса.

Answer 2

код:

  count = 0
  maxPointsInSet = 100
  foreach(point in array){
      if(randomWithChacnce(point.value))) {
         addToSet(point)
         count++
      }
      if(count == maxPointsInSet)
         break;
  }

  function randomWithChacnce(int num){
    random = a randomized number between 0 to 1 // or random from 1 to 100 num*100
    if(num >= random)
     return true;
    return false
  }

если вам это нужно на каком-то конкретном языке, просто спросите меня