Simulez efficacement des dés pondérés roulants (ou traversant un graphique pondéré), avec des mises à jour fréquentes

J’ai un graphe orienté pondéré qui est dense avec environ 20 000 nœuds.

  1. Étant donné un nœud dans le graphique, je choisis un nœud adjacent de manière aléatoire avec une probabilité liée aux poids relatifs.
  2. Après chaque choix, je reçois des informations sur le choix, qu’il soit bon ou mauvais, et met à jour le réseau. Par exemple, après un mauvais choix, je diminue le poids de toutes les arêtes pointant vers le nœud choisi.

Hier, j’ai appris la méthode du pseudonyme pour simuler le laminage d’un dé pondéré, ce qui revient à faire un choix (chaque nœud est un dé pondéré et les côtés correspondent à d’autres nœuds). Un rouleau est très efficace, mais la mise à jour des poids ne l’est pas; la méthode des alias peut ne pas être appropriée car je mettrai à jour plus de dés que je ne jetterai!

Quelle structure de données dois-je utiliser, ce qui permet des mises à jour fréquentes, et quel algorithme correspondant est le mieux pour faire les choix?


Quelques idées / notes:

  • Je peux diminuer les mises à jour en enregistrant chaque réglage de poids, puis en mettant à jour réellement un nœud / dé lorsque cela est nécessaire (c’est-à-dire directement avant un lancer). Mais je serais toujours en train de pré-calculer les données d’alias une fois pour chaque rôle.
  • Au lieu de cela, je pourrais simplement stocker le graphique tel quel (pour que les mises à jour soient bon marché) et renoncer à la méthode des alias. Je calculerais les poids relatifs à la volée avant chaque rouleau (la recherche binary fonctionne ici).
  • Un autre avantage du calcul des poids relatifs à la volée est que je pouvais prendre en compte le “poids global” pour chaque nœud afin de réduire davantage les mises à jour. Ensuite, un mauvais choix ne produirait que 2 mises à jour: le poids du bord entrant et le poids global du nœud.
  • ajouté : Peut-être y a-t-il quelque chose entre les deux: un moyen de maintenir les poids relatifs locaux dans une structure de données (par exemple, une méthode tree ou alias), puis de les fusionner à chaque volée avec des “poids globaux”.

La vérité est que, dans la pratique, je n’ai pas besoin de faire des choix très souvent (pas plus d’une fois par minute), je n’ai donc pas besoin de la solution la plus efficace. Mais il s’agit d’un projet secondaire amusant et je suis intéressé par la recherche d’une solution théoriquement optimale.

Je pense que vous pouvez le faire avec la complexité de log (k) où k est le nombre de faces dans les dés.

pour un noeud particulier, p1, p2, …, pk sont les probabilités relatives. Soit p1 + p2, …, + pk = p.

Construisez une arborescence avec ces probabilités relatives sous forme de feuilles. le parent de chaque nœud non-feuille est la sum des probabilités relatives de leurs enfants. Pour “lancer un dé”, tracez une valeur aléatoire comprise entre 0 et p, et suivez-la dans l’arbre. Lorsque vous souhaitez mettre à jour la probabilité relative d’une face de dé, modifiez simplement la valeur du nœud feuille correspondante et propagez-la dans l’arborescence.

De cette manière, vous pouvez choisir une valeur aléatoire avec un nombre aléatoire avec les étapes de log (k) nécessaires pour trouver la feuille correspondant au nombre aléatoire. Lorsque vous mettez à jour une feuille, il faut un temps de log (k) pour mettre à jour l’arbre.

Ceci est une description très simple de la solution et laissez-moi savoir si vous avez besoin d’une description complète. Je suis sûr que cela fonctionne, mais je ne suis pas sûr que cela soit suffisamment efficace pour vos besoins.

pour résumer, cet algorithme a besoin de: 1. Un seul nombre aléatoire entre 0 et p 2. O (log (k)) complexité pour “lancer les dés” (c’est-à-dire trouver le nœud suivant) où k est le nombre de faces dans les dés 3. O (log (k)) pour “mettre à jour les dés” d’un nœud donné. S’il y a m arêtes par rapport au nœud d’origine, la complexité est O (log (k1)) + O (log (k2)) … O ((km)) où k1, k2, … km représentent la connectivité des réseaux adjacents. nœuds.

====Tree Example==== 

Si le dé a 4 faces et que les probabilités relatives sont 1:50, 2:80, 3:20, 4:70, construisez l’arbre comme suit:

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

Générez un nombre aléatoire v compris entre 0 et 220. S’il s’agit de v = 100: prenez la route de gauche (depuis 100 <130) puis prenez la bonne route (depuis 100> 80) et mettez à jour v = v-80 = 20. nous sums à la feuille déclarer o / p ie 2

Si v = 210: à gauche et v = v-130 = 80, à gauche v = v-70 = 10, feuille de retour = 4

Si 4 devient 60, changez 70 à 60, 90 à 80 et 220 à 210.

 ==== Lazy update variation ==== 

Chaque fois que les poids sont modifiés, ne mettez pas l’arborescence à jour immédiatement. Au lieu de cela, marquez-le simplement comme un “poids sale”, attendez de devoir faire une prédiction à partir de ce nœud particulier.

Lorsque vous devez effectuer une prédiction à partir d’un nœud particulier et si certaines pondérations sont sales, procédez comme suit: a. mettre à jour l’arborescence avec uniquement des nœuds sales ou b. mettre à jour l’arbre entier. Si le nombre de poids sales est t et le nombre de poids totaux k, si t * log (k)