问是否有任何匹配算法可以根据4名玩家的游戏级别来创建他们的组？
EN

Stack Overflow用户

提问于 2021-11-15 10:34:52

回答 1查看 121关注 0票数 1

在一项名为padel网球的运动中，人们以4人一组的方式组织比赛。每个运动员都有一个“游戏级别”：从1(对于初学者)到7(对于职业球员)。它可以有一个小数点。

问题目标：最大限度地增加了4名玩家创建的组数。

数据：2数据集:一个用于发布游戏的玩家，另一个用于寻找游戏的玩家。每个数据集都包含有玩家ID和播放级别的列。

约束。发行者的播放级别弥补了可以加入的玩家的差距：+-0.5。注:如果出版商的游戏水平为7，那么加入的玩家的差距是6到7，如果是1，那么差距是1到2。

假设:当发布游戏时，玩家会单独完成，因此他/她希望有3个人单独加入(从其他数据集)。在第二个数据集中有更多的玩家。

问题的变化：研究在第二个数据集中改变对的百分比时的不同结果(最初为零)。额外的组合，将第一个数据集转换成对。备注:在为分析问题的变化而创建对时，使用+-1的游戏间隙标准创建它们。更大的目标是知道哪种组合创造了更多的游戏。

附加问题(？)：运行所有可能匹配的计算能力。

朋友建议我使用python或VBA来运行不同的匹配模拟，但我愿意接受建议。谢谢你的阅读，并希望能给出一些提示，说明从何开始:) PS:我在python方面的经验非常少。

matching

python

algorithm

回答 1

Stack Overflow用户

发布于 2021-11-15 11:30:44

主要的问题是可以通过排序和贪婪地匹配'publisher‘播放器和3组’搜索‘播放器来解决。

每个发行者对应一个长度1的间隔，这是玩家在游戏中可接受的技能水平。根据它们的正确端点对这些间隔进行排序。此外，根据“搜索”玩家的级别对他们进行排序。

现在，同时浏览这两个列表。当至少有3个搜索玩家和至少一个间隔需要考虑时，请查看最小的3个参与者，p1、p2和p3，以及最小的间隔，I =左、右。有三个案件：

如果正确的< p3，那么我们永远无法匹配这个间隔，所以放弃它。
否则，如果p3 <=向右但左> p1，则放弃p1。
否则，这是一个有效的匹配，所以记录“Interval I match players (p1，p2，p3 )”，并删除I、p1、p2和p3。

重复这些步骤将给出尽可能多的分组。这可以用类似的方法作为贪婪区间调度的证明来证明。

作为算法运行的一个示例：

Publishing Players [1.0, 2.5, 3.2, 3.5]
Corresponding intervals: ([1.0-2.0], [2.0-3.0], [2.7-3.7], [3.0-4.0])

Searching Players [1.0, 2.2, 2.5, 2.9, 3.0, 3.4, 3.8]

Loop iterations:
Iteration 1:
I =          [1.0, 2.0]
p1, p2, p3 = [1.0,      2.2, 2.5]
I's right end too small, discard I

Iteration 2:
I =               [2.0,          3.0]
p1, p2, p3 = [1.0,      2.2, 2.5]
p1 too small, discard p1

Iteration 3:
I =         [2.0,              3.0]
p1, p2, p3 =    [2.2, 2.5, 2.9]
Match found: discard I, p1, p2, p3

Iteration 4:
I =         [2.7,          3.7]
p1, p2, p3 =    [3.0, 3.4,     3.8]
I's right end too small, discard I

Iteration 5:
I =          [3.0,          4.0]
p1, p2, p3 = [3.0, 3.4, 3.8]
Match found: discard I, p1, p2, p3

Out of players or intervals: done.