algorithm - 多人游戏锦标赛生成器

Question

<分区>

Answer 1

解决相关社交高尔夫球手问题的方法之一是本地搜索。一些提议的方法非常复杂。下面的 C 程序不是；它选择一个随机的初始时间表并进行随机交换，不会增加不玩的玩家对的数量。 100 名玩家和 6 人一组至少需要 21 轮(有些玩家缺席一轮，然后需要 ceil((100 - 1)/(6 - 1)) = 20 轮来玩每个人)，所以 27 不是与最佳值相差太远，但我确信使用更复杂的优化技术可以做得更好。

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

enum {
  GAMENUMPLAYER = 6,
  NUMPLAYER = 100,
  ROUNDNUMPLAYER = NUMPLAYER - NUMPLAYER % GAMENUMPLAYER,
  NUMROUND = 27
};

static int Schedule[NUMROUND][NUMPLAYER];
static int Numgame[NUMPLAYER][NUMPLAYER];
static int Numunplayed = (NUMPLAYER * (NUMPLAYER - 1)) / 2;

static void count(int r, int i, int delta) {
  int start;
  int stop;
  int j;
  if (i >= ROUNDNUMPLAYER) return;
  start = i - i % GAMENUMPLAYER;
  stop = start + GAMENUMPLAYER;
  for (j = start; j < stop; j++) {
    int p;
    int q;
    if (j == i) continue;
    p = Schedule[r][i];
    q = Schedule[r][j];
    if (q < p) {
      int t;
      t = p;
      p = q;
      q = t;
    }
    if (Numgame[p][q] == 0) Numunplayed--;
    Numgame[p][q] += delta;
    if (Numgame[p][q] == 0) Numunplayed++;
  }
}

static void swap(int r, int i, int j) {
  int t;
  count(r, i, -2);
  count(r, j, -2);
  t = Schedule[r][i];
  Schedule[r][i] = Schedule[r][j];
  Schedule[r][j] = t;
  count(r, i, 2);
  count(r, j, 2);
}

static void validate(void) {
  int nu;
  int q;
  nu = 0;
  for (q = 0; q < NUMPLAYER; q++) {
    int p;
    for (p = 0; p < q; p++) {
      int ng;
      int r;
      ng = 0;
      for (r = 0; r < NUMROUND; r++) {
        int i;
        for (i = 0; i < ROUNDNUMPLAYER; i++) {
          int k;
          if (Schedule[r][i] != p) continue;
          for (k = 0; k < GAMENUMPLAYER; k++) {
            if (Schedule[r][i - i % GAMENUMPLAYER + k] == q) ng++;
          }
        }
      }
      assert(ng * 2 == Numgame[p][q]);
      assert(Numgame[p][q] >= 0);
      if (Numgame[p][q] == 0) nu++;
    }
  }
  assert(nu == Numunplayed);
}

int main(void) {
  int r;
  for (r = 0; r < NUMROUND; r++) {
    int i;
    for (i = 0; i < NUMPLAYER; i++) {
      int j;
      j = rand() % (i + 1);
      Schedule[r][i] = Schedule[r][j];
      Schedule[r][j] = i;
    }
    for (i = 0; i < NUMPLAYER; i++) count(r, i, 1);
  }
  while (Numunplayed > 0) {
    int r;
    int i;
    int j;
    int previous;
    r = rand() % NUMROUND;
    i = rand() % NUMPLAYER;
    j = rand() % NUMPLAYER;
    previous = Numunplayed;
    swap(r, i, j);
    if (Numunplayed < previous) {
      fprintf(stderr, "%d\n", Numunplayed);
    } else if (Numunplayed > previous) {
      swap(r, i, j);
    }
  }
  for (r = 0; r < NUMROUND; r++) {
    int i;
    for (i = 0; i < NUMPLAYER; i++) {
      if (i > 0) putchar(i % GAMENUMPLAYER == 0 ? ';' : ',');
      printf("%d", Schedule[r][i]);
    }
    putchar('\n');
  }
  return EXIT_SUCCESS;
}