gpt4 book ai didi

algorithm - 添加子集匹配维度的区间树?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:17:33 26 4
gpt4 key购买 nike

这是一个关于一个有点复杂的问题的算法问题。基础是这样的:

基于可用时隙保留时隙 的调度系统。插槽有特定的标准,我们称它们为标签。如果可用槽的标签集是预留槽的超集,则预留会通过这些标签与可用槽相匹配。

举个具体的例子,看这个场景:

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

可以在 11:00 到 12:30 之间预订标签 AB,从 12:00 到 13:30 CD 可用,并且大约在 12:00 到 12:30 之间有重叠。

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

此处已为 A 预订,因此在 11:15-ish 之间不能为 AB 预订和 12:00 左右。

简而言之就是这个想法。可用插槽没有特定限制:

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

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

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

澄清一下:当同时有两个可用的插槽时,例如,标记 A,那么此时可以为 A 进行两次预留,但是没有了。

我有一个修改过的 interval tree 的实现;快速概览:

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

当该过程完成后,剩下的就是剩余的可用空档片,我可以查询是否可以为特定时间进行新预订并添加它。

数据结构看起来像这样:

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

标签本身就是键值对象,它们的列表就是一个“标签集”。如果有帮助,可以将它们连载;到目前为止,我使用的是 Python set 类型,这使得比较非常容易。槽开始/结束时间是树中的 UNIX 时间戳。我不是特别喜欢这些特定的数据结构,如果有用的话可以重构它们。


我面临的问题是这不是没有错误的;每隔一段时间,一个预订就会潜入系统并与其他预订发生冲突,我还不知道这到底是怎么发生的。当标签以复杂的方式重叠时,它也不是很聪明,需要计算最佳分布,以便所有预订都能尽可能地适合可用的插槽;事实上,目前还不确定如何在重叠场景中将预订与可用时段相匹配。

我想知道的是:区间树最适合用于此目的,但我当前添加标签集匹配作为附加维度的系统笨拙且固定; 有没有一种数据结构或算法可以优雅地处理这个问题?

必须支持的 Action :

  1. 向系统查询与特定标签集匹配的可用空位(考虑到可能会降低可用性但本身不属于所述标签集的预订;例如,在上面的示例中查询 B 的可用性>).
  2. 确保没有匹配的可用时段的预订不能添加到系统。

最佳答案

您的问题可以使用 constraint programming 解决.在 python 中,这可以使用 python-constraint 来实现图书馆。

首先,我们需要一种方法来检查两个插槽是否相互一致。这是一个函数,如果两个插槽共享一个标签并且它们的框架重叠,则返回 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 中描述的那样工作)

关于algorithm - 添加子集匹配维度的区间树?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44589798/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com