Supprimer des articles d'un ensemble de manière inégale distribuée

Avez-vous envisagé de regarder cela en termes d'une solution de programmation dynamique?

Je pense que vous pourrez peut-être le faire en optimisant sur le nombre de questions disponibles à gauche ouverte à tous les joueurs tels qu'aucun joueur n'a laissé avec zéro question ouverte.

Le lien suivant offre une bonne vue d'ensemble de la construction Programmation dynamique Solutions à ce type de problèmes.

Vous pouvez utiliser un tel algorithme pour résoudre le problème - pouvez-vous choisir au plus t des questions telles que chaque utilisateur a au moins une question à répondre? Je pense que c'est http://fr.wikipedia.org/wiki/set_cover , et je Pensez à résoudre votre problème en général vous permet de résoudre le couvercle défini, alors je pense que c'est NP-complet.

Il y a au moins une relaxation de programmation linéaire. Associer chaque question avec une variable qi dans la plage 0 <= qi <= 1. Choix des questions Qi de telle sorte que chaque utilisateur a au moins x questions disponibles montants disponibles à la contrainte SUM UIJ QJ> = x, qui est linéaire en qj et x, Vous pouvez donc optimiser la fonction objectif x avec les variables linéaires x et qj. Malheureusement, le résultat n'a pas besoin de vous donner entier QJ - considérez par exemple le cas lorsque toutes les paires de questions possibles sont associées à certains utilisateurs et que vous souhaitez que chaque utilisateur puisse répondre au moins 1 question, en utilisant au plus de la moitié des questions. La solution optimale est Qi = 1/2 pour tout i.

