Эффективное моделирование броска взвешенных кубиков (или обхода взвешенного графика) с частыми обновлениями - PullRequest
Новая
       6

Эффективное моделирование броска взвешенных кубиков (или обхода взвешенного графика) с частыми обновлениями

6 голосов
/ 06 января 2012

У меня есть взвешенный ориентированный граф с плотностью около 20 000 узлов.

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

Я узнал вчера о методе псевдонима для имитации броска взвешенного кубика, который аналогичен выбору одного варианта (каждый узел - один взвешенный кубик, и стороны соответствуют другие узлы). Один бросок очень эффективен, но обновление весов - нет; метод псевдонимов может не подходить, потому что я буду обновлять больше кубиков, чем я буду бросать!

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

Некоторые идеи / заметки:

  • Я могу уменьшать обновления, записывая каждую корректировку веса, а затем фактически обновляя только узел / кубик, когда это необходимо (т.е. непосредственно перед броском). Но я все равно буду предварительно вычислять данные псевдонима один раз для каждого броска.
  • Вместо этого я мог бы просто сохранить график как есть (чтобы обновления были дешевыми) и отказаться от метода псевдонима. Я бы вычислял относительные веса на лету перед каждым броском (здесь работает бинарный поиск).
  • Дополнительным преимуществом вычисления относительных весов на лету является то, что я мог бы вычленить «глобальный вес» для каждого узла, чтобы еще больше сократить обновления. Тогда неправильный выбор приведет только к двум обновлениям: весу входящего фронта и глобальному весу узла.
  • добавлено : Может быть, есть что-то среднее: способ поддерживать локальные относительные веса в структуре данных (например, метод дерева или псевдонима), а затем во время каждого броска объединять их с «глобальными весами» на летать.

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

1 Ответ

1 голос
/ 06 января 2012

Я думаю, что вы можете сделать это со сложностью log (k), где k - количество граней в кости.

для одного конкретного узла, пусть p1, p2, ..., pk - относительные вероятности.Пусть p1 + p2, ..., + pk = p.

Построить древовидную структуру с этими относительными вероятностями в виде листьев.родитель каждого неконечного узла является суммой относительных вероятностей их потомков.Чтобы «бросить кубик», нарисуйте случайное значение от 0 до p и следуйте по нему через дерево.Если вы хотите обновить относительную вероятность поверхности кости, просто измените значение соответствующего листа и распространите его вверх по дереву.

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

Это очень простое описание решения, и дайте мне знать, еслиВам нужно полное описание.Я уверен, что это работает, но не уверен, что это достаточно эффективно для вас.

Подводя итог, этот алгоритм требует: 1. Только одно случайное число между 0 и p 2. O (log (k))сложность «бросить кубик» (т.е. найти следующий узел), где k - количество граней в кости 3. O (log (k)), чтобы «обновить кубик» данного узла.Если есть m ребер от исходного узла, то сложность O (log (k1)) + O (log (k2)) ... O ((km)), где k1, k2, ... km - связность смежныхузлы. 

====Tree Example====

Если в кости 4 грани и относительные вероятности 1:50, 2:80, 3:20, 4:70, постройте дерево следующим образом: 

          220
       /       \
    130         90
   /   \      /    \
 50    80    20    70
  |    |     |      |
  1    2     3      4

Создайте случайное число v от 0 до 220. Если это v = 100: выберите левый маршрут (с 100 <130), а затем выберите правильный маршрут (с 100> 80) и обновите v = v-80.= 20. Так как мы находимся на листе, объявляем o / p, т.е. 2

Если v = 210: слева и v = v-130 = 80, слева v = v-70 = 10, возврат листа = 4

Если 4 изменится на 60, изменится с 70 на 60, с 90 на 80 и с 220 на 210. 

==== Lazy update variation ====

При изменении весов не обновляйте дерево немедленно.Вместо этого просто пометьте его как «грязный вес», подождите, пока вам не потребуется сделать прогноз на этом конкретном узле.

Когда вам нужно сделать прогноз на конкретном узле и если некоторые из весовых коэффициентов являются грязными, либоа.обновить дерево только с грязными узлами или б.обновить все дерево.Если количество грязных весов равно t, а количество полных весов k, если t * log (k)

...