У меня есть конкретная проблема, которую я хочу решить с помощью алгоритма Кнута X. Однако я изо всех сил пытаюсь перевести свою проблему в подходящие ограничения, которые составляют матрицу инцидентности для алгоритма X для работы.
Для своего летнего турнира в спортивном клубе я хочу составить расписание, в котором четыре игрока будут группироваться вместе, без перегруппировки какой-либо пары игроков в последующих игровых раундах.
Я подумал, что это хорошо переводится в проблему с точным прикрытием:
- Все игроки представлены в виде столбца матрицы
- Каждая группа из четырех игроков (независимо от их порядка) составляет одну строку в матрице.
- Таким образом, 1 записывается в ячейке матрицы, когда игрок является членом этой группы.
После настройки для 20 игроков у меня есть матрица инцидентности с 20 столбцами и 4845 строками (969 строк на игрока/столбец).
Алгоритм X найдет решение очень хорошо, но это покроет только один (первый) раунд. Если алгоритм продолжит работу, он выдаст больше альтернативных решений для одного и того же раунда, что меня не интересует. Поэтому я создаю итератор вокруг алгоритма, который будет принимать решение и удалять строки из матрицы инцидентности на основе перекрытия игроков: всякий раз, когда группа из решения имеет пересечение не менее 2 с любой строкой матрицы, эта строка удаляется. . После первого запуска алгоритма матрица сокращается до 1280 строк. Запуск алгоритма X найдет следующее решение и т. д., пока не перестанет.
Короче говоря, этот подход не является правильным применением проблемы точного покрытия - мне пришлось итеративно находить частичные решения. Правильная задача о точном покрытии должна каким-то образом включать в себя последовательность игровых раундов. Почему? Потому что сейчас я не исследую весь спектр возможных решений! Количество игроков, равное 20, является лучшим примером для этого. Алгоритм X найдет решения всего за 3 последовательных раунда. Тем не менее, я знаю, что есть по крайней мере 5, когда выбираются разные промежуточные решения. Я надеялся, что именно эту задачу сможет решить за меня алгоритм X. При описанном выше подходе между игровыми раундами не происходит возврата.
Несмотря на то, что вопрос достаточно абстрактный, чтобы в коде не было необходимости, вот моя реализация DLX Кнута (алгоритм X с Танцевальные ссылки) в Python:
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))]
Обратите внимание, что это не обязательно должно быть точное решение. Это просто пример решения, которое я нашел во время своих попыток в конечном итоге создать расписание для произвольного количества игроков.
