从不均匀分布的集中删除项目

Question

我有一个网站,用户提交问题(每天零,一或多个),投票并每天回答一个问题(更多细节在这里).用户只能通过提交,投票或回答一次来查看问题.

我有一些玩家已经看过的问题.我需要每个月从池中删除30个问题.我需要选择要删除的问题,以便最大限度地提高游泳池中可用问题的数量.

有5个问题的池的例子(需要删除3个):

• 玩家A遇到过问题1,3和5
• 玩家B已经看到问题1和4
• 玩家C见过问题2和4

我虽然要删除顶级玩家所看到的问题,但这个位置会发生变化.按照上面的例子,玩家A只剩下2个问题要玩(2和4).但是,如果我删除1,3和5,情况将是:

• 玩家A可以玩问题2和4
• 玩家B可以玩问题2
• 玩家C不能玩任何东西因为1,3,5被移除而他已经看过2和4.

该解决方案的得分为零,即具有最少可用问题量的玩家具有零可用问题.

在这种情况下,最好删除1,3和4,给出:

• 玩家A可以玩问题2
• 玩家B可以玩问题2和5
• 玩家C可以玩问题5

此解决方案的得分为1,因为有两个可用问题最少的玩家有一个可用问题.

如果数据量很小,我就可以强制解决问题.但是,我有数百个玩家和问题,所以我正在寻找一些算法来解决这个问题.

Answer 1

线性规划模型。

变体 1。

Sum(Uij * Qj) - Sum(Dij * Xj) + 0     =  0 (for each i)
0             + Sum(Dij * Xj) - Score >= 0 (for each i)
Sum(Qj) = (Number of questions - 30)
Maximize(Score)

Uij是1如果用户i没有看到问题j，否则是0

Dij是单位矩阵的元素（Dij=1如果是i=j，否则是0）

Xj是辅助变量（每个用户一个）

变体 2。

Sum(Uij * Qj) >= Score (for each i)
Sum(Qj) = (Number of questions - 30)
No objective function, just check feasibility

在这种情况下，LP问题比较简单，但Score应该通过二分法和线性搜索来确定。将当前范围设置为[0 ..用户未见过的问题的最少数量]，设置Score为范围的中间，应用整数LP算法（时间限制较小）。如果没有找到解决方案，则将范围设置为 [begin .. Score]，否则将其设置为 [ Score.. end] 并继续二分查找。

（可选）使用二分搜索来确定精确解的上限Score。

从通过二分搜索找到的最佳 开始Score，应用整数 LP 算法Score，增加 1, 2, ...（并根据需要限制计算时间）。最后，你要么得到精确的解，要么得到一些好的近似值。

以下是 GNU GLPK 的 C 示例代码（对于变体 1）：

#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;
  int time = 30; // sec.

  // 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*2 + 1);
  for (row = 1; row <= users; ++row)
  {
    glp_set_row_bnds(lp, row, GLP_FX, 0.0, 0.0);
    glp_set_row_bnds(lp, row + users, GLP_LO, 0.0, 0.0);
  }
  glp_set_row_bnds(lp, users*2 + 1, GLP_FX, questions2, questions2);

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

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

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

  // Configure matrix (score column)
  for (row = 1; row <= users*2; ++row)
  {
    ind[row] = row;
    val[row] = (row > users)? -1.0: 0.0;
  }
  ind[users*2 + 1] = users*2 + 1;
  val[users*2 + 1] = 0.0;
  glp_set_mat_col(lp, questions + users + 1, users*2 + 1, ind, val);

  // Solve integer GLPK problem
  glp_iocp param;
  glp_init_iocp(&param);
  param.presolve = GLP_ON;
  param.tm_lim = time * 1000;
  glp_intopt(lp, &param);
  printf("Score = %g\n", glp_mip_obj_val(lp));

  glp_delete_prob(lp);
  return 0;
}

在我的测试中，时间限制运行不可靠。看起来像是 GLPK 中的一些错误...

变体2的示例代码（仅LP算法，不自动搜索Score）：

#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;
}

看来变体 2 可以很快找到相当好的近似值。并且近似值比变体 1 更好。