Дерево интервала с добавленным размером соответствия подмножества?

Ответ 1

Ваша проблема может быть решена с помощью программирования ограничений. В python это может быть реализовано с помощью библиотеки python-constraint.

Во-первых, нам нужен способ проверить, соответствуют ли два слота друг другу. это функция, которая возвращает true, если два слота совместно используют тег, а их rimeframes перекрываются. В 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 для двух типов запрошенных вами функций.

Вторая функциональность - самая простая. Чтобы реализовать это, мы можем использовать функцию isConsistent(set), которая принимает список слотов в предоставленной структуре данных в качестве входных данных. Затем функция будет передавать все слоты на ограничение python и будет проверять, соответствует ли список слотов (нет 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

Эта функция может вызываться всякий раз, когда пользователь хочет добавить слот резервирования. Входной слот можно добавить в список уже существующих слотов, и согласованность может быть проверена. Если это согласовано, новый слот будет резервным. Else, новый слот перекрывается и должен быть отклонен.

Поиск доступных слотов

Эта проблема немного сложнее. Мы можем использовать те же функции, что и выше, с несколькими значительными изменениями. Вместо того, чтобы добавить новый слот вместе с существующим слотом, мы теперь хотим добавить все возможные слоты в уже существующие слоты. Затем мы можем проверить согласованность всех возможных слотов с зарезервированными слотами и спросить систему ограничений для совместимых комбинаций.

Поскольку число возможных слотов было бы бесконечным, если бы мы не накладывали на него никаких ограничений, сначала нужно объявить некоторые параметры для программы:

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 (теги, установить) с тегами, для которых вы хотите использовать доступные слоты и набор уже зарезервированных слотов. Обратите внимание, что эта функция действительно возвращает все последовательные возможные слоты, поэтому никаких усилий не требуется, чтобы найти максимальную длину или для других оптимизаций.

Надеюсь, это поможет! (Я получил его для работы, как вы описали в моем pycharm)

Ответ 2

Здесь решение, я буду включать весь код ниже.

1. Создайте таблицу слотов и таблицу резервирования

2. Создайте матрицу резервирования x слотов

который заполняется истинными или ложными значениями, исходя из того, возможна ли комбинация с резервированием.

3. Выясните лучшее сопоставление, которое позволяет использовать большинство комбинаций резервирования-слота

Примечание. Мое текущее решение плохо масштабируется с очень большими массивами, поскольку оно включает в себя цикл всех возможных перестановок списка с размером = количество слотов. Я отправил еще один вопрос, чтобы узнать, может ли кто-нибудь найти лучший способ сделать это. Однако это решение является точным и может быть оптимизировано.

Источник кода Python

Часть 1

from IPython.display import display
import pandas as pd
import datetime

available_data = [
    ['SlotA', datetime.time(11, 0, 0), datetime.time(12, 30, 0), set(list('ABD'))],
    ['SlotB',datetime.time(12, 0, 0), datetime.time(13, 30, 0), set(list('C'))],
    ['SlotC',datetime.time(12, 0, 0), datetime.time(13, 30, 0), set(list('ABCD'))],
    ['SlotD',datetime.time(12, 0, 0), datetime.time(13, 30, 0), set(list('AD'))],
]

reservation_data = [
    ['ReservationA', datetime.time(11, 15, 0), datetime.time(12, 15, 0), set(list('AD'))],
    ['ReservationB', datetime.time(11, 15, 0), datetime.time(12, 15, 0), set(list('A'))],
    ['ReservationC', datetime.time(12, 0, 0), datetime.time(12, 15, 0), set(list('C'))],
    ['ReservationD', datetime.time(12, 0, 0), datetime.time(12, 15, 0), set(list('C'))],
    ['ReservationE', datetime.time(12, 0, 0), datetime.time(12, 15, 0), set(list('D'))]
]

reservations = pd.DataFrame(data=reservation_data, columns=['reservations', 'begin', 'end', 'tags']).set_index('reservations')
slots = pd.DataFrame(data=available_data, columns=['slots', 'begin', 'end', 'tags']).set_index('slots')

display(slots)
display(reservations)

Часть 2

def is_possible_combination(r):
    return (r['begin'] >= slots['begin']) & (r['end'] <= slots['end']) & (r['tags'] <= slots['tags'])

solution_matrix = reservations.apply(is_possible_combination, axis=1).astype(int)
display(solution_matrix)

Часть 3

import numpy as np
from itertools import permutations

# add dummy columns to make the matrix square if it is not
sqr_matrix = solution_matrix
if sqr_matrix.shape[0] > sqr_matrix.shape[1]:
    # uhoh, there are more reservations than slots... this can't be good
    for i in range(sqr_matrix.shape[0] - sqr_matrix.shape[1]):
        sqr_matrix.loc[:,'FakeSlot' + str(i)] = [1] * sqr_matrix.shape[0]
elif sqr_matrix.shape[0] < sqr_matrix.shape[1]:
    # there are more slots than customers, why doesn't anyone like us?
    for i in range(sqr_matrix.shape[0] - sqr_matrix.shape[1]):
        sqr_matrix.loc['FakeCustomer' + str(i)] = [1] * sqr_matrix.shape[1]

# we only want the values now
A = solution_matrix.values.astype(int)

# make an identity matrix (the perfect map)
imatrix = np.diag([1]*A.shape[0])

# randomly swap columns on the identity matrix until they match. 
n = A.shape[0]

# this will hold the map that works the best
best_map_so_far = np.zeros([1,1])

for column_order in permutations(range(n)):
    # this is an identity matrix with the columns swapped according to the permutation
    imatrix = np.zeros(A.shape)
    for row, column in enumerate(column_order):
        imatrix[row,column] = 1

    # is this map better than the previous best?
    if sum(sum(imatrix * A)) > sum(sum(best_map_so_far)):
        best_map_so_far = imatrix

    # could it be? a perfect map??
    if sum(sum(imatrix * A)) == n:
        break

if sum(sum(imatrix * A)) != n:
    print('a perfect map was not found')

output = pd.DataFrame(A*imatrix, columns=solution_matrix.columns, index=solution_matrix.index, dtype=int)
display(output)

Ответ 3

Предлагаемые подходы Arne и tinker были полезны, но не в конечном итоге достаточны. Я придумал гибридный подход, который решает его достаточно хорошо.

Основная проблема заключается в том, что это трехмерная проблема, которую трудно решить во всех измерениях одновременно. Это не просто совпадение совпадения времени или перекрытие тега, а согласование временных интервалов с перекрытием тегов. Это достаточно просто, чтобы сопоставить слоты с другими слотами на основе времени и даже тегов, но тогда довольно сложно сопоставить уже подходящий слот доступности с другим резервированием в другое время. Смысл, этот сценарий, в котором одна доступность может охватывать две оговорки в разное время:

+---------+
| A, B    |
+---------+
xxxxx xxxxx
x A x x A x
xxxxx xxxxx

Попытка подойти к этому в программировании на основе ограничений требует невероятно сложной связи ограничений, которая вряд ли управляема. Моим решением было упростить проблему...

Удаление одного измерения

Вместо того, чтобы одновременно решать все измерения, это значительно упрощает проблему, чтобы в значительной степени удалить измерение времени. Я сделал это, используя мое существующее дерево интервалов и нарезая его по мере необходимости:

def __init__(self, slots):
    self.tree = IntervalTree(slots)

def timeslot_is_available(self, start: datetime, end: datetime, attributes: set):
    candidate = Slot(start.timestamp(), end.timestamp(), dict(type=SlotType.RESERVED, attributes=attributes))
    slots = list(self.tree[start.timestamp():end.timestamp()])
    return self.model_is_consistent(slots + [candidate])

Чтобы узнать, доступен ли конкретный слот, я беру только соответствующие слоты в это конкретное время (self.tree[..:..]), что уменьшает сложность вычисления до локализованного подмножества:

  |      |             +-+ = availability
+-|------|-+           xxx = reservation
  |  +---|------+
xx|x  xxx|x
  |  xxxx|
  |      |

Затем я подтверждаю согласованность внутри этого узкого фрагмента:

@staticmethod
def model_is_consistent(slots):
    def can_handle(r):
        return lambda a: r.attributes <= a.attributes and a.contains_interval(r)

    av = [s for s in slots if s.type == SlotType.AVAILABLE]
    rs = [s for s in slots if s.type == SlotType.RESERVED]

    p = Problem()
    p.addConstraint(AllDifferentConstraint())
    p.addVariables(range(len(rs)), av)

    for i, r in enumerate(rs):
        p.addConstraint(can_handle(r), (i,))

    return p.getSolution() is not None

(Здесь я опускаю некоторые оптимизации и другие коды.)

Эта часть представляет собой гибридный подход предложений Арне и возиться. Он использует программирование на основе ограничений, чтобы найти соответствующие слоты, используя матричный алгоритм, предложенный мастером. В принципе: если какое-либо решение этой проблемы, в которой все оговорки могут быть назначены для другого доступного слота, тогда этот срез времени находится в согласованном состоянии. Поскольку я прохожу в желаемом слоте резервирования, если модель все еще непротиворечива, включая этот слот, это означает, что это безопасно зарезервировать этот слот.

Это все еще проблематично, если в этом узком окне есть две короткие оговорки, назначаемые для одной и той же доступности, но вероятность этого низкая, а результат - всего лишь ложный отрицательный результат для запроса доступности; ложные срабатывания будут более проблематичными.

Поиск доступных слотов

Поиск всех доступных слотов является более сложной задачей, поэтому необходимо еще некоторое упрощение. Во-первых, можно только запросить модель для доступности для определенного набора тегов (там нет "дать мне все доступные по всему миру слоты" ), а во-вторых, его можно запросить только с определенной детализацией (желаемая длина слота). Это подходит мне для моего конкретного случая использования, в котором мне просто нужно предложить пользователям список слотов, которые они могут зарезервировать, например 9: 15-9: 30, 9: 30-9: 45 и т.д. Это делает алгоритм очень просто, повторно используя приведенный выше код:

def free_slots(self, start: datetime, end: datetime, attributes: set, granularity: timedelta):
    slots = []
    while start < end:
        slot_end = start + granularity
        if self.timeslot_is_available(start, slot_end, attributes):
            slots.append((start, slot_end))
        start += granularity

    return slots

Другими словами, он просто проходит через все возможные слоты в течение заданного интервала времени и буквально проверяет, доступен ли этот слот. Это немного решение грубой силы, но отлично работает.