优化矩阵中的排列

Question

我正在努力解决下面的问题，我确信这个问题有解决办法。我不能透露太多的信息，所以我制定了它的一般术语，并提出了以下寓言。我在这里向你介绍 睡眠问题。你知道吗

Imagine a monastery where 12 monks sleep, eat, pray, or work outside the monastery. Each monk, needs to sleep 8 or 6 hours per night. Each monk has X amount where he has to work in the garden, the stall or herd the sheep (e.g, activities outside the monastery) and Y hours hangs around within the walls of the monastery during these Y hours each monk is either hanging around (e.g. praying, eating, consuming beer) or he is sleeping S hours (Y is always bigger the S).

The head of this monastery asks if there is a possible way to find a best possible sleeping arrangement such that the number of beds can be reduced, and that each monks get its required sleeping.

我对该问题的输入数据如下表所示：

time_slots_in_monastery = [
#  time of the day
#14 16 18 20 22 24 2  4  6  8 10  12
(0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
(0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
(0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
(0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
(0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
(0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0),
(0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0),
(0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
(0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0),
(0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
]

每行代表一个和尚。数字1代表寺院内的时隙，0代表僧侣在外的时间。你知道吗

另外，我还有一个向量，包含每个人的睡眠需求 和尚。你知道吗

required_sleeping = [4, # number of sleeping slots , each one is 2 hours.
                     3,
                     3,
                     4,
                     4,
                     4,
                     4,
                     3,
                     3,
                     3,
                     3,
                     3]

目前的解决方案是：

solution = [
    (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    ]

# total beds:
#    0, 0, 12, 12, 12, 5, 0, 0 , 0, 0, 0, 0

所有的僧侣晚上6点睡觉。但是如果我们让11号和尚和12号和尚使用同一张床，我们就可以把床的数量减少到11张。更好的是，1号和尚和2号和尚也可以共用一张床，然后我们把床的数量减少到10张。你知道吗

better_solution = [
        (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
        (0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0),
        (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
        (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
        (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
        (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
        (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
        (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
        (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
        (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
        (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
        (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
        ]

现在有12个僧侣，这个问题可能是暴力强迫的，但实际上我有大约50个僧侣，解决的时间是5分钟，而不是2小时。因此，我正在寻找一种方法，找到一种方法来解决问题的f-最小搜索风格或任何其他方式，这是不是蛮力。你知道吗

我在这里介绍我的Python暴力解决方案：

 import pprint
 time_slots_in_monastery = [
 #  time of the day
 #14 16 18 20 22 24 2  4  6  8 10  12
 (0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
 (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
 (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
 (0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
 (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
 (0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0),
 (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
 (0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0),
 (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
 (0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0),
 (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
 ]
 required_sleeping = [4,
                      3,
                      3,
                      4,
                      4,
                      4,
                      4,
                      3,
                      3,
                      3,
                      3,
                      3]

 def make_new_bed(rl):
     bed = '0' * rl
     return bed

 def search_in_beds(beds, rl, sleep_time, first, last):
     sleep_slots = '0' * sleep_time
     sleep = '1' * sleep_time
     index = False
     for cn, bed in enumerate(beds):
         try:
             index = bed[first:last+1].index(sleep_slots)
             index += first
             bed = bed[:first] + bed[first:last+1].replace(sleep_slots, sleep, 1) + bed[last+1:]
             beds[cn] = bed
             print()
             print('monastery time from: %s to: %s' % (first, last))
             print('this monk found a place in bed(%s) from (%s) to (%s)' % (cn, index, index + sleep_time-1))
             print('bed(%s) time: %s ' % (cn, bed))
         except:
             """
             I did not found a free time in this bed
             """
             pass
     if index:
         return index, index + sleep_time - 1
     #adding a bed and searching again
     beds.append(make_new_bed(rl))
     return search_in_beds(beds, rl, sleep_time, first, last)

 def monks_beds(t, rsleep, rl=12):
     beds = []
     output = []
     for cn, i in enumerate(t):
         sleep_time = rsleep[cn]
         first = i.index(1)
         last = len(i) - 1 - i[::-1].index(1)
         first, last = search_in_beds(beds, rl, sleep_time, first, last)
         out = rl * '0'
         out = out[:first] + sleep_time * '1' + out[last:]
         output.append([int(x) for x in out])
     return beds

 print('time_slots_in_monastery:')
 pprint.pprint(time_slots_in_monastery)
 print('required_sleeping')
 pprint.pprint(required_sleeping)
 pprint.pprint(monks_beds(time_slots_in_monastery, required_sleeping))

Answer 1

天真的解决方案

我能想出的一个解决办法没有考虑到“在修道院的时间”，那就是确保相邻两个僧侣的睡眠时间永远不会重叠，以我们一天的时间长度为模数：

monks = numpy.array([
    (1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0),
    (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1),  # Pattern wraps around at midnight
    ...
])

我相信（但现在还不能正式证明）这个解决方案是最优的，因为：

1. 如果一天足够长，你只需要一张床。你知道吗
2. 一天正好一个小时太短了你需要一张第二张床，第一次睡。剩下的时间里，床都是空的。你知道吗
3. 一天短两个小时你需要一张第二张床，前两个时间段。剩下的时间里，床都是空的。你知道吗
4. 每个时隙的床位数将一直填充到最后一个时隙，然后您需要第三张床位作为第一个时隙。你知道吗
5. 继续。你知道吗

所以我们需要解决的就是如何通过编程改变我们的睡眠时间，使相邻的两个时间不重叠：

import numpy

monks = numpy.array([
    (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
])

# Hours of sleep required is sum along columns
hours = numpy.sum(monks, axis=1)

# Reset all sleeping times to first column
monks = numpy.sort(monks, axis=1)[:, ::-1]

# Generate sleeping pattern without overlap of two neighboring monks. When
# one monk rises, the next one goes to bed.
hours = numpy.cumsum(hours)

# Insert 0 shift for first monk
hours = numpy.insert(hours, 0, 0)

for s, i in zip(hours, range(monks.shape[0])):
    monks[i, :] = numpy.roll(monks[i, :], s)

beds = numpy.max(numpy.sum(monks, axis=0))

print monks
# [[1 1 1 1 0 0 0 0 0 0 0 0]
#  [0 0 0 0 1 1 1 0 0 0 0 0]
#  [0 0 0 0 0 0 0 1 1 1 0 0]
#  [1 0 0 0 0 0 0 0 0 0 1 1]
#  [0 1 1 1 1 0 0 0 0 0 0 0]
#  [0 0 0 0 0 1 1 1 1 0 0 0]
#  [1 0 0 0 0 0 0 0 0 1 1 1]
#  [0 1 1 1 1 0 0 0 0 0 0 0]
#  [0 0 0 0 0 1 1 1 0 0 0 0]
#  [0 0 0 0 0 0 0 0 1 1 1 0]
#  [1 1 0 0 0 0 0 0 0 0 0 1]
#  [0 0 1 1 1 0 0 0 0 0 0 0]
#  [0 0 0 0 0 1 1 1 0 0 0 0]]

print beds
# 4

相邻“寺院时间”的可能解决方案

第二个解决方案我“可以想象的工作”（但肯定不能证明是最优的）是使用相同的算法，限制在“时间在修道院”的时间，排序后的“时间在修道院”矩阵。你知道吗

1. 首先，我会对矩阵进行排序，以便进入最早矩阵的僧侣首先：

   time_slots_in_monastery = numpy.array([
       (0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),  # monk 0 enters earlier than 1
       (0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
       (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
       (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0),
       (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0),
       (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0),
   ])
   

2. 然后对绑定的条目（僧侣同时进入）进行排序，以便最先离开的僧侣优先：

   time_slots_in_monastery = numpy.array([
       (0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
       (0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
       (0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),  # monk 2 and 3 enter at same time, but 2 leaves earlier than 3
       (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0),
       (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
       (0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0),
       (0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0),
   ])
   

3. 应用前面的算法，但仅限于time_slots_in_monastery二进制掩码：

   1. Monk0在Monk0mask index0开始睡觉
   2. 和尚1在和尚0停止时开始睡觉。在蒙版之外的重叠被环绕，从蒙克1蒙版索引0开始
   3. 继续为所有僧侣。你知道吗

这个想法是让两个相邻的僧侣有尽可能多的重叠，并尽可能早地填补第一个空缺。你知道吗

def rangemod(val, start, stop):
    """ Modulo in range between start and stop

    Adjusted from
    http://stackoverflow.com/questions/3057640/math-looping-between-min-and-max-using-mod
    """
    p = stop - start
    mod = (val - start) % p
    if mod < 0:
        mod += p
    return start + mod;


timeslots = numpy.array([
    (0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
    (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
    (0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0),
    (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
    (0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0),
    (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
    (0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0),
    (0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0),
])

sleephours = numpy.array([4, 3, 3, 4, 4, 4, 4, 3, 3, 3, 3, 3])

# Sort timeslots
startidx = numpy.array([list(row).index(1) for row in timeslots])
endidx = numpy.array([list(row)[::-1].index(1) for row in timeslots])

sortidx = numpy.array([
    x for _, _, x in sorted(
        zip(startidx, endidx, range(len(startidx))),
        key=lambda (x, y, z): (x, -y)
    )
])

# Put all indices and sleephours in new order
startidx = startidx[sortidx]
endidx = endidx[sortidx]
endidx = timeslots.shape[1] - endidx
sleephours = sleephours[sortidx]
timeslots = timeslots[sortidx, :]

print timeslots
# [[0 1 1 1 1 1 0 0 0 0 0 0]
#  [0 0 1 1 1 1 1 1 0 0 0 0]
#  [0 0 1 1 1 1 1 1 0 0 0 0]
#  [0 0 1 1 1 1 1 1 1 0 0 0]
#  [0 0 1 1 1 1 1 1 1 0 0 0]
#  [0 0 1 1 1 1 1 1 1 0 0 0]
#  [0 0 1 1 1 1 1 1 1 1 0 0]
#  [0 0 0 1 1 1 1 1 1 0 0 0]
#  [0 0 0 1 1 1 1 1 1 0 0 0]
#  [0 0 0 1 1 1 1 1 1 0 0 0]
#  [0 0 0 1 1 1 1 1 1 1 0 0]
#  [0 0 0 0 0 1 1 1 1 1 0 0]]

out = numpy.zeros_like(timeslots)

# Fill sleep schedule
prevstop = startidx[0]
for r, s, e, t, row in zip(sleephours, startidx, endidx, timeslots, out):
    sleeprange = numpy.arange(s, e)
    sleeppattern = numpy.zeros(e - s)
    sleeppattern[:r] = 1
    sleeppattern = numpy.roll(sleeppattern, prevstop - s)
    row[sleeprange] = sleeppattern
    prevstop += r
    prevstop = rangemod2(prevstop, s, e)

print out
# [[0 1 1 1 1 0 0 0 0 0 0 0]
#  [0 0 1 0 0 1 1 1 0 0 0 0]
#  [0 0 0 1 1 1 1 0 0 0 0 0]
#  [0 0 1 0 0 0 0 1 1 0 0 0]
#  [0 0 0 1 1 1 0 0 0 0 0 0]
#  [0 0 0 0 0 0 1 1 1 0 0 0]
#  [0 0 1 1 1 0 0 0 0 0 0 0]
#  [0 0 0 0 0 1 1 1 1 0 0 0]
#  [0 0 0 1 1 1 0 0 0 0 0 0]
#  [0 0 0 0 0 0 1 1 1 0 0 0]
#  [0 0 0 1 1 1 1 0 0 0 0 0]
#  [0 0 0 0 0 0 0 1 1 1 0 0]]

print numpy.max(numpy.sum(sleeping_slots, axis=0))
# 6

Answer 2

这里的解决方案与上面的有点不同。我已经把和尚们的指数洗牌了，但我相信重新索引不会有问题。我相信这个解决方案是最优的。你知道吗

算法如下：

首先，我们把僧侣分成4和3两个单位。你知道吗

• 3个僧侣谁睡4个单位，可以分为一个单位谁将只需要一张床。这是这组3个僧侣的最佳解决方案。你知道吗
• 同样地，4个僧侣睡3个单位可以被认为是一个单位，每个人睡一张床。你知道吗

现在我们需要计算这些单元的数量，并为每个单元分配一张单人床。你知道吗

关于剩下的僧侣：

我们一定会把剩下的修道士消耗4个时间单位，并不断增加修道士（消耗3个时间单位），直到我们达到12个时间单位。我们给这一组分配一张床。你知道吗

我们现在必须为不属于上一个单位的其余僧侣分配一张床。你知道吗

程序如下：

if __name__ == '__main__':

    reqSleep = [4, 3, 3, 4, 4, 4, 4, 3, 3, 3, 3, 3]
    num4     = len([r for r in reqSleep if r==4])
    num3     = len([r for r in reqSleep if r==3])

    group4, left4 = num4/3, num4%3
    group3, left3 = num3/4, num3%4

    groups = {}
    groups['group3'] = [
        (1,1,1,0,0,0,0,0,0,0,0,0),
        (0,0,0,1,1,1,0,0,0,0,0,0),
        (0,0,0,0,0,0,1,1,1,0,0,0),
        (0,0,0,0,0,0,0,0,0,1,1,1),
    ]

    groups['group4'] = [
        (1,1,1,1,0,0,0,0,0,0,0,0),
        (0,0,0,0,1,1,1,1,0,0,0,0),
        (0,0,0,0,0,0,0,0,1,1,1,1),
    ]

    print num4, ' >', (group4, left4)
    print num3, ' >', (group3, left3)

    alreadyIn = []
    for i in range(group4):
        alreadyIn += groups['group4']

    for i in range(group3):
        alreadyIn += groups['group3']

    # we add the number of monks who
    # sleep for 4 hours
    alreadyIn += groups['group4'][:left4]

    # Now we are left with `left3`. How many can 
    # we add to this ? We take until they consume 
    # 12 time units. 
    num3ToFill = 0
    currTotal  = left4*4
    for i in range(left3):
        if currTotal + 3 > 12: break
        num3ToFill += 1
        currTotal  += 3

    # Fill in the number of groups
    alreadyIn += groups['group3'][-num3ToFill:]

    # Finally add the leftover monks at the end
    if left3 > num3ToFill:
        alreadyIn += groups['group3'][: (left3-num3ToFill)]

    print 'Monk sleep specs ...'
    for x in  alreadyIn:
        print x

    print 'Beds used ...'
    numBeds = map(sum, zip(*alreadyIn))
    print numBeds

    print 'done'   

结果如下：

5  > (1, 2)
7  > (1, 3)
Monk sleep specs ...
(1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1)
(1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1)
(1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1)
(1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0)
Beds used ...
[4, 4, 4, 4, 4, 4, 3, 3, 2, 3, 3, 3]

增加更多的僧侣和不同的时间单位可以通过更仔细地观察“所需睡眠”时间来优化。所有的算法都可能围绕着优化阵列来解决。你知道吗