c# - una - Algoritmo de clasificación para un problema de ordenamiento sin comparación

orden de un algoritmo

Question

Actualmente me encuentro con un problema de clasificación difícil. Tengo una colección de eventos que deben ordenarse uno contra el otro (un tipo de comparación ) y en contra de su posición relativa en la lista.

En los términos más simples, tengo una lista de eventos en los que cada uno tiene una prioridad (número entero), una duración (segundos) y un tiempo de aparición más temprano que el evento puede aparecer en la lista. Necesito ordenar los eventos según la prioridad, pero ningún evento puede aparecer en la lista antes de su primera aparición. Aquí hay un ejemplo para (con suerte) hacerlo más claro:

// Psuedo C# code
class Event { int priority; double duration; double earliestTime ; }

void Example()
{
    Event a = new Event { priority = 1, duration = 4.0, earliestTime = 0.0 };
    Event b = new Event { priority = 2, duration = 5.0, earliestTime = 6.0 };
    Event c = new Event { priority = 3, duration = 3.0, earliestTime = 0.0 };
    Event d = new Event { priority = 4, duration = 2.0, earliestTime = 0.0 };

    // assume list starts at 0.0 seconds
    List<Event> results = Sort( new List<Event> { a, b, c, d } );

    assert( results[ 0 ] == a ); // 4.0 seconds elapsed
    assert( results[ 1 ] == c ); // 7.0 seconds elapsed
    assert( results[ 2 ] == b ); // 12.0 seconds elapsed
    assert( results[ 3 ] == d ); // 14.0 seconds elapsed
}

El ítem "b" tiene que ser el último porque no está permitido comenzar hasta los 6.0 segundos en la lista, por lo que se difiere y "c" llega antes que "b" aunque su prioridad sea menor. (Espero que lo anterior explique mi problema, si no me lo diga y lo editaré).

Mi idea actual es usar una ordenación de inserción para administrar el proceso de clasificación. A diferencia de muchos de los otros algoritmos de clasificación comunes, el ordenamiento de inserción decide el orden de la lista de a uno por vez y en orden. Por lo tanto, para cada índice, debería poder encontrar el siguiente evento de prioridad más baja, cuya primera hora de ocurrencia será satisfecha.

Espero encontrar recursos sobre la clasificación de algoritmos y estructuras de datos para ayudarme a diseñar una buena solución para este "tipo" de problema. Mi problema real es en realidad más complejo que esto: clasificación jerárquica, búferes de variables entre eventos, restricciones de tiempo no constantes múltiples, de modo que cuanta más información o ideas, mejor. La velocidad y el espacio no son realmente una preocupación. La precisión en la clasificación y la mantenibilidad del código son una preocupación.

Editar: Aclaraciones (basadas en comentarios)

• Los eventos consumen toda su duración (es decir, no hay superposición de eventos permitidos)
• Los eventos deben ocurrir en o después de su hora más temprana, no pueden ocurrir antes de su hora más temprana.
• Los eventos pueden ocurrir más tarde que su hora más temprana si existen eventos de prioridad más baja
• Los eventos no pueden ser interrumpidos
• Existe una duración máxima de la suma de todos los eventos que pueden caber en una lista. Esto no se muestra arriba. (En realidad, la duración de todos los eventos será mucho mayor que la duración máxima de la lista de tiempos).
• No puede haber vacíos. (No hay agujeros para probar y rellenar).

Editar: respuesta

Mientras que David Nehme dio la respuesta que seleccioné, quería señalar que su respuesta es una especie de inserción en el corazón, y varias otras personas me proporcionaron inserciones de tipo respuestas de tipo. Esto confirma para mí que un tipo de inserción especializada es probablemente el camino a seguir. Gracias a todos por sus respuestas.

Answer 1

Aquí hay un código de Python en la línea de la respuesta de Douglas. Primero clasificamos por prioridad, luego ajustamos una línea de tiempo en una forma de selección y clasificación:

#!/usr/bin/env python
MIN_PRIORITY = 100

class Event(object):
    def __init__(self, name, priority, duration, earliestTime):
        self.name = name
        self.priority = priority
        self.duration = duration
        self.earliestTime = earliestTime
    def __str__(self):
        return "%-10s:  P %3d  D %3.1f  T %3.1f" % (self.name, self.priority, self.duration, self.earliestTime)

def sortEvents(_events):
    def comparePriority(event1, event2):
        if event1.priority < event2.priority: return -1
        if event1.priority > event2.priority: return 1
        return 0

    # Get a copy of the events and sort by priority
    events = [e for e in _events]
    events.sort(cmp=comparePriority)

    # Select one event at a time, checking for compatibility with elapsed time
    elapsedTime = 0.0
    sortedEvents = []
    while events:
        minGap = events[0].earliestTime - elapsedTime
        for e in events:
            currentGap = e.earliestTime - elapsedTime
            if currentGap < minGap:
                minGap = currentGap
            if currentGap <= 0.0:
                sortedEvents.append(e)
                elapsedTime += e.duration
                events.remove(e)
                break

        # If none of the events fits, add a suitable gap
        if minGap > 0:
            sortedEvents.append( Event("gap", MIN_PRIORITY, minGap, elapsedTime) )
            elapsedTime += minGap
    return sortedEvents

