algorithm - profe - operaciones con intervalos matemovil

Árbol de intervalos con dimensión agregada de concordancia de subconjuntos?

Question

Esta es una pregunta algorítmica sobre un problema algo complejo. La base es esta:

Un sistema de programación basado en ranuras disponibles y ranuras reservadas . Las tragamonedas tienen ciertos criterios, llamémoslas etiquetas . Las etiquetas hacen coincidir una reserva con una ranura disponible si el conjunto de etiquetas de la ranura disponible es un superconjunto de la ranura reservada.

Como ejemplo concreto, tomemos este escenario:

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

Entre las 11:00 a las 12:30 se pueden hacer reservas para las etiquetas A y B , de 12:00 a 13:30 C y D está disponible, y hay una superposición de aproximadamente 12:00 a 12:30.

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

Aquí se ha realizado una reserva para A , por lo que no se pueden hacer otras reservas para A o B entre las 11: 15-ish y las 12: 00-ish.

Esa es la idea en pocas palabras. No hay limitaciones específicas para las ranuras disponibles:

• una ranura disponible puede contener cualquier número de etiquetas
• cualquier número de ranuras puede superponerse en cualquier momento
• las ranuras son de longitud arbitraria
• Las reservas pueden contener cualquier número de etiquetas.

La única regla que debe ser obedecida en el sistema es:

• al agregar una reserva, al menos una ranura disponible restante debe coincidir con todas las etiquetas en la reserva

Para aclarar: cuando hay dos ranuras disponibles al mismo tiempo con, digamos, la etiqueta A , entonces se pueden hacer dos reservas para A en ese momento, pero no más.

Tengo que trabajar con una implementación modificada de un árbol de intervalos ; como una visión general rápida:

• todas las ranuras disponibles se agregan al árbol de intervalos (se conservan duplicados / superposiciones)
• Todas las ranuras reservadas están iteradas y:
  • Todas las ranuras disponibles que coincidan con el momento de la reserva se consultan desde el árbol.
  • el primero de los que coinciden con las etiquetas de la reserva se corta y la porción se elimina del árbol

Cuando finaliza ese proceso, lo que queda son las porciones restantes de las ranuras disponibles, y puedo consultar si se puede hacer una nueva reserva para un tiempo determinado y agregarla.

Las estructuras de datos se ven algo así:

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

Las etiquetas son en sí mismas objetos clave-valor, una lista de ellas es un "conjunto de etiquetas". Esos podrían ser serializados si ayuda; Hasta ahora estoy usando un tipo de set Python que hace que la comparación sea lo suficientemente fácil. Los tiempos de inicio / finalización de la ranura son sellos de tiempo UNIX dentro del árbol. No estoy particularmente casado con estas estructuras de datos específicas y puedo refactorizarlas si es útil.

El problema al que me enfrento es que esto no funciona sin errores; De vez en cuando, una reserva se abre camino en el sistema que entra en conflicto con otras reservas, y aún no pude averiguar cómo puede suceder eso exactamente. Tampoco es muy inteligente cuando las etiquetas se superponen de una manera compleja donde se necesita calcular la distribución óptima para que todas las reservas puedan ajustarse lo mejor posible en las ranuras disponibles; de hecho, actualmente no es determinista cómo las reservas se comparan con las ranuras disponibles en escenarios superpuestos.

Lo que quiero saber es: los árboles de intervalo son en su mayoría geniales para este propósito, pero mi sistema actual para agregar la coincidencia de conjuntos de etiquetas como una dimensión adicional a esto es anticuado y está activado; ¿Existe una estructura de datos o un algoritmo que pueda manejar esto de una manera elegante?

Acciones que deben ser apoyadas:

1. Consultar en el sistema las ranuras disponibles que coinciden con ciertos conjuntos de etiquetas (teniendo en cuenta las reservas que pueden reducir la disponibilidad pero que no forman parte de dicho conjunto de etiquetas; por ejemplo, en el ejemplo anterior que solicita una disponibilidad para B ).
2. Asegurarse de que no se puedan agregar reservas al sistema que no tienen una ranura disponible coincidente.

Answer 1

Aquí hay una solución, incluiré todo el código a continuación.

1. Crear una tabla de ranuras, y una tabla de reservas.

2. Crea una matriz de reservas x slots.

que se llena con valores verdaderos o falsos en función de si esa combinación de ranura de reserva es posible

3. Determine la mejor asignación que permita la mayoría de las combinaciones de ranuras de reserva

Nota: mi solución actual se adapta mal con arreglos muy grandes, ya que implica recorrer todas las posibles permutaciones de una lista con tamaño = número de ranuras. He publicado otra pregunta para ver si alguien puede encontrar una mejor manera de hacerlo. Sin embargo, esta solución es precisa y puede ser optimizada.

Código fuente de Python

Parte 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)

Parte 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)

Parte 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)

Answer 2

Los enfoques sugeridos por Arne y tinker fueron útiles, pero en última instancia no fueron suficientes. Se me ocurrió un enfoque híbrido que lo resuelve lo suficientemente bien.

El problema principal es que es un tema tridimensional, que es difícil de resolver en todas las dimensiones a la vez. No se trata solo de hacer coincidir una superposición de tiempo o una superposición de etiquetas, se trata de hacer coincidir segmentos de tiempo con superposiciones de etiquetas. Es lo suficientemente simple para hacer coincidir las ranuras con otras ranuras en función del tiempo e incluso las etiquetas, pero es bastante complicado hacer coincidir una ranura de disponibilidad ya coincidente con otra reserva en otro momento. Es decir, este escenario en el que una disponibilidad puede cubrir dos reservas en diferentes momentos:

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

