我有问题!
我有一个简单的表格,其中包含player_1
、player_2
和played
。
+---------+----------+----------+
| player1 | player2 | played |
+---------+----------+----------+
| 1 | 2 | 1 |
| 1 | 3 | 2 |
| 1 | 4 | 1 |
| 1 | 5 | 0 |
| 1 | 6 | 0 |
| 2 | 3 | 3 |
| 2 | 4 | 2 |
| 2 | 5 | 1 |
| 2 | 6 | 3 |
| 3 | 4 | 1 |
| 3 | 5 | 2 |
| 3 | 6 | 0 |
| 4 | 5 | 3 |
| 4 | 6 | 1 |
| 5 | 6 | 3 |
+---------+----------+----------+
等等...有 78 条记录,因为总共有 13 名球员。
我想要一个结果,告诉我哪些"比赛"玩得最少。因此,例如,一个人生病了,上次不能玩,这个人和其他玩家之间的游戏较低。这场比赛更有可能出现在结果中。
但是在每个结果中,向我显示 6 场比赛(1 名玩家有一些休息时间),一名球员只能显示一次!但是,玩得最少的游戏也必须出现在结果中。(嗯,最后一部分很简单,ORDER BY played ASC
,LIMIT 6
)...
如何让每个 13 名玩家(好吧,没有一个)出现在结果中?
一个不错的结果是(好吧,现在我只想要 3 场比赛,因为在这个例子中只有 6 名球员)......每个玩家在这一轮中都玩一场比赛,它是通过排列最少的游戏来选择的。其余的只是被填满。
+---------+----------+----------+
| player1 | player2 | played |
+---------+----------+----------+
| 1 | 5 | 0 |
| 2 | 4 | 1 |
| 3 | 6 | 0 |
+---------+----------+----------+
你可以把它想象成一个图问题。假设每个玩家都是一个节点,表中的每条记录代表一个弧线,一个权重为"玩过"的加权弧,与弧线相连的 2 名玩家之间的游戏数。
现在,您正在寻找一种算法来查找玩得最少的 6 场比赛(如果我理解正确的话,下一轮要玩的 6 场比赛),前提是每个玩家每轮只玩一次。我建议使用贪婪的算法:
1. Sort arcs ascending.
2. While there are still arcs left.
2.1 Remove first arc and add to round_games.
2.2 Remove all arcs with any participating nodes in the previous arc.