if __name__ == "__main__":
    #e1 = Event("event1", 1, 1.0, 4.0)
    #e2 = Event("event2", 2, 1.0, 6.0)
    #e3 = Event("event3", 3, 1.0, 8.0)
    #e4 = Event("event4", 4, 1.0, 10.0)

    e1 = Event("event1", 1, 4.0, 0.0)
    e2 = Event("event2", 2, 5.0, 6.0)
    e3 = Event("event3", 3, 3.0, 0.0)
    e4 = Event("event4", 4, 2.0, 0.0)

    events = [e1, e2, e3, e4]

    print "Before:"
    for event in events: print event
    sortedEvents = sortEvents(events)
    print "/nAfter:"
    for event in sortedEvents: print event

Answer 2

Creo que debería ordenar la lista dos veces: primero por prioridad y luego por primera vez, usando cualquier algoritmo de ordenación estable , por ejemplo, ordenar por inserción. De esta forma, el tiempo aumentará y cada vez las cosas se ordenarán por prioridad.

A menos que veas algo que yo no puedo, puedes ignorar por completo la duración de cada evento para este fin.

http://en.wikipedia.org/wiki/Category:Stable_sorts

Answer 3

Creo:

1. Clasificar tareas por prioridad
2. Ajuste las tareas en una línea de tiempo, tomando la primera ranura disponible después de su Tiempo más temprano, que tiene un agujero lo suficientemente grande para la tarea.

Convierte la línea de tiempo en una lista de tareas y espera (para las brechas).

Preguntas:

1. ¿Se permiten espacios?
2. ¿Se pueden dividir las tareas?
3. Dadas las tareas como en la pregunta: ¿es mejor retrasar b para completar c, o hacer d para que b pueda comenzar a tiempo?

Editar:

Os las respuestas a mis preguntas son:

1. No (ish - si no hay nada para correr, creo que podríamos tener una brecha)
2. No
3. Todavía no está claro, pero creo que el ejemplo sugiere ejecutar c y retrasar b.

En este caso, el algoritmo podría ser:

1. Ordenar por prioridad
2. Mantenga un contador para el ''tiempo'' actual que comienza con t = 0
3. Busque en la lista ordenada, para el elemento de mayor prioridad que se puede iniciar en t.
4. Agregue el artículo a la orden de ejecución y agregue su duración a t.
5. Repita 3 y 4 hasta que la lista se agote. Si no hay tareas ejecutables en t, y hay tareas pendientes, agregue una tarea de suspensión de 1 segundo en el orden de ejecución.

Este algoritmo también es O (n ^ 2).

Answer 4

En otras palabras, desea optimizar el tiempo de ejecución general al formular dos restricciones (fuerte: primer punto de ejecución, débil: prioridad)? Esto se llama un problema de satisfacción de restricción . Hay solucionadores especiales para este tipo de problema.

Por cierto, la solución de Jakber no funciona. Incluso sin la duración, el siguiente ejemplo obviamente falla:

event a (priority = 1, start = 5)
event b (priority = 2, start = 0)

La secuencia ordenada sería a , b , mientras que el resultado deseado es seguramente b , a .

Answer 5

Incidentalmente, en el caso más general, puede que no haya solución (a menos que se permitan vacíos, como señaló Douglas). Por ejemplo:

Event a = new Event { priority = 1, duration = 1.0, earliestTime = 4.0 };
Event b = new Event { priority = 2, duration = 1.0, earliestTime = 4.0 };
Event c = new Event { priority = 3, duration = 1.0, earliestTime = 4.0 };
Event d = new Event { priority = 4, duration = 1.0, earliestTime = 4.0 };

Answer 6

No estoy del todo seguro de entender las complejidades de su problema, pero mi instinto me dice que debe definir una relación entre la prioridad y la hora de inicio. El ejemplo sería:

Event a = new Event { priority = 1, duration = 4.0, earliestTime = 1.0 };
Event b = new Event { priority = 2, duration = 5.0, earliestTime = 0.0 };

Entonces, ¿seguimos adelante y comenzamos con b en el tiempo = 0, o esperamos un tic y luego comenzamos a porque es de mayor prioridad? Supongamos que hay más eventos con más prioridades y compensaciones a más largo plazo. Creo que necesita una regla del tipo "si el próximo evento tiene una prioridad X mayor y la brecha (entre ahora y el tiempo más temprano) es menor a Y segundos, espere y luego comience el evento de mayor prioridad. De lo contrario, comience la baja prioridad evento (por lo tanto, rechazando la prioridad alta) ".

Answer 7

