如何创建避免重复的优化计划

Question

我有一份为期 16 天的团队间比赛列表：

| Date | Game                        |
|------|-----------------------------|
| 1    | hot ice vs playerz          |
| 1    | caps vs quiet storm         |
| 1    | slick ice vs blizzard       |
| 1    | flow vs 4x4's               |
| 2    | avalanche vs cold force     |
| 2    | freeze vs in too deep       |
| 2    | game spot vs rare air       |
| 2    | out of order vs cold as ice |
| 3    | playerz vs avalanche        |
| 3    | quiet storm vs freeze       |
| 3    | blizzard vs game spot       |
| 3    | 4x4's vs out of order       |
| 14   | freeze vs avalanche         |
| 14   | out of order vs game spot   |
| 14   | in too deep vs cold force   |
| 14   | cold as ice vs rare air     |
| 15   | blizzard vs quiet storm     |
| 15   | playerz vs 4x4's            |
| 15   | slick ice vs caps           |
| 15   | hot ice vs flow             |
| 16   | game spot vs freeze         |
| 16   | avalanche vs out of order   |
| 16   | rare air vs in too deep     |
| 16   | cold force vs cold as ice   |

有 16 支球队组成了这个时间表，我想在 Python 中做的是找到所有 8 种游戏组合，让我“看到”每支球队一次。唯一的限制是我每天只能看一场比赛。在这一点上，我所能想到的就是大量嵌套的 for 循环，这些循环生成所有可能的计划，然后检查每个计划是否有效。一个有效的时间表是每个日期有一场比赛并且每支球队都见一次。

Answer 1

您可以使用回溯算法遍历不同的匹配组合，并根据您提到的限制条件过滤它们。

第一步是将您的数据格式化为一个集合，例如 python list 或 dict。然后实施递归回溯算法，每天选择一场比赛，并检查以确保所选比赛不包括您已经选择的球队。

这是一个使用您在问题中提供的数据的粗略示例：

def combinations(matches, day, schedules, current):
    """Backtracking function for selecting unique schedules."""
    # base case when you have a match from each day
    if day > max(matches.keys()):  
        schedules.append(current[:])
        return
    # skip over days where there are no matches
    while day not in matches:
        day += 1
    # select one match for the current date
    for i in range(len(matches[day])):
        teams = matches[day][i]
        current_teams = [j for i in current for j in i]
        # check if the teams are already in the current schedule
        if teams[0] in current_teams or teams[1] in current_teams: 
            continue
        del matches[day][i]
        # recursive case
        combinations(matches, day + 1, schedules, current + [teams])
        matches[day].insert(i,teams)
    return




def format(inp):
    """Formats input data into a dictionary."""
    lines = inp.split("\n")[2:]     # split lines of input data
    matches = [(line.split("|")[1:-1]) for line in lines]
    schedule = {}
    # add matches to dict with date as key and matches as value.
    for day, match in matches:
        day = int(day.strip())
        teams = match.strip().split(" vs ")
        try:
            schedule[day].append(teams)
        except KeyError:
            schedule[day] = [teams]
    ideal = []
    # use backtracking algorithm to get desired results
    combinations(schedule, 1, ideal, [])
    show_schedules(ideal)


def show_schedules(results):
    for i, x in enumerate(results):
        print(f"Schedule {i+1}")
        for day, match in enumerate(x):
            print(f"Day: {day+1} - {match[0]} vs. {match[1]}")
        print("\n")


format(inp)  # <- entry point:`inp` is the pre-formatted data `str`

这并不是最优雅的代码...:) 通过示例数据，该算法生成了 6 场比赛的 32 个独特时间表。输出看起来像这样但是对于每一天的比赛：

Schedule 1
Day: 1 - hot ice vs. playerz
Day: 2 - avalanche vs. cold force
Day: 3 - quiet storm vs. freeze
Day: 4 - out of order vs. game spot
Day: 5 - slick ice vs. caps
Day: 6 - rare air vs. in too deep


Schedule 2
Day: 1 - hot ice vs. playerz
Day: 2 - avalanche vs. cold force
Day: 3 - 4x4's vs. out of order
Day: 4 - cold as ice vs. rare air
Day: 5 - blizzard vs. quiet storm
Day: 6 - game spot vs. freeze

有关回溯的更多信息，这里有一些外部资源，或者这里有无数关于堆栈溢出的例子。

https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/

http://jeffe.cs.illinois.edu/teaching/algorithms/book/02-backtracking.pdf

如何创建避免重复的优化计划

How to create optimized schedule that avoids duplicates

python

optimization