Intentar encajar esto en la programación basada en restricciones requiere una relación de restricciones increíblemente compleja que es difícilmente manejable. Mi solución a esto fue simplificar el problema ...

Eliminando una dimensión

En lugar de resolver todas las dimensiones a la vez, simplifica enormemente el problema para eliminar en gran medida la dimensión del tiempo. Hice esto usando mi árbol de intervalos existente y cortándolo según sea necesario:

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

Para consultar si hay una ranura específica disponible, solo tomo las ranuras relevantes en ese momento específico ( self.tree[..:..] ), lo que reduce la complejidad del cálculo a un subconjunto localizado:

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

Entonces confirmo la consistencia dentro de esa rebanada estrecha:

@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

(Estoy omitiendo algunas optimizaciones y otros códigos aquí).

Esta parte es el enfoque híbrido de las sugerencias de Arne y Tinker. Utiliza la programación basada en restricciones para encontrar ranuras coincidentes, utilizando el algoritmo matricial sugerido por Tinker. Básicamente: si hay alguna solución a este problema en el que todas las reservas puedan asignarse a una ranura diferente disponible, entonces este segmento de tiempo se encuentra en un estado consistente. Ya que estoy pasando la ranura de reserva deseada, si el modelo sigue siendo consistente, incluida esa ranura, esto significa que es seguro reservar esa ranura.

Esto sigue siendo problemático si hay dos reservas breves asignables a la misma disponibilidad dentro de esta ventana estrecha, pero las posibilidades son bajas y el resultado es simplemente un falso negativo para una consulta de disponibilidad; Los falsos positivos serían más problemáticos.

Encontrando ranuras disponibles

Encontrar todas las ranuras disponibles es un problema más complejo, por lo que, de nuevo, es necesaria alguna simplificación. Primero, solo es posible consultar la disponibilidad del modelo para un conjunto particular de etiquetas (no hay "dame todas las ranuras disponibles globalmente") y, en segundo lugar, solo se puede consultar con una granularidad particular (longitud de ranura deseada). Esto me conviene para mi caso de uso particular, en el que solo necesito ofrecer a los usuarios una lista de espacios que pueden reservar, como 9: 15-9: 30, 9: 30-9: 45, etc. Esto hace que el algoritmo sea muy simple al reutilizar el código anterior:

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

En otras palabras, solo pasa por todas las ranuras posibles durante el intervalo de tiempo dado y, literalmente, comprueba si esa ranura está disponible. Es una solución de fuerza bruta, pero funciona perfectamente bien.

Answer 3

Su problema puede resolverse mediante la programación de restricciones . En Python, esto se puede implementar utilizando la biblioteca de python-constraint .

Primero, necesitamos una forma de verificar si dos ranuras son consistentes entre sí. esta es una función que devuelve verdadero si dos ranuras comparten una etiqueta y sus marcos de tiempo se superponen. En Python esto se puede implementar usando la siguiente función

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

No estaba seguro de si querías que las etiquetas fueran completamente iguales (como {foo: bar} es igual a {foo: bar}) o solo las teclas (como {foo: bar} es igual a {foo: qux}), pero puedes Cambia eso en la función de arriba.

Control de consistencia

Podemos usar el módulo de restricción de Python para los dos tipos de funcionalidad que solicitó.

La segunda funcionalidad es la más sencilla. Para implementar esto, podemos usar la función isConsistent(set) que toma una lista de ranuras en la estructura de datos provista como entrada. La función luego alimentará todas las ranuras a la restricción python y comprobará si la lista de ranuras es consistente (no hay 2 ranuras que no deban superponerse, se superpongan) y devolverá la consistencia.

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

Se puede llamar a esta función siempre que un usuario quiera agregar un espacio de reserva. La ranura de entrada se puede agregar a la lista de ranuras ya existentes y se puede verificar la consistencia. Si es consistente, la nueva ranura será reservada. De lo contrario, la nueva ranura se superpone y debe ser rechazada.

Encontrando ranuras disponibles

Este problema es un poco más complicado. Podemos usar la misma funcionalidad que antes con algunos cambios significativos. En lugar de agregar la nueva ranura junto con la ranura existente, ahora queremos agregar todas las ranuras posibles a las ranuras ya existentes. Luego, podemos verificar la consistencia de todas esas ranuras posibles con las ranuras reservadas y solicitar al sistema de restricciones las combinaciones que sean consistentes.

Debido a que el número de ranuras posibles sería infinito si no le pusiéramos restricciones, primero debemos declarar algunos parámetros para el programa:

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

Ahora podemos continuar con la función principal. Se parece mucho a la verificación de consistencia, pero en lugar de la nueva ranura del usuario, ahora agregamos una variable para descubrir todas las ranuras disponibles.

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())

Utilizo algunas funciones de ayuda para mantener el código limpio. Se incluyen aquí.

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)

Ahora puede usar la función getAvailableSlots (etiquetas, conjunto) con las etiquetas para las que desea las ranuras disponibles y un conjunto de ranuras ya reservadas. Tenga en cuenta que esta función realmente devuelve todas las ranuras posibles consistentes, por lo que no se hace ningún esfuerzo para encontrar el de longitud máxima o para otras optimizaciones.

¡Espero que esto ayude! (Lo hice funcionar como lo describiste en mi pycharm)