区间树增加了子集匹配的维数？

Question

这是一个关于某个复杂问题的算法问题.基础是这样的:

一种基于可用时隙和预留时隙的调度系统.插槽有一定的标准,我们称之为标签.如果可用插槽的标签集是保留插槽的超集,则预留与这些标签的可用插槽匹配.

作为一个具体示例,请采用以下方案:

11:00  12:00  13:00
+--------+
| A, B   |
+--------+
       +--------+
       | C, D   |
       +--------+

11:00至12:30预订标签的时间之间A,并B可以进行,时间为12:00至13:30 C和D可用,并有大约12点的重叠至12:30.

11:00  12:00  13:00
+--------+
| A, B   |
+--------+
       +--------+
       | C, D   |
       +--------+
  xxxxxx
  x A  x
  xxxxxx

这里A已经预订了,因此在11:15-ish和12:00-ish之间没有其他预订A或B可以预订.

这就是简单的想法.可用插槽没有特定限制:

• 可用的插槽可以包含任意数量的标签
• 任何数量的插槽都可以随时重叠
• 插槽具有任意长度
• 预订可以包含任意数量的标签

系统中唯一需要遵守的规则是:

• 添加预订时,至少有一个剩余可用插槽必须与预留中的所有标签匹配

澄清一下:当有两个可用的插槽同时使用标签时A,那么A可以在那时进行两次预订,但不能再进行.

我有一个改进的间隔树实现的工作; 作为快速概述:

• 所有可用的槽都被添加到间隔树中(保留重复/重叠)
• 所有保留的槽都是迭代的,并且:
  • 从树中查询与预约时间匹配的所有可用插槽
  • 匹配保留标签的第一个被切片并从树中删除切片

当该过程完成时,剩下的剩余可用插槽片段,我可以查询是否可以在特定时间内进行新预订并添加它.

数据结构看起来像这样:

{
  type: 'available', 
  begin: 1497857244, 
  end: 1497858244, 
  tags: [{ foo: 'bar' }, { baz: 42 }]
}
{
  type: 'reserved', 
  begin: 1497857345, 
  end: 1497857210, 
  tags: [{ foo: 'bar' }]
}

标签本身就是键值对象,它们的列表是"标签集".如果它有帮助,可以将它们序列化; 到目前为止,我使用的是Python set类型,这使得比较变得非常容易.插槽开始/结束时间是树中的UNIX时间戳.我并没有特别嫁给这些特定的数据结构,如果它有用,可以重构它们.

---

我面临的问题是,这不会无错误; 每隔一段时间,一次预订会悄悄进入与其他预订冲突的系统,而我还无法弄清楚这是怎么发生的.当标签以复杂的方式重叠时,它也不是很聪明,需要计算最佳分布,因此所有预留都可以尽可能地适应可用的插槽; 实际上,目前在重叠场景中如何将预留与可用时隙匹配是不确定的.

我想知道的是:间隔树大多数都是为了这个目的,但我现在的系统添加标签集匹配作为一个额外的维度是笨重和螺栓连接; 是否有一种数据结构或算法能够以优雅的方式处理这个问题？

必须支持的行动:

1. 查询系统以查找与某些标签集匹配的可用插槽(考虑可能降低可用性但本身不属于所述标签集的预留;例如,在上面查询可用性的示例中B).
2. 确保没有预留可以添加到没有匹配可用插槽的系统中.

Answer 1

使用约束编程可以解决您的问题.在python中,这可以使用python-constraint库来实现.

首先,我们需要一种方法来检查两个插槽是否彼此一致.如果两个槽共享一个标签并且它们的rimeframe重叠,则这个函数返回true.在python中,这可以使用以下函数实现

def checkNoOverlap(slot1, slot2):
    shareTags = False
    for tag in slot1['tags']:
        if tag in slot2['tags']:
            shareTags = True
            break    
    if not shareTags: return True
    return not (slot2['begin'] <= slot1['begin'] <= slot2['end'] or 
                slot2['begin'] <= slot1['end'] <= slot2['end'])