Si tiene un conjunto limitado de niveles de prioridad, puede mantener un conjunto de listas ordenadas por tiempo, 1 para cada nivel. Siempre que necesite el próximo evento, verifique el encabezado de cada lista en orden de prioridad hasta que encuentre uno cuyo tiempo de inicio haya pasado. (Mantenga un registro de la hora mínima de inicio mientras realiza la verificación; en caso de que aún no haya ningún evento listo, sabe cuál esperar)

Answer 8

Esto es en realidad más que un problema de clasificación. Es un problema de programación de una sola máquina con fechas de lanzamiento. Dependiendo de lo que intente hacer, el problema podría ser NP-Hard. Por ejemplo, si está tratando de minimizar la suma ponderada de los tiempos de finalización (el peso es inversamente proporcional a la prioridad), el problema se clasificará como

1|ri;pmtn|Σ wiCi 

y es NP-difícil. Existen numerosos artículos sobre este tema, pero podría ser más de lo que necesita.

En su caso, nunca desea una solución con espacios vacíos, por lo que lo que podría necesitar es una simple simulación de eventos discretos (O (n log (n))). Necesitas almacenar releas_jobs como una cola de prioridad.

unreleased_jobs = jobs  // sorted list of jobs, by release date
released_jobs = {}      // priority queue of jobs, by priority
scheduled_jobs = {}     // simple list
while (!unreleased_jobs.empty() || !released_jobs.empty()) {

    while (unreleased_jobs.top().earliestTime  <= t) {
        released_jobs.push(unreleased_jobs.pop())
    }
    if (!released_jobs.empty()) {
       next_job = released_jobs.pop();
       scheduled_jobs.push_back(next_job)
       t = t + next_job.duration
    } else {
       // we have a gap
       t = unreleased_jobs.top().earliestTime
    }
}

Un problema es que puede tener un trabajo de baja prioridad con un tiempo de liberación justo antes de un trabajo corto de alta prioridad, pero producirá un cronograma con la propiedad de que no hay lagunas (si es posible un cronograma sin espacios vacíos) .

Answer 9

Parece que realmente quieres un tipo basado en la comparación. Su clave de clasificación es {earliestTime, priority}, en ese orden. Como tu ejemplo es pseudo-C #, te daré una solución pseudo-C #:

class Event : IComparable<Event>, IComparable{
    int    priority;
    double duration;
    double earliestTime;

    public int CompareTo(Event other){
        if(other == null)
            return 1; /* define: non-null > null */

        int cmp = earliestTime.CompareTo(other.earliestTime);
        if(cmp != 0)
            return cmp;

        /* earliestTimes were equal, so move on to next comparison */
        return priority.CompareTo(other.priority);
    }

   int IComparable.CompareTo(object other){ /* for compatibility with non-generic collections */
       if(other == null)
            return 1; /* define: non-null > null */

       Event e_other = other as Event;
       if(e_other == null) /* must have been some other type */
           throw new ArgumentException("Must be an Event", "other");

       return CompareTo(e_other); /* forward to strongly-typed implementation */
   }
}

Ahora su lista se ordenará tal como lo espera su afirmación.

EDITAR :

Mi presunción inicial era que los eventos serían eliminados de la lista y entregados a un hilo separado, para que el administrador de colas pudiera despedir el próximo evento a tiempo, pero por los comentarios que recibí, tuve la idea de que tal vez un enfoque que era un solo subproceso, pero todavía permitía que los eventos de mayor prioridad dispararan lo más cerca posible de su hora de inicio era más deseable. En ese caso, la función CompareTo debería cambiar de la siguiente manera:

public int CompareTo(Event other){
    if(other == null)
        return 1; /* define: non-null > null */

    int cmp = priority.CompareTo(other.priority);

    if(cmp == 0)
        /*
         * calculate and compare the time each event will be late
         * if the other one were to start first.  This time may be
         * negative if starting one will not make the other one late
         */
        return (earliestTime + duration - other.earliestTime).CompareTo(
            other.earliestTime + other.duration - earliestTime);

    /*
     * they''re different priorities. if the lower-priority event
     * (presume that greater priority index means lower priority,
     * e.g. priority 4 is "lower" priority than priority 1), would
     * would make the higher-priority event late, then order the
     * higher-priority one first.  Otherwise, just order them by
     * earliestTime.
     */
    if(cmp < 0){/* this one is higher priority */
        if(earliestTime <= other.earliestTime)
            /* this one must start first */
            return -1;

        if(other.earliestTime + other.duration <= earliestTime)
            /* the lower-priority event would not make this one late */
            return 1;

        return -1;
    }

    /* this one is lower priority */
    if(other.earliestTime <= earliestTime)
        /* the other one must start first */
        return 1;

    if(earliestTime + duration <= other.earliestTime)
        /* this event will not make the higher-priority one late */
        return -1;

    return 1;
}

Pruebe esto contra cualquier suposición, pero creo que es lo que estamos buscando.

Answer 10

Suena como un problema que tuve el otro día, que fue respondido aquí .
Suponiendo que estás usando C # ...