我的问题是生成具有相同游戏数量的随机玩家对,但限制游戏数量,这样所有玩家就不必互相玩了。
把它想象成一个国际象棋游戏,其中随机玩家被设置为游戏,但每个玩家不必与所有玩家一起玩(这会花费太多时间)但他们都必须拥有相同数量的公平竞争的游戏。
到目前为止,我为游戏生成了独特的配对,但所有玩家都必须扮演每个人,这会花费太多时间。 我知道代码并不漂亮,但它必须每月运行一次,以生成对:
@RequestMapping("/voistlus/{id}")
public String newGame(Model model, @PathVariable Long id) {
Stage stage = stageService.findOneById(id);
if (gameService.findByStage(stage).isEmpty()) {
List<Paar> paars = paarService.getAllPaar();
List<Game> pairs = new ArrayList<Game>();
for (Paar one : paars) {
for (Paar two : paars) {
if (!one.equals(two)) {
Game newPair = new Game();
newPair.setPaar1(one);
newPair.setPaar2(two);
if (!pairs.contains(newPair)) {
if (pairs.isEmpty()) {
pairs.add(newPair);
newPair.setStage(stage);
gameService.save(newPair);
} else {
boolean exists = false;
for (Game game : pairs) {
if (game.getPaar1().equals(two) && game.getPaar2().equals(one)) {
exists = true;
}
}
if (!exists) {
pairs.add(newPair);
newPair.setStage(stage);
gameService.save(newPair);
}
}
}
}
}
}
}
model.addAttribute("pairs", gameService.findByStage(stage));
return "newGame";
}
最佳答案
考虑图中每个玩家都是一个顶点,玩家之间的边表示这些玩家之间的游戏。我们想要做的是在这个图中找到循环,其中每个循环都经过所有玩家,即我们想在这个图中找到哈密顿循环。
一般来说,找出一个图是否有哈密顿环是 NP 完全的。然而,由于我们在这个问题中考虑的图是一个完全图(每个顶点都有一条到其他顶点的边),所以这个问题很容易。
我们可以用下面的伪代码来做到这一点
Let V be the empty set
Let E be the empty set
Let init be a random vertex
Add init to V
While V does not contain all players
Select a random vertex R that is not in V
Add R to V
Add the edge (init - R) to E
Let init = R
End
E now contains the set of games to be played
通过多次执行此操作,您将能够生成多个哈密尔顿循环,每个循环都是一组游戏,其中每个玩家与另外两个不同的玩家对战。
该算法有一个主要缺点,即它允许同一游戏多次出现。 (玩家 1 和玩家 2 有可能不止一次对战。)
如果我们想避免这种情况,我们必须在搜索下一个循环之前从图中删除我们找到的循环。然而,这样做会确定是否存在另一个循环,从而再次找到它,NP 完全。
关于Java生成随机玩家对,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27998416/