(mais donné une source de programmation linéaire, vous pouvez l'utiliser comme lié à http: //fr.wikipedia .org / wiki / sucaire_and_bound ).

Alternativement, vous pouvez simplement écrire le problème et le jeter dans un package de programmation linéaire entier, si vous avez une personne à portée de main.

présentant cela en termes de questions toujours jouables. Je trouverai les questions de 0 à 4 au lieu de 1 à 5, car cela est plus pratique dans la programmation.

void decide_one_question(int question_id
                       , int questions_kept_so_far
                       , upper_bound_on_the_score) {
        if(upper_bound_on_the_score < best_score_so_far) {
            // the upper bound is already too low,
            // therefore, this is a dead end.
            return;
        }
        if(question_id == 5) // .. continue with the rest of the function.

Voici un programme entier. Laissez constante invisible (i, j) code> être 1 code> si lecteur i code> n'a pas vu la question j code> et 0 code> sinon. Laissez la variable conservée (j) code> être 1 code> si question j code> doit être conservé et 0 code> sinon. Laissez la variable score code> être l'objectif.

maximize score                                       # score is your objective
subject to

for all i,  score <= sum_j (unseen(i, j) * kept(j))  # score is at most
                                                     # the number of questions
                                                     # available to player i

sum_j (1 - kept(j)) = 30                             # remove exactly
                                                     # 30 questions

for all j,  kept(j) in {0, 1}                        # each question is kept
                                                     # or not kept (binary)

(score has no preset bound; the optimal solution chooses score
 to be the minimum over all players of the number of questions
 available to that player)

S'il y a trop d'options à la force brute et qu'il existe probablement de nombreuses solutions presque optimales (sonne comme le cas), considère les méthodes de Monte-Carlo.

Vous avez une fonction de fitness clairement définie, alors rendez-vous simplement des affectations aléatoires sur le résultat. Rincer et répéter jusqu'à ce que vous manquiez de temps ou que d'autres critères soient satisfaits.

La question semble d'abord facile, mais après avoir pensé plus loin que vous réalisez la dureté.

L'option la plus simple supprimerait les questions observées par nombre maximum d'utilisateurs. Mais cela ne prend pas le nombre de questions restantes pour chaque utilisateur en considération. Certaines questions peuvent être laissées pour certains utilisateurs après avoir retiré.

Une solution plus complexe comporterait le nombre de questions restantes pour chaque utilisateur après avoir supprimé une question. Vous devez le calculer pour chaque question et chaque utilisateur. Cette tâche peut consommer du temps si vous avez de nombreux utilisateurs et questions. Ensuite, vous pouvez résumer le nombre de questions à gauche pour tous les utilisateurs. Et sélectionnez la question avec la somme la plus élevée.

Je pense qu'il serait sage de limiter le nombre de questions restantes à un utilisateur à une valeur raisonnable. Vous pouvez penser "OK, cet utilisateur a suffisamment de questions à afficher s'il a plus de x questions". Vous en avez besoin, car après avoir supprimé une question, seules 15 questions peuvent être laissées pour un utilisateur actif tandis que 500 questions peuvent être laissées pour un utilisateur de visites rares. Ce n'est pas juste de la somme 15 et 500. Vous pouvez plutôt définir une valeur seuil de 100.

Pour que cela soit plus facile à calculer, vous ne pouvez considérer que les utilisateurs qui ont visionné plus de questions x.

modèles de programmation linéaire.

variante 1. strong> p> xxx pré>

uij code> est 1 Code> Si l'utilisateur i code> n'a pas vu la question j code>, sinon il est 0 code> p>

dij code > Est-ce élément de matrice d'identité ( dij = 1 code> si i = j code>, sinon il est 0 code>) p>

Xj code> est une variable auxiliaire (une pour chaque utilisateur) p>

variante 2. Strong> p> xxx pré>

dans ce cas , Le problème LP est plus simple, mais score code> doit être déterminé par la recherche binaire et linéaire. Définissez la plage de courant sur [0 .. Le moins de questions invisibles pour un utilisateur], définissez «Code> Score code> au milieu de la plage, appliquez l'algorithme INTEGER LP (avec une petite limite de temps). Si aucune solution n'a été trouvée, réglez la plage de [COMMEND .. SCORE CODE>], sinon réglez-le sur [ Score code> .. fin] et poursuivez la recherche binaire. P>

(Éventuellement) Utilisez une recherche binaire pour déterminer la limite supérieure de la solution exacte de la solution code> p>

à partir du meilleur code> Score code>, trouvé par la recherche binaire, appliquez-la entier Algorithme LP avec Score Code>, augmenté de 1, 2, ... (et limiter le temps de calcul si nécessaire). À la fin, vous obtenez une solution exacte, soit une bonne approximation. P>

Voici un exemple de code en C pour GNU GLPK (pour variante 1): p>

#include <stdio.h>
#include <stdlib.h>
#include <glpk.h>

int main(void)
{
  int ind[3000];
  double val[3000];
  int row;
  int col;
  glp_prob *lp;

  // Parameters
  int users = 120;
  int questions = 10000;
  int questions2 = questions - 30;
  double score = 4869.0 + 7;

  // Create GLPK problem
  lp = glp_create_prob();
  glp_set_prob_name(lp, "questions");
  glp_set_obj_dir(lp, GLP_MAX);

  // Configure rows
  glp_add_rows(lp, users + 1);
  for (row = 1; row <= users; ++row)
  {
    glp_set_row_bnds(lp, row, GLP_LO, score, score);
  }
  glp_set_row_bnds(lp, users + 1, GLP_FX, questions2, questions2);

  // Configure columns
  glp_add_cols(lp, questions);
  for (col = 1; col <= questions; ++col)
  {
    glp_set_obj_coef(lp, col, 0.0);
    glp_set_col_kind(lp, col, GLP_BV);
  }

  // Configure matrix (question columns)
  for(col = 1; col <= questions; ++col)
  {
    for (row = 1; row <= users; ++row)
    {
      ind[row] = row;
      val[row] = (rand() % 2)? 1.0: 0.0;
    }
    ind[users + 1] = users + 1;
    val[users + 1] = 1.0;
    glp_set_mat_col(lp, col, users + 1, ind, val);
  }

  // Solve integer GLPK problem
  glp_iocp param;
  glp_init_iocp(&param);
  param.presolve = GLP_ON;
  glp_intopt(lp, &param);

  glp_delete_prob(lp);
  return 0;
}