Что такое эффективный алгоритм для расчета взвешенных сумм? - PullRequest
Новая
       27

Что такое эффективный алгоритм для расчета взвешенных сумм?

1 голос
/ 24 июня 2019

Я не уверен, что такое технический термин, поэтому термин, который я могу найти, будет оценен.

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

Decision A: 1
Decision B: 3
Decision C: 5
Sum: 9

Что делает код, так это то, что он складывает их вместе, так что вероятность принятия решения А составляет 1/9,3/9 принятия решения B, 5/9 принятия решения C.

Существуют факторы, которые удаляют и добавляют определенные решения из пула.Эти веса не являются фиксированными (например, B может быть 2 для более умных персонажей или разделены на B1 и B2 с их собственным соответствующим весом).

Сейчас я просто выполняю линейный поиск, подобный следующему (в JavaScript): 

let totalWeight = 0;
for (let i = array.length - 1; i >= 0; i--) {
    totalWeight += array[i].weight;
}

// this function rolls a random number from 1 to totalWeight
let r = roll(1, totalWeight); 
let search = 1;
for (let i = 0; i < array.length; i++) {
    let w = array[i].weight;
    if (r >= search && r < (search+w)){
        return array[i];
    }
    search += w;
}

Но это не очень эффективно.Похоже, что здесь может быть алгоритм двоичного поиска, но я не могу думать об этом.Есть идеи?

Ответы [ 2 ]

2 голосов
/ 24 июня 2019

После того, как я посмотрел код, который вы ввели, я думаю, что метод / алгоритм rejection sampling - это то, что вы ищете.Чтобы получить тот же вывод вашего кода, используя выборку отклонения: 

var sample = []; 
for (let i = array.length - 1; i >= 0; i--) {
    for(let j = array[i].weight-1;j>=0;j--) {
        sample.push(i);
    }
}
// this function rolls a random number from 0 to sample.length-1
// which sample.length should be equivalent to your total weight 
let r = roll(0, sample.length-1);
return array[sample[r]];

Приведенный выше код уменьшает сложность времени, но увеличивает сложность пространства.

Если вы пытаетесь реализовать binary search в своем алгоритме без rejection sampling, попробуйте следующий код: 

let totalWeight = 0;
//add one property into your array, call it accumulative_weight or aw

for (let i = array.length - 1; i >= 0; i--) {
    totalWeight += array[i].weight;
    //assign the accumulative_weight property 
    array.aw = totalWeight;
}

// this function rolls a random number from 1 to totalWeight
let r = roll(1, totalWeight); 
let start = 0;
let end = array.length;
let position = "not found";
while(start!=end)
{
    let target = parseInt((end-start)/2);
    if( array[target].aw > r )
        end = target;
    else if ( array[target].aw - array[target].weight < r )
        start = target;
    else
    {
        let position = target;
        break; 
    }
}
return position;

Обратите внимание, что ваш массив должен быть отсортирован.Надеюсь, поможет.

2 голосов
/ 24 июня 2019

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

Здесь - список алгоритмов для выполнения этой задачи.

...