Здесь я попытаюсь начать с неэффективной процедуры, которая удовлетворяет одному виду случайности, и заменить ее более эффективной.
1) Неэффективно - я предполагаю, что у вас есть список свойств и связанных с нимирасходы.Рассмотрим все возможные наборы свойств - если существует N свойств, таких наборов будет 2 ^ N.Из этого рассмотрим набор наборов свойств, которые вписываются в ваш бюджет.Из этого меньшего (но, вероятно, все еще огромного) набора выберите случайный набор свойств.
2) Возможная реализация.Я предполагаю, что все затраты представляют собой целые числа умеренного размера, или что вы можете принять неточность, связанную с округлением их до этого.Теперь вы можете создать массив A, где A [i] - это количество способов создания совокупной стоимости i.При рассмотрении 0 свойств A [0] = 1. Теперь рассмотрим свойство стоимости 3. Единственный ненулевой элемент A на данный момент - это A [0].Это дает вам другой способ генерировать A [0 + 3 = 3], поэтому вы можете установить A [3] = 1 + A [0].Рассматривая каждое свойство по очереди, вы можете установить A [i] = количество способов, которыми вы можете создать набор стоимости i, используя эти свойства.
После того, как вы построите массив, рассмотрите каждое свойство вОбратимся, начиная со стоимости B. Выберите точную стоимость C путем выборки из затрат> = B с вероятностью, пропорциональной числу способов создания набора этих затрат.Теперь рассмотрим каждое свойство по очереди.Если дано свойство стоимости c, если оно больше текущей стоимости C, откажитесь от него.Если нет, рассмотрите A [C] и A [C - c] и выберите между ними с вероятностью, пропорциональной их размеру.Если вы выбираете A [C], вы отказываетесь от собственности.Если вы выберете A [C - c], вы включите свойство в свой случайный набор.
Возможно, есть способ сделать что-то эквивалентное без округления до целых чисел, используя http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm - возможно, я сижуи об этом позже.
Да - это довольно легко выпадает из Метрополис-Гастингс.По сути, вы начинаете с любого допустимого набора, например с нулевого набора, запускаете большое количество шагов Метрополиса-Гастингса и надеетесь, что результат будет достаточно хорошо перемешан, и результирующий набор будет в значительной степени случайным в соответствии с вашим распределением.Если вам нужна еще одна случайная выборка, снова выполните ее через множество шагов MH.
На языке записи в Википедии P (x ') = P (x_t) = 1. Для вычисления Q (x_t; x') вам нужно решить, как перейти от набора к набору.Если вы упорядочите свойства в отсортированном порядке стоимости, вы можете рассчитать, учитывая общую стоимость набора, сколько из оставшихся свойств вы можете себе позволить добавить к нему - например, выполнить двоичный анализ, чтобы определить количество свойств, которыедостаточно дешевы и используют какое-то сбалансированное дерево для подсчета количества уже выбранных таких свойств.Таким образом, вы можете определить количество различных свойств, которые вы можете добавить к текущему набору, и, конечно, вы также можете вычесть любое из существующих свойств.Если шаг состоит в том, чтобы либо добавить, либо вычесть одно свойство, вы знаете, как много разных способов уйти от x_t, и вы можете сделать аналогичный расчет для x '.Таким образом, Q (x '; x_t) равно 1 / (количество выходов из x_t), а Q (x_t; x') равно 1 / (количество выходов из x '), и как только вы решили, двигаться или нет,если вы решили переехать, вы выбираете один из этих способов из x_t наугад.