Структура данных для загруженных костей? - PullRequest
Новая
       31

Структура данных для загруженных костей?

122 голосов
/ 17 февраля 2011

Предположим, что у меня есть n-сторонний загруженный кристалл, где каждая сторона k имеет некоторую вероятность p k выпадения, когда я его бросаю.Мне любопытно, есть ли хороший алгоритм для статического хранения этой информации (то есть для фиксированного набора вероятностей), чтобы я мог эффективно моделировать случайный бросок кубика.

В настоящее время у меня есть O (lgо) решение этой проблемы.Идея состоит в том, чтобы сохранить таблицу совокупной вероятности первых k сторон для всех k, чтобы они сгенерировали случайное действительное число в диапазоне [0, 1), и выполнить двоичный поиск по таблице, чтобы получить самый большой индекс, совокупный показатель которогозначение не больше выбранного значения.Мне скорее нравится это решение, но кажется странным, что среда выполнения не учитывает вероятности.В частности, в экстремальных случаях, когда всегда появляется одна сторона или значения распределяются равномерно, можно сгенерировать результат скручивания в O (1), используя наивный подход, хотя мое решение все равно будет выполнять логарифмическое много шагов.

Есть ли у кого-нибудь какие-либо предложения о том, как решить эту проблему таким образом, который каким-то образом "адаптивен" во время выполнения?

РЕДАКТИРОВАТЬ : на основе ответов на этот вопросЯ написал статью, описывающую многие подходы к этой проблеме , а также их анализ.Похоже, что реализация метода псевдонима Vose дает Θ (n) время предварительной обработки и O (1) время на бросок матрицы, что действительно впечатляет.Надеемся, что это полезное дополнение к информации, содержащейся в ответах!

Ответы [ 3 ]

111 голосов
/ 17 февраля 2011

Вы ищете метод псевдонима , который предоставляет метод O (1) для генерации фиксированного дискретного распределения вероятностей (при условии, что вы можете получить доступ к записям в массиве длины n впостоянное время) с однократной настройкой O (n).Вы можете найти это документально в главе 3 (PDF) из "Неоднородная генерация случайных вариаций" Люка Деврой.

Идея состоит в том, чтобы взять вашвероятности p k и производят три новых массива из n элементов: q k , a k и b k .Каждое q k - это вероятность между 0 и 1, а каждый a k и b k - это целое число от 1 до n.

Мы генерируем случайные числа от 1 до n, генерируя два случайных числа r и s от 0 до 1. Пусть i = floor (r * N) +1.Если q i i , в противном случае вернуть b i .Работа с методом псевдонимов заключается в выяснении того, как получить q k , a k и b k .

.
4 голосов
/ 17 февраля 2011

Используйте сбалансированное двоичное дерево поиска (или двоичный поиск в массиве) и получите O (log n) сложности. У каждого узла должен быть по одному узлу, а ключами должен быть интервал, который запустит этот результат. 

function get_result(node, seed):
    if seed < node.interval.start:
        return get_result(node.left_child, seed)
    else if seed < node.interval.end:
        // start <= seed < end
        return node.result
    else:
        return get_result(node.right_child, seed)

Преимущество этого решения в том, что оно очень простое в реализации, но все еще имеет хорошую сложность.

3 голосов
/ 17 февраля 2011

Я думаю о гранулировании вашей таблицы.

Вместо того, чтобы иметь таблицу с кумулятивным значением для каждого значения кубика, вы можете создать целочисленный массив длины xN, где x в идеале - большое число, которое нужно увеличить.Точность вероятности.

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

Может быть, я мог бы объяснить проще на примере:

Используя три кубика: P (1) = 0,2, P (2) = 0,5, P (3) = 0,3

Создайте массив, в этом случае я выберу простую длину, скажем, 10. (то есть x = 3.33333) 

arr[0] = 1,
arr[1] = 1,
arr[2] = 2,
arr[3] = 2,
arr[4] = 2,
arr[5] = 2,
arr[6] = 2,
arr[7] = 3,
arr[8] = 3,
arr[9] = 3

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

Этот метод может потерять точность, но увеличения x и точности будет достаточно.

...