竞赛配对算法

Question

我需要找到理想的配对比赛球员，根据以下规则：

• 得分相等或相近的球员应进行匹配。
• 两名选手在比赛中只能进行一场相互比赛。
• 所有球员必须在一轮比赛中进行一场比赛。

它基本上是一个简化的瑞士锦标赛系统。

我有以下名次：

[{
  "playerIndex": 0,
  "points": 0,
  "opponents": [3, 2, 4]
}, {
  "playerIndex": 1,
  "points": 3,
  "opponents": [4, 5, 2]
}, {
  "playerIndex": 2,
  "points": 3,
  "opponents": [5, 0, 1]
}, {
  "playerIndex": 3,
  "points": 4,
  "opponents": [0, 4, 5]
}, {
  "playerIndex": 4,
  "points": 6,
  "opponents": [1, 3, 0]
}, {
  "playerIndex": 5,
  "points": 2,
  "opponents": [2, 1, 3]
}]

读为:第一个数组项目是玩家编号(索引)0，它已经与玩家编号(索引) 3、2和4一起玩过，并且获得了0分，每个项目在一场比赛中有六名选手中的一名。

第四场比赛我要选三场。按照一条规则，两名球员不得进行超过一次的相互比赛，我从下列比赛中选择：

[ [ 0, 1 ], [ 0, 5 ], [ 1, 3 ], [ 2, 3 ], [ 2, 4 ], [ 4, 5 ] ]

这六场比赛中的每一场都有两名球员的分数差异如下：

[3, 2, 1, 1, 2, 4]

因此，第四轮的理想配对是，在一轮比赛中，每名选手之间的分数差都是最低的：

[ [0, 5], [1, 3], [2, 4] ]

有没有办法实时找到这些理想的配对？这是不可能尝试所有可能的组合，因为可以有超过100人在一场比赛和计算将永远。

有人建议我使用algorithm或algorithm (都可以在JS：https://www.npmjs.com/package/edmonds-blossom和https://github.com/sfentress/edmunds-karp中找到)。但我不知道如何阅读结果。

有人能帮忙吗？

Answer 1

编辑:匈牙利算法失败，如果有太多的可能的解决方案。在我的情况下，在第一轮之后，有很多球员拥有相同的分数。

Edmond算法的性能要好得多(发现这个JS实现可以通过NPM https://github.com/mattkrick/EdmondsBlossom获得)。

只是很难理解如何使用它。主要的区别是你需要用成对来给它喂食，对于那些应该是首选的对，它们之间的点差更大。所以我对已经玩过的两对使用零差。

我的最后(希望)解决方案：

  var maxDiff = (roundIndex + 1) * this.config.pointsWin

  var possiblePairs = []
  availablePlayers.forEach(player => {
    availablePlayers.forEach(opponent => {
      if (
        player.playerIndex !== opponent.playerIndex // &&
        // player.opponents.indexOf(opponent.playerIndex) === -1
      ) {
        var match = [player.playerIndex, opponent.playerIndex]
        match.sort(function(a, b) {
          return a - b;
        })
        if (player.opponents.indexOf(opponent.playerIndex) === -1) {
          match.push(maxDiff - Math.abs(player.points - opponent.points))
        }
        else {
          match.push(0)
        }
        if (this.searchForArray(possiblePairs, match) === -1) {
          possiblePairs.push(match)
        }
      }
    })
  })

  var rawPairing = edmondsBlossom(possiblePairs)
  rawPairing.forEach((match, index) => {
    if (match !== -1 && match < index) {
      round.matches.push({
        home: match,
        home_score: '',
        away: index,
        away_score: '',
        referee: -1
      })
    }
  })

首先，我计算球员之间最大可能的分数差异(希望有人能得到零分，而其他人都会得到零分)。然后在玩家之间创建所有可能的组合，并用最大可能的点数来标记它们--对于之前匹配的玩家，玩家的积分差或零。

然后将数组提供给返回整数数组的EdmondsBlossom函数.

[6,8,14,5,15,3,0,10,1,12,7,13,9,11,2,4]

...read如下:玩家指数0应该与玩家6，玩家1比8，玩家2比14，玩家3比5.玩家5比3(副本)。有时，输出中有-1值被简单跳过。

以下是我的解决方案(不推荐)：

由于@VedPrakash的评论，我找到了解决我问题的匈牙利算法。幸运的是，NPM https://github.com/addaleax/munkres-js上也有一个JS实现。

Munkers函数需要一个矩阵作为输入。在我的例子中，这是玩家在我的矩阵交点上的点数差异(见下文)。已经相互玩过的两对有着更高的价值，无法实现(在我的例子中是9)。

输入矩阵：

[ [ 9, 4, 9, 9, 9, 3 ],
  [ 4, 9, 9, 2, 9, 9 ],
  [ 9, 9, 9, 2, 4, 9 ],
  [ 9, 2, 2, 9, 9, 9 ],
  [ 9, 9, 4, 9, 9, 5 ],
  [ 3, 9, 9, 9, 5, 9 ] ]

输出：

[ [ 0, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 1 ], [ 4, 2 ], [ 5, 0 ] ]

最后要处理的是过滤Munker输出(其中包含重复的-- 0vs1和1vs0)，所以我只需比较第一个和第二个索引就可以过滤它们。

我的实施：

  var maxDiff = (roundIndex + 1) * this.config.pointsWin

  // prepare matrix
  var matrix = [];
  for (var i = 0; i < availablePlayers.length; i++) {
    matrix[i] = new Array(availablePlayers.length);
    matrix[i].fill(0)
  }

  // fill matrix with players points diff
  for (var y = 0; y < availablePlayers.length; y++) {
    var playerY = availablePlayers[y]

    for (var x = 0; x < availablePlayers.length; x++) {
      var playerX = availablePlayers[x]

      if (x === y) {
        matrix[x][y] = maxDiff
      }
      else if (playerY.opponents.indexOf(x) !== -1) {
        matrix[x][y] = maxDiff
        matrix[y][x] = maxDiff
      }
      else {
        var value = Math.abs(playerX.points - playerY.points)
        matrix[x][y] = value
        matrix[y][x] = value
      }
    }
  }

  // console.table(matrix)
  // console.table(computeMunkres(matrix))
  // return

  // make pairing
  var rawPairing = computeMunkres(matrix)
  rawPairing.forEach(pairing => {
    if (pairing[0] < pairing[1]) {
      round.matches.push({
        home: pairing[0],
        home_score: '',
        away: pairing[1],
        away_score: '',
        referee: -1
      })
    }
  })