Алгоритм сортировки для проблемы сортировки без сравнения?

Ответ 1

На самом деле это больше, чем проблема сортировки. Это проблема с одиночной машиной с датами выпуска. В зависимости от того, что вы пытаетесь сделать, проблема может быть NP-Hard. Например, если вы пытаетесь имитировать взвешенную сумму времени завершения (вес обратно пропорционален приоритету), проблема заключается в classized as

1|ri;pmtn|Σ wiCi 

и NP-жесткий. Есть многочисленные статьи по этой теме, но это может быть больше, чем вам нужно.

В вашем случае вы никогда не хотите решения с пробелами, поэтому вам может потребоваться простое моделирование дискретных событий (время O (n log (n))). Вам необходимо сохранить выпущенные_jobs в качестве очереди приоритетов.

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
    }
}

Одна из проблем заключается в том, что у вас может быть низкоприоритетное задание с временем освобождения непосредственно перед короткой высокоприоритетной задачей, но оно создаст расписание с тем свойством, что пробелов нет (если расписание без пробелов возможно).

Ответ 2

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

Кстати, решение jakber не работает. Даже без длительности, очевидно, следующий пример:

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

Сортированная последовательность будет a, b, а желаемый результат - b, a.

Ответ 3

Я думаю:

• Сортировка задач по приоритету
• Задайте задачи в строку времени, взяв первый доступный слот после их раннего времени, у которого есть отверстие, достаточно большое для задачи.

Преобразуйте строку времени в список задач и подождите (для пробелов).

Вопросы:

• Разрешены ли пробелы?
• Можно ли разделять задачи?
• Учитывая задачи, как в вопросе: лучше ли задержать b для завершения c, или d, чтобы b мог начать вовремя?

Edit:

О, ответы на мои вопросы:

• Нет (ish - если нечего запускать, я думаю, у нас может быть разрыв)
• Нет
• Все еще не понятно, но я предполагаю, что пример предлагает запустить c и задержать b.

В этом случае алгоритм может быть:

• Сортировка по приоритету
• Держите счетчик для текущего "времени", начиная с t = 0
• Найдите отсортированный список для элемента с наивысшим приоритетом, который можно запустить с помощью t.
• Добавьте элемент в выполняемый порядок и добавьте его продолжительность в t.
• Повторите 3 и 4 до тех пор, пока список не будет исчерпан. Если в t нет задач, выполняемых при t, а задачи остаются незавершенными, вставьте оставшуюся 1-секундную задачу ожидания в текущем порядке.

Этот алгоритм также O (n ^ 2).

Ответ 4

Я думаю, вам нужно отсортировать список дважды: сначала по приоритету, а затем по раннему времени, используя любой алгоритм сортировки стабильный, например, сортировка вставки. Таким образом, время будет увеличиваться, и каждый раз все будет сортироваться по приоритету.

Если вы ничего не видите, я не могу полностью игнорировать продолжительность каждого события с целью сортировки.

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

Ответ 5

Похоже, вы действительно хотите сортировку на основе сравнения. Ваш ключ сортировки - {earlyliestTime, priority}, в этом порядке. Поскольку ваш пример псевдо-С#, я дам вам псевдо-С# решение:

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 */
   }
}

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

ИЗМЕНИТЬ

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

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;
}

Проверьте это на любые предположения, но я думаю, что это то, что мы ищем.

Ответ 6

Если у вас ограниченный набор уровней приоритета, вы можете сохранить набор отсортированных по времени списков, по 1 для каждого уровня. Всякий раз, когда вам нужно следующее событие, проверьте главу каждого списка в порядке приоритета, пока не найдете тот, время начала которого прошло. (Отслеживайте минимальное время начала, пока вы не проверяете, пока событие еще не готово, вы знаете, какой из них ждать)

Ответ 7

Звучит как проблема, с которой я столкнулся на днях, на который был дан ответ здесь.
Предполагая, что вы используете С#...

Ответ 8

Кстати, в самом общем случае не может быть никакого решения (если не разрешены пробелы, как указал Дуглас). Например:

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 };

Ответ 9

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

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

Итак, продолжаем ли мы и начинаем b во время = 0, или мы ждем отметки, а затем запустим a, потому что это более высокий приоритет? Предположим, что было больше событий с большим количеством приоритетов и более длительных компромиссов. Я думаю, вам нужно правило по строкам "если следующее событие имеет более высокий приоритет X, а разрыв (между настоящим и самым ранним временем) меньше, чем Y секунд, ждать, а затем запускать событие с более высоким приоритетом, иначе начинать низкий приоритет событие (таким образом, отбрасывает высокоприоритетный)".

Ответ 10

Вот несколько кодов Python в соответствии с ответами Дугласа. Сначала мы сортируем по приоритету, затем мы устанавливаем временную шкалу в порядке сортировки:

#!/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