在體育安排的背景下，我有一個游戲串列，其中團隊可能會玩超過 1x 的游戲。如果是這樣的話，他們的比賽應該是背靠背的。由于配對的本質，這可能不可行，至少它們應該盡可能靠近。
這是初始配對的示例，其中每個團隊進行 2 次比賽：
[('t05', 't09'), ('t07', 't03'), ('t01', 't09'), ('t03', 't01'), ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t10', 't08'), ('t10', 't04'), ('t08', 't02')]
請注意，這不是雙回圈配置，即每支球隊在主客場比賽中每隔兩場比賽。這只是團隊玩兩場比賽的配置。
我正在嘗試實施一種演算法來對這些游戲進行排序，以使每個團隊的游戲盡可能地接近。這是第一個簡單的方法：
matches = list(matches)
c = collections.Counter([t for m in matches for t in m.teams])
for t, n in c.iteritems():
if n > 1:
# matches containing the team t
indices = [i for i, m in enumerate(matches) if t in m.teams]
for i in indices:
# bring these matches to the front
matches.insert(0, matches.pop(i))
return matches
這是結果：
[('t10', 't04'), ('t10', 't08'), ('t01', 't09'), ('t05', 't09'), ('t08', 't02'), ('t07', 't03'), ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t03', 't01')]
顯然這不是很好，因為它是一面之詞，通過將他們的比賽放在串列的前面，它使串列末尾的團隊受益更多。一邊倒，我的意思是它在每場比賽中只關注一支球隊并為該球隊進行排序，而忽略第二支球隊，這將打破另一支球隊的背靠背平衡。
這將是使用約束編程進行最大化的完美案例，例如使用python-constraint或pyomo。但是我在建模約束滿足問題 (CSP) 方面真的很糟糕，所以我不知道從哪里開始這個案例。
有任何想法嗎？
uj5u.com熱心網友回復：
遞回函式可以以動態編程的方式嘗試各種排序，優先連接游戲而不是序列中的中斷。
這個沒有特別優化，但對于小游戲串列應該足夠快：
def gameOrder(games,prevGame=None):
if len(games)==1: return games # base condition (only one game)
best,breaks = games,len(games)-1 # track best order and number of breaks
for strict in (1,0): # prioritize connections over breaks
for i,game in enumerate(games): # each game as 1st in sequence
if breaks <= strict: return best # minimum breaks reached
if strict and prevGame and prevGame.isdisjoint(game):
continue # does not connect to previous (strict)
seq = [game] gameOrder(games[:i] games[i 1:],set(game)) # sort rest
brk = sum(set(g1).isdisjoint(g2) for g1,g2 in zip(seq,seq[1:]))
if brk < breaks:
breaks,best = brk,seq # track best so far
return best # return best found
輸出：
games = [('t05', 't09'), ('t07', 't03'), ('t01', 't09'), ('t03', 't01'),
('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t10', 't08'),
('t10', 't04'), ('t08', 't02')]
print(gameOrder(games)) # only one break between (t07,t05) and (t02,t06)
[('t05', 't09'), ('t01', 't09'), ('t03', 't01'), ('t07', 't03'),
('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t10', 't04'),
('t10', 't08'), ('t08', 't02')]
請注意，這可確保盡可能多的球隊連續比賽。如果您的目標是將任何球隊的比賽之間的最壞情況“距離”最小化，或者最小化每支球隊的平均比賽距離，這可能不是最佳解決方案。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359141.html