我有一个特定的问题，我想使用Knuth's Algorithm X来解决。但是，我很难将我的问题转化为合适的约束，这些约束构成了算法 X 运行的关联矩阵。
对于我的体育俱乐部夏季锦标赛，我想制定一个时间表，将四名球员组合在一起，而无需在随后的比赛中重新组合任何一对球员。
我认为这可以很好地转化为这样的精确覆盖问题：
- 所有玩家都表示为矩阵的一列
- 每组四名玩家（不管他们的顺序）是矩阵中的一行。
- 因此，当玩家是该组的成员时，将 1 写入矩阵单元格。
在为 20 个玩家设置后，我得到了一个包含 20 列和 4845 行（每个玩家/列 969 行）的关联矩阵。
算法 X 会很好地找到一个解决方案，但这只会涵盖一个（第一）轮。让算法继续下去会为同一轮吐出更多替代解决方案，这对我来说并不感兴趣。所以我围绕算法构建了一个迭代器，它将获取解决方案并根据玩家重叠从关联矩阵中删除行：每当解决方案中的一个组与矩阵的任何行有至少 2 的交集时，该行就会被删除. 在算法第一次运行后，矩阵被剔除到 1280 行。运行算法 X 将找到下一个解决方案，等等，直到它不再存在。
长话短说，这种方法不是精确覆盖问题的正确应用——我必须反复寻找部分解决方案。正确的精确覆盖问题应该包括以某种方式进行的回合顺序。为什么？因为现在我没有探索所有可能的解决方案！20 名球员就是最好的例子。算法 X 将只找到 3 个连续轮次的解决方案。Yet, I do know that there are at least 5, when different intermediate solutions are chosen. 这正是我希望算法 X 能够为我解决的工作。使用上述方法，游戏轮次之间没有回溯。
尽管这个问题足够抽象以至于不需要代码，但这是我在 Python 中实现的 Knuth 的 DLX（带有Dancing Links的算法 X）：
from itertools import combinations
def dancing_links (players):
"""
Implement the dancing links algorithm as described by Donald Knuth, which
attemts to solve an exact cover problem exhaustively in an efficient way.
Adapted for my use case, I define the incidence matrix as follows:
* Columns are players.
* Rows are groups of players.
* The intersection of groups and players mean that that player is a
member of that group.
* One group contains exactly four players, i.e. each row has
exactly four 1s.
* Repeatedly solve the exact cover problem for a reduced set of groups,
where each round the total set of groups is filtered for illegal
groups. An illegal group features at least two players that
have already played together in a round.
"""
class FoundSolution (Exception):
"Use the exception to abort recursive stacks"
pass
# Dancing links is based on "doubly linked lists" intersecting
# with each other. Python doesn't have this kind of data structure
# and implementing it is quite expensive. E.g. each field of the incidence
# matrix could be a Node which has pointers in all four directions,
# The Node class with 6 attributes (four pointers, a name and arbitrary
# data) needs to undergo countless name lookups, which is a slow process
# in Python. So instead, I represent each node without a class definition
# as a dict.
#
# Since we're walking over so many doubly linked lists, starting from
# any of its nodes, we need to remember where we started and iterate
# through all of them. That clutters our code later on a lot without
# this iterator function.
def iter_dll (start, direction='right'):
next = start[direction]
# Need to explicitly compare object ids. Otherwise Python
# would try to do a deep comparison of two dicts. which is impossible
# due to the circular referencing.
while id(start) != id(next):
yield next
next = next[direction]
def cover (column):
"""
Cover a column by removing its head node from the control row and
removing each of its rows from other columns that intersect.
"""
column['left']['right'] = column['right']
column['right']['left'] = column['left']
for r in iter_dll(column, 'down'):
for c in iter_dll(r):
c['up']['down'] = c['down']
c['down']['up'] = c['up']
def uncover (column):
# Undo the changes caused by a call to cover(dll) by injecting the
# linked nodes with the remembered predecessor and successor.
for r in iter_dll(column, 'up'):
for c in iter_dll(r, 'left'):
c['up']['down'] = c['down']['up'] = c
else:
column['left']['right'] = column['right']['left'] = column
def search (i, root):
if id(root['right']) == id(root):
# The only way to exit the complete recursion stack is an exception.
raise FoundSolution
for c in iter_dll(root):
cover(c)
for r in iter_dll(c, 'down'):
lineup.append(r)
for j in iter_dll(r):
cover(j['data'])
search(i+1, root)
lineup.pop()
for j in iter_dll(r, 'left'):
uncover(j['data'])
else:
uncover(c)
def generate_incidence_matrix (groups):
# The gateway to our web of doubly linked lists.
root = {'name': 'root', 'data': None}
# Close the circle in left and right dirctions, so we can keep the
# circle closed while injecting new nodes.
root['right'] = root['left'] = root
# The control row of column headers is created by attaching each new
# Header with the previous one.
for player in players:
n = {
'name': 'Headnode {}'.format(player),
'data': player,
'right': root,
'left': root['left'],
}
n['up'] = n['down'] = n
root['left']['right'] = root['left'] = n
# Now append nodes to each column header node in our control row -
# one for each player of a distinct group of four players.
rnmbr = 0
# Seed for new row nodes
seed = {'name': 'seed', 'data': None}
for g in groups:
rnmbr += 1
seed['right'] = seed['left'] = seed
# Iterate through the control nodes for each of the four players.
for header in (m for m in iter_dll(root) for p in g if m['data'] == p):
n = {
# Chose a name that identifies the row and colum for this
# new node properly.
'name': 'R-{},C-{}'.format(rnmbr, header['data']),
'data': header,
'up': header['up'],
'down': header,
'left': seed,
'right': seed['right']
}
header['up']['down'] = header['up'] = n
seed['right']['left'] = seed['right'] = n
else:
# Extract the seed from this row
seed['right']['left'] = seed['left']
seed['left']['right'] = seed['right']
return root
groups = tuple(combinations(players, 4))
groups_per_round = len(players)/4
lineups = []
while len(groups) >= groups_per_round:
root = generate_incidence_matrix(groups)
lineup = []
try:
search(0, root)
except FoundSolution:
lineup = reduce(list.__add__, ([r['data']['data']] + [n['data']['data'] for n in iter_dll(r)] for r in lineup))
lineup = tuple(tuple(sorted(lineup[i:i + 4])) for i in xrange(0, len(lineup), 4))
lineups.append(lineup)
groups = tuple(group for group in groups if all(len(g.intersection(set(group))) < 2 for g in (set(s) for s in lineup)))
else:
break
return lineups
给定玩家列表，此功能将打印中间解决方案到屏幕，直到选项用尽。可悲的是，它没有我希望的那么快，但对我来说这是一个很好的编程练习。:-)
调用dancing_links()上面定义的函数将产生以下输出...
>>> pprint.pprint(dancing_links(range(1,21)))
[((1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 16), (17, 18, 19, 20)),
((1, 5, 9, 13), (2, 6, 10, 17), (3, 7, 14, 18), (4, 11, 15, 19), (8, 12, 16, 20)),
((1, 6, 11, 14), (2, 5, 12, 18), (3, 8, 13, 19), (4, 9, 16, 17), (7, 10, 15, 20))]
我所期待的更像是……
[((1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 16), (17, 18, 19, 20)),
((1, 5, 9, 13), (2, 6, 10, 17), (3, 7, 14, 18), (4, 11, 15, 19), (8, 12, 16, 20)),
((1, 12, 15, 18), (2, 5, 16, 19), (3, 6, 9, 20), (4, 7, 10, 13), (8, 11, 14, 17)),
((1, 7, 11, 20), (2, 8, 13, 18), (3, 5, 10, 15), (4, 9, 16, 17), (6, 12, 14, 19)),
((1, 8, 10, 19), (2, 7, 9, 15), (3, 12, 13, 17), (4, 5, 14, 20), (6, 11, 16, 18))]
请注意，它不一定是这个确切的解决方案。这只是我在尝试最终为任意数量的玩家生成时间表时发现的一个示例解决方案。