首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >网球比赛日程安排

网球比赛日程安排
EN

Stack Overflow用户
提问于 2011-01-20 21:08:27
回答 5查看 9.1K关注 0票数 43

运动员的数量有限,网球场的数量也有限。在每一轮,最多有多少场比赛就有多少场比赛。没有人在两轮比赛中不休息。每个人都在和其他人比赛。制作出尽可能少轮次的时间表。(因为规则是每个人都必须在两轮之间休息,所以可以有一轮没有比赛的回合。)5名球员和2个球场的输出可能是:

代码语言:javascript
运行
复制
 |  1   2   3   4   5
-|------------------- 
2|  1   - 
3|  5   3   - 
4|  7   9   1   - 
5|  3   7   9   5   -

在此输出中,列和行是玩家编号,矩阵中的数字是这两个玩家竞争的整数。

问题是找到一种算法,可以在可行的时间内对更大的实例做到这一点。我们被要求用Prolog来做这件事,但是任何语言的(伪)代码都是有用的。

我的第一次尝试是一个贪婪的算法,但它给出的结果太多了。然后我建议了一个迭代加深深度优先搜索,我的一个朋友实现了,但在小到7个玩家的实例上仍然花费了太多的时间。

(这是一道旧的考题。我采访过的人中没有人有任何解决方案。)

EN

回答 5

Stack Overflow用户

发布于 2011-01-20 21:48:43

这非常类似于Traveling Tournament Problem,它是关于安排足球队的。在TTP中,他们最多只能找到8个团队的最优解决方案。任何打破10个或更多团队的持续记录的人,都更容易在研究期刊上发表文章。

这是NP困难的,诀窍是使用元启发式,如禁忌搜索,模拟退火,...而不是蛮力或分枝捆绑。

看一下使用Drools Plannermy implementation (开源的java)。Here are the constraints,它应该是直接的,用限制来代替它,比如没有人打2轮没有休息。

票数 13
EN

Stack Overflow用户

发布于 2011-01-26 22:10:38

每个玩家必须至少玩n-1场比赛,其中n是玩家的数量。所以最小轮次是2(n - 1) - 1,因为每个玩家都需要休息一场比赛。最小值还由(n(n-1))个/2总匹配除以法庭数量确定。使用这两种方法中最小的一种可以得到最优解的长度。然后是一个很好的较低的估计公式((剩余的matches+rests数)/courts)并运行A* search

正如Geoffrey所说,我认为这个问题是NP困难的,但是像A*这样的元启发式非常适用。

票数 5
EN

Stack Overflow用户

发布于 2011-01-21 09:45:39

Python解决方案:

代码语言:javascript
运行
复制
import itertools

def subsets(items, count = None):
    if count is None:
        count = len(items)

    for idx in range(count + 1):
        for group in itertools.combinations(items, idx):
            yield frozenset(group)

def to_players(games):
    return [game[0] for game in games] + [game[1] for game in games]

def rounds(games, court_count):
    for round in subsets(games, court_count):
        players = to_players(round)
        if len(set(players)) == len(players):
            yield round

def is_canonical(player_count, games_played):
    played = [0] * player_count
    for players in games_played:
        for player in players:
            played[player] += 1

    return sorted(played) == played



def solve(court_count, player_count):
    courts = range(court_count)
    players = range(player_count)

    games = list( itertools.combinations(players, 2) )
    possible_rounds = list( rounds(games, court_count) )

    rounds_last = {}
    rounds_all = {}
    choices_last = {}
    choices_all = {}



    def update(target, choices, name, value, choice):
        try:
            current = target[name]
        except KeyError:
            target[name] = value
            choices[name] = choice
        else:
            if current > value:
                target[name] = value
                choices[name] = choice

    def solution(games_played, players, score, choice, last_players):
        games_played = frozenset(games_played)
        players = frozenset(players)

        choice = (choice, last_players)

        update(rounds_last.setdefault(games_played, {}), 
                choices_last.setdefault(games_played, {}), 
                players, score, choice)
        update(rounds_all, choices_all, games_played, score, choice)

    solution( [], [], 0, None, None)

    for games_played in subsets(games):
        if is_canonical(player_count, games_played):
            try:
                best = rounds_all[games_played]
            except KeyError:
                pass
            else:
                for next_round in possible_rounds:
                    next_games_played = games_played.union(next_round)

                    solution( 
                        next_games_played, to_players(next_round), best + 2,
                        next_round, [])

                for last_players, score in rounds_last[games_played].items():
                    for next_round in possible_rounds:
                        if not last_players.intersection( to_players(next_round) ):
                            next_games_played = games_played.union(next_round)
                            solution( next_games_played, to_players(next_round), score + 1,
                                    next_round, last_players)

    all_games = frozenset(games)


    print rounds_all[ all_games ]
    round, prev = choices_all[ frozenset(games) ]
    while all_games:
        print "X ", list(round)
        all_games = all_games - round
        if not all_games:
            break
        round, prev = choices_last[all_games][ frozenset(prev) ]

solve(2, 6)

输出:

代码语言:javascript
运行
复制
11
X  [(1, 2), (0, 3)]
X  [(4, 5)]
X  [(1, 3), (0, 2)]
X  []
X  [(0, 5), (1, 4)]
X  [(2, 3)]
X  [(1, 5), (0, 4)]
X  []
X  [(2, 5), (3, 4)]
X  [(0, 1)]
X  [(2, 4), (3, 5)]

这意味着它将需要11轮。该列表以相反的顺序显示了要在轮次中进行的游戏。(尽管我认为相同的时间表可以向前和向后工作。)我会回来解释为什么我有这个机会。

对于一个球场,五名球员,得到了错误的答案。

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/4747498

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档