有没有匹配算法可以根据玩家的游戏水平创建4人一组的游戏



在一项被称为padel网球的运动中,人们4人一组组织比赛。每个玩家都有一个";游戏水平";分配:从1(初学者(到7(职业选手(。它可以有1个小数。

问题目标:最大化创建的每组4名玩家的数量。

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

约束Publisher的游戏等级为可以加入的玩家修复了差距:+-0.5。注:如果发行商的游戏等级为7,则加入的玩家的差距为6到7。如果是1,则间隙为1到2。

假设:发布游戏时,玩家独自完成,因此他/她预计还会有3个人单独加入(来自其他数据集(。第二个数据集中有更多的参与者。

问题的变化:研究当第二个数据集中的配对百分比变化时的不同结果(最初为零(。额外的组合,将第一个数据集转换为对。备注:当创建用于分析问题变化的配对时,请使用+-1的游戏水平差距标准创建它们更大的目标是知道哪种组合能创造更多的游戏

其他问题(?(:运行所有可能匹配的计算能力。

朋友推荐我使用python或VBA Excel来运行不同的匹配模拟,但我愿意接受建议。感谢您的阅读,希望您能从哪里开始回答:(附言:我对python的经验很少。

主要问题可以通过排序来解决,并贪婪地将"发布者"玩家与3名"搜索"玩家进行匹配。

每个发布者对应一个长度为1的间隔,这是玩家在游戏中可接受的技能水平。按右端点对这些间隔进行排序。还要按级别对"搜索"玩家进行排序。

现在,同时浏览这两个列表。当至少有3个搜索玩家和至少1个间隔需要考虑时,看看最小的3个玩家p1、p2和p3,以及最小的间隔I=[左,右]。有三种情况:

  1. 如果正确<p3,那么我们永远无法匹配这个区间,所以放弃它
  2. 否则,如果p3<=向右但向左>p1,然后将p1从考虑中丢弃
  3. 否则,这是一个有效的匹配,因此记录"间隔I匹配的玩家(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.

例如,如果你将问题泛化,使得"间隙间隔"的长度不都相同,或者它们的值/权重不同,那么贪婪方法就不再有效,需要一种动态编程方法。

最新更新