Eu tenho, por exemplo, esta tabela
+ ----------------- + | frutas | peso + ----------------- + | maçã 4 | laranja 2 | limão | 1 | + ----------------- +
Eu preciso devolver uma fruta aleatória. Mas a maçã deve ser colhida 4 vezes mais que o limão e 2 vezes mais que a laranja .
Em um caso mais geral, deve ser f(weight)
muitas vezes frequente.
O que é um bom algoritmo geral para implementar esse comportamento?
Ou talvez haja algumas jóias prontas em Ruby? :)
PS:
Eu implementei o algoritmo atual no Ruby https://github.com/fl00r/pickup
algorithms
ruby
math
random
fl00r
fonte
fonte
Respostas:
A solução conceitualmente mais simples seria criar uma lista em que cada elemento ocorra tantas vezes quanto seu peso, para que
Em seguida, use as funções que você tem à sua disposição para escolher um elemento aleatório dessa lista (por exemplo, gerar um índice aleatório dentro do intervalo apropriado). Obviamente, isso não é muito eficiente em termos de memória e requer pesos inteiros.
Outra abordagem um pouco mais complicada seria assim:
Calcule as somas acumuladas de pesos:
Onde um índice abaixo de 4 representa uma maçã , 4 abaixo de 6 uma laranja e 6 abaixo de 7 um limão .
Gere um número aleatório
n
no intervalo de0
atésum(weights)
.n
. A fruta correspondente é o seu resultado.Essa abordagem requer código mais complicado que o primeiro, mas menos memória e computação e suporta pesos de ponto flutuante.
Para qualquer um dos algoritmos, a etapa de configuração pode ser feita uma vez para um número arbitrário de seleções aleatórias.
fonte
Aqui está um algoritmo (em C #) que pode selecionar um elemento ponderado aleatório de qualquer sequência, repetindo-o apenas uma vez:
Isso se baseia no seguinte raciocínio: vamos selecionar o primeiro elemento da nossa sequência como "resultado atual"; em cada iteração, mantenha-o ou descarte-o e escolha o novo elemento como atual. Podemos calcular a probabilidade de qualquer elemento ser selecionado no final como um produto de todas as probabilidades de que ele não seria descartado nas etapas subsequentes, vezes a probabilidade de que ele fosse selecionado em primeiro lugar. Se você fizer as contas, verá que este produto simplifica para (peso do elemento) / (soma de todos os pesos), que é exatamente o que precisamos!
Como esse método itera apenas a sequência de entrada uma vez, ele funciona mesmo com sequências obscenamente grandes, desde que a soma de pesos se encaixe em um
int
(ou você pode escolher algum tipo maior para esse contador)fonte
As respostas já presentes são boas e eu as expandirei um pouco.
Como Benjamin sugeriu, somas cumulativas são normalmente usadas neste tipo de problema:
Para encontrar um item nessa estrutura, você pode usar algo como o pedaço de código do Nevermind. Este pedaço de código C # que eu costumo usar:
Agora para a parte interessante. Qual é a eficiência dessa abordagem e qual é a solução mais eficiente? Meu pedaço de código requer O (n) de memória e é executado em O (n) tempo. Eu não acho que isso possa ser feito com menos de O (n) espaço, mas a complexidade do tempo pode ser muito menor, O (log n) na verdade. O truque é usar a pesquisa binária em vez do loop for regular.
Há também uma história sobre a atualização de pesos. Na pior das hipóteses, a atualização do peso para um elemento causa a atualização de somas cumulativas para todos os elementos, aumentando a complexidade da atualização para O (n) . Isso também pode ser reduzido para O (log n) usando a árvore indexada binária .
fonte
Esta é uma implementação simples do Python:
e
Nos algoritmos genéticos, esse procedimento de seleção é chamado seleção proporcional de aptidão ou seleção de roda de roleta, pois:
Os algoritmos típicos têm complexidade O (N) ou O (log N), mas você também pode executar O (1) (por exemplo , seleção de roleta através de aceitação estocástica ).
fonte
Esta essência está fazendo exatamente o que você está pedindo.
você pode usá-lo assim:
O código acima provavelmente (% 98) retornará 0, que é o índice de 'apple' para a matriz especificada.
Além disso, esse código testa o método fornecido acima:
Dá uma saída algo assim:
fonte