优化矩阵内的排列

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 位僧侣。数字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-minimum-search 风格或任何其他非蛮力方式解决问题的方法。

我在 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

天真的解决方案

我想出的一个解决方案没有考虑到 "time at monastery" 总是确保两个相邻僧侣的睡眠时间永远不会重叠，以我们一天的长度为模：

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
    ...
])

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

足够长的一天，您只需要一张床。
一天整整一个小时太短了，您需要一张第二张床，用于第一个时间段。在一天剩下的时间里，床将是空的。
一天两个小时你需要一张第二张床，用于前两个时间段。在一天剩下的时间里，床将是空的。
每个时间段的床位数量将一直填满到最后一个时间段，然后您将需要第三个 床位再次用于第一个时间段。
继续。

所以我们需要解决的就是如何以编程方式改变两个相邻时间不重叠的僧侣睡眠时间：

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

连续 "time at monastery"

的可能解决方案

我"can imagine working"的第二个解决方案（但绝对不能证明是最优的）是在对"time at monastery"矩阵排序后使用相同的算法，限制在"time at monastery"次。

首先我会对矩阵进行排序，让最早进入的和尚排在第一位：

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),
])

然后对并列条目（同时进入的僧人）进行排序，使最早离开的僧人在前：

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),
])

应用以前的算法，但仅限于 time_slots_in_monastery 二进制掩码：
1. 和尚0 开始在和尚睡觉 0 面具索引 0
2. 当僧侣 0 停止时，僧侣 1 开始睡觉。 Overlap beyond mask 环绕，从 Monk 1 mask index 0
3. 所有僧侣继续。

想法是让两个相邻的僧侣尽可能多地重叠，并尽早填充第一个槽位。

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

    Adjusted from
    
    """
    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]

添加更多的僧侣和不同的时间单位可以通过更仔细地查看"required sleeping"次来优化。所有算法都可能围绕优化该数组来解决。

优化矩阵内的排列

Optimizing arangments inside a matrix

python

matrix

mathematical-optimization

天真的解决方案

连续 "time at monastery"