Интуиция
Я дам ему попробовать. Наивный подход - перечислить все возможные решения и выбрать лучший. Имея это в виду, поиск k комнат, в которых можно разместить n собрания, эквивалентен поиску k-разделенного n точек. Пример 2-стороннего разделения 5 собраний - это [ 0,2,4 ] и [ 1,3 ] в примере OP:
|---0------| |---------4---------|
|------1-----| |----------3-----------|
|--------2-------|
Итак, основная идея состоит в том, чтобы перечислить все k участников n собраний с ограничением, что два перекрывающихся собрания не могут принадлежать одному кластеру. Например, [ 0,1,2 ] и [ 3,4 ] не является допустимым разделом, потому что собрания [ 0,1,2 ] не могут проходить в комнате; то же самое касается встреч [ 3,4 ]. К счастью, ограничение легко реализовать при использовании рекурсивного подхода.
Алгоритм
С Python это выглядит так:
def kWay( A, k, overlap ) :
"""
A = list of meeting IDs, k = number of rooms,
overlap[ meeting ID m ] = set of meetings overlapping with m
"""
if k == 1 : # only 1 room: all meetings go there
yield [ A[:] ]
elif k == len(A) : # n rooms and n meetings: put 1 meeting per room
yield [ [a] for a in A ]
else :
for partition in kWay( A[1:], k, overlap ) : # add new meeting to one existing room
for i, ci in enumerate( partition ) :
isCompatible = all( A[0] not in overlap[x] for x in ci ) # avoid 2 overlapping meetings in the same room
res = partition[:i] + [ ci + [ A[0] ] ] + partition[ i+1: ]
if isCompatible :
yield res
for partition in kWay( A[1:], k-1, overlap ) : # add new meeting to a new room
isValid = ( set(A[1:]) & set.union( * ( overlap[a] for a in A[ 1: ] ) ) == set() ) # avoid 2 overlapping meetings in the same room
if (k-1>1) or ( k-1==1 and isValid ) :
yield partition + [ [ A[0] ] ]
Это выглядит немного сложным, но на самом деле это довольно просто, когда вы понимаете, что это просто рекурсивный алгоритм для kway разбиения + 2 дополнительных строки, чтобы гарантировать, что мы рассматриваем только допустимые разделы.
Решение примера OP
Хорошо, теперь давайте подготовим входные данные на примере OP:
import collections
n = 5
k = 2
#
A = range(n)
# prepare overlap dictionary
pairs = [ (0,1), (1,2), (2,3), (3,4) ] # overlapping meetings
size = dict( ( (0,10), (1,8), (2,6) , (3,10), (4,8) ) )
overlap = collections.defaultdict(set)
for (i,j) in pairs :
overlap[i].add(j)
overlap[j].add(i)
defaultdict(<type 'set'>, {0: set([1]), 1: set([0, 2]), 2: set([1, 3]), 3: set([2, 4]), 4: set([3])})
{0: 10, 1: 8, 2: 6, 3: 10, 4: 8}
Теперь мы просто перебираем допустимые 2 сегменты и печатаем размеры комнат. Есть только один допустимый раздел, поэтому это наше решение:
for partition in kWay( A, k, overlap ) :
print partition, [ max( size[x] for x in c ) for c in partition ]
[[3, 1], [4, 2, 0]] [10, 10]
Итак, собрания 1,3 проходят в комнату размера 10, а собрания 0,2,4 проходят в комнату размера 10.
Чуть более сложный пример
Но был только один допустимый 2-полосный раздел, так что, конечно, это тоже было оптимальным решением. Как скучно! Давайте добавим новую встречу 5 и новую комнату в пример OP, чтобы сделать его более интересным:
|---0------| |---5---| |---------4---------|
|------1-----| |----------3-----------|
|--------2-------|
Соответствующие входные данные:
n = 6
k = 3
#
A = range(n)
pairs = [ (0,1), (1,2), (2,3), (3,4), (5,2), (5,3) ] # overlapping meetings
size = dict( ( (0,10), (1,8), (2,6) , (3,10), (4,8), (5,2) ) )
overlap = collections.defaultdict(set)
for (i,j) in pairs :
overlap[i].add(j)
overlap[j].add(i)
defaultdict(<type 'set'>, {0: set([1]), 1: set([0, 2]), 2: set([1, 3, 5]), 3: set([2, 4, 5]), 4: set([3]), 5: set([2, 3])})
{0: 10, 1: 8, 2: 6, 3: 10, 4: 8, 5: 2}
И результат:
for partition in kWay( A, k, overlap ) :
print partition, [ max( size[x] for x in c ) for c in partition ]
[[3, 1], [4, 2, 0], [5]] [10, 10, 2]
[[3, 1], [4, 2], [5, 0]] [10, 8, 10]
[[3, 0], [4, 2], [5, 1]] [10, 8, 8]
[[3], [4, 2, 0], [5, 1]] [10, 10, 8]
[[4, 5, 1], [3, 0], [2]] [8, 10, 6]
[[4, 5, 1], [3], [2, 0]] [8, 10, 10]
[[4, 5, 0], [3, 1], [2]] [10, 10, 6]
[[4, 5], [3, 1], [2, 0]] [8, 10, 10]
Оптимальная 3-полосная перегородка - [[3, 1], [4, 2, 0], [5]], а оптимальные размеры комнаты - [10, 10, 2]. Вы также можете получить минимальный размер всех комнат напрямую:
min( sum( [ max( size[x] for x in c ) for c in partition ] ) for partition in kWay( A, k, overlap ) )
22
person
usual me
schedule
11.07.2014