我不确定你是否希望标签完全相同(如{foo:bar}等于{foo:bar})或只是键(如{foo:bar}等于{foo:qux}),但你可以改变上面的功能.

一致性检查

我们可以使用python-constraint模块来实现您请求的两种功能.

第二个功能是最简单的.为了实现这一点,我们可以使用isConsistent(set)将提供的数据结构中的插槽列表作为输入的函数.然后,该函数将所有插槽提供给python-constraint,并检查插槽列表是否一致(没有2个插槽不应重叠,重叠)并返回一致性.

def isConsistent(set):
        #initialize python-constraint context
        problem = Problem()
        #add all slots the context as variables with a singleton domain
        for i in range(len(set)):
            problem.addVariable(i, [set[i]])        
        #add a constraint for each possible pair of slots
        for i in range(len(set)):
            for j in range(len(set)):
                #we don't want slots to be checked against themselves
                if i == j:
                    continue
                #this constraint uses the checkNoOverlap function
                problem.addConstraint(lambda a,b: checkNoOverlap(a, b), (i, j))
        # getSolutions returns all the possible combinations of domain elements
        # because all domains are singleton, this either returns a list with length 1 (consistent) or 0 (inconsistent)
        return not len(problem.getSolutions()) == 0

只要用户想要添加预留槽,就可以调用此功能.输入槽可以添加到现有槽的列表中,并且可以检查一致性.如果它是一致的,则重新保留新的插槽.否则,新的插槽重叠并且应该被拒绝.

寻找可用的插槽

这个问题有点棘手.我们可以使用与上面相同的功能,并进行一些重大更改.我们现在想要将所有可能的插槽添加到现有插槽中,而不是将新插槽与现有插槽一起添加.然后,我们可以检查所有可能的插槽与保留插槽的一致性,并向约束系统询问一致的组合.

因为如果我们没有对它进行任何限制,可能的插槽数将是无限的,我们首先需要为程序声明一些参数:

MIN = 149780000 #available time slots can never start earlier then this time
MAX = 149790000 #available time slots can never start later then this time
GRANULARITY = 1*60 #possible time slots are always at least one minut different from each other

我们现在可以继续主要功能了.它看起来很像一致性检查,但是我们现在添加一个变量来发现所有可用的插槽,而不是用户的新插槽.

def availableSlots(tags, set):
    #same as above
    problem = Problem()
    for i in range(len(set)):
        problem.addVariable(i, [set[i]])
    #add an extra variable for the available slot is added, with a domain of all possible slots
    problem.addVariable(len(set), generatePossibleSlots(MIN, MAX, GRANULARITY, tags))
    for i in range(len(set) +1):
        for j in range(len(set) +1):
            if i == j:
                continue
            problem.addConstraint(lambda a, b: checkNoOverlap(a, b), (i, j))
    #extract the available time slots from the solution for clean output
    return filterAvailableSlots(problem.getSolutions())

我使用一些辅助函数来保持代码清洁.它们包括在这里.

def filterAvailableSlots(possibleCombinations):
    result = []
    for slots in possibleCombinations:
        for key, slot in slots.items():
            if slot['type'] == 'available':
                result.append(slot)

    return result

def generatePossibleSlots(min, max, granularity, tags):
    possibilities = []
    for i in range(min, max - 1, granularity):
        for j in range(i + 1, max, granularity):
            possibleSlot = {
                              'type': 'available',
                              'begin': i,
                              'end': j,
                              'tags': tags
            }
            possibilities.append(possibleSlot)
    return tuple(possibilities)

您现在可以将函数getAvailableSlots(tags,set)与您想要可用插槽的标签和一组已预留的插槽一起使用.请注意,此函数确实返回所有一致的可能插槽,因此无需查找最大长度或其他优化.

希望这可以帮助!(我按照你在我的pycharm中描述的那样工作)