Qual è un buon algoritmo per una distribuzione casuale e irregolare di una quantità fissa di una risorsa?

Question

Qual è un buon algoritmo per una distribuzione casuale e irregolare di una quantità fissa di una risorsa?

Naviga le tue risposte

#1 da (6 voti)
#2 da (0 voti)

4

Problema

Ho X , un numero intero positivo, di qualche risorsa, R .

Ci sono N obiettivi potenziali.

Voglio distribuire tutto R ai N target in qualche modo "interessante".

"Interessante" significa:

Alcuni target potrebbero non ottenere alcun R .
Raramente dovrebbe essere quasi uniforme (con una maggioranza di target vicina a X / N della risorsa).
Ci dovrebbe essere almeno una piccola possibilità che un bersaglio ottenga tutto R .

Soluzioni errate

L'approccio ingenuo sarebbe scegliere un target casuale e assegnargli una R e ripetere X volte. Ciò comporterebbe un approccio troppo uniforme.

L'idea successiva è scegliere un numero casuale tra 1 e X e assegnarlo a un bersaglio casuale. Ne risulta un numero troppo grande (almeno X / 2 in media) assegnato a un target.

Domanda

Questo algoritmo verrà usato frequentemente e voglio che la distribuzione sia interessante e irregolare in modo che la sorpresa non svanisca per gli utenti.

Esiste un buon algoritmo per qualcosa tra questi due approcci, che corrisponde alla definizione di interessante sopra?

random algorithms

posta Nicole 05.04.2012 - 01:08

fonte

2 risposte

Leggi altre domande sui tag random algorithms

Quali passi posso fare per evitare problemi di codifica dei caratteri in un'applicazione web? Di quale cattiva pratica è necessario chiamare le funzioni per ordinare un segno?

score 6 · Answer 1

Combina i due approcci. Distribuisci una quantità casuale della risorsa a un utente casuale, quindi ripeti. Ad ogni passo, scegli una parte della risorsa rimanente (1 / x, con x un numero in virgola mobile compreso tra 2 e 10) e consegnala a uno qualsiasi dei giocatori (incluso un giocatore che ha già ricevuto parte della risorsa). Quando la risorsa rimanente lasciata a disposizione diventa abbastanza bassa (ad esempio, sotto 1 / 2N a sinistra), consegnala semplicemente senza ulteriore suddivisione.

Ciò consente la possibilità che quasi tutte le risorse vadano allo stesso giocatore (1/2 distribuite due volte a un giocatore), divise in modo uniforme e una distribuzione simile a un frattale. La maggior parte delle volte ci saranno squilibri significativi nella risorsa disponibile per ciascun utente. Puoi giocare con il punto limite e l'intervallo di suddivisione (2..10, 1..20, 3..5) per vedere come varia la distribuzione delle risorse finché non trovi un risultato che ti piace.

Inoltre, i parametri di suddivisione potrebbero essere essi stessi flessibili ... da A..B, e A e B sono scelti a caso. Se entrambi sono bassi (da 1,2 a 2,5), un numero molto esiguo di utenti otterrà la maggior parte delle risorse. Se entrambi sono alti (da 8.1 a 11.0), la distribuzione sarà abbastanza uniforme. Ciò consente anche di ottimizzare la granularità della distribuzione delle risorse come opzione di configurazione.

score 0 · Answer 2

IMHO ha bisogno di capire quale distribuzione di probabilità vuoi (sembra che la normale distribuzione risponda alle tue esigenze). Puoi lasciare che la mediana sia R (sceglierla in modo casuale ogni volta) e puoi anche cambiare la varianza ogni volta. Se la velocità non è così importante, il modulo casuale di Python può generare numeri casuali in base alla distribuzione normale. Altrimenti, google per come convertire la distribuzione flat nella distribuzione normale.