Информатика · объяснение и практика

Расписание с ценностью задач: почему раннее окончание уже не гарантирует оптимум

Выбрать совместимые полуоткрытые интервалы максимального суммарного веса и восстановить выбранные исходные задачи из динамики.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Методы алгоритмов: углубление · Учебная карта

Главная мысль

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

Метод и постановка

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

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

Проверка и границы вывода

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

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

Пример

Пусть задачи заданы как (начало,конец,вес): (0,3,5), (1,2,3), (2,4,4), (4,5,2). Первая задача с последней дают вес семь; задачи 2,3,4 дают девять.

Оптимальный вес равен девяти, выбранные исходные номера — 2,3,4. Общие точки времени два и четыре разрешены договорённостью о полуоткрытых интервалах.

От чтения к действию

А теперь — вы

Все интервалы имеют отрицательные веса, пустой набор разрешён. Каков оптимальный вес?

Частые вопросы

Кратчайший интервал всегда выгоднее?

Нет. При весах важна сумма ценностей совместимого набора, а не только количество интервалов.

Нужно брать отрицательный вес?

Нет. Пустой набор разрешён, поэтому отрицательная цель не навязывается.

Углублённый разбор

Расписание с ограничением числа выбранных задач

Ограничение числа выбранных задач требует ещё одной координаты динамики. Условия «не более K»и«ровно K»имеют разные начальные состояния и могут давать разные оптимальные расписания на одном входе.

Перед началом: Взвешенные интервалы; Динамическое программирование.

Бюджет относится к числу выбранных объектов

Отсортируем полуоткрытые интервалы по окончанию и найдём p(i) — последний совместимый предыдущий индекс. Пусть D(i,k) обозначает лучший вес среди первых i задач с использованием не более k. Тогда D(i,k)=max(D(i−1,k),wᵢ+D(p(i),k−1)) при k>0. Выбор текущей задачи уменьшает бюджет на единицу независимо от её длительности и веса.

Начальные значения D(i,0)=0 и D(0,k)=0 соответствуют разрешённому пустому набору. При отрицательном весе задачу можно пропустить, так что максимум остаётся неотрицательным. Число состояний O(nK), а после предварительного поиска p каждое заполняется за постоянное время. Бюджет больше n не создаёт новых полезных возможностей.

Ровно K требует явного состояния невозможности

Для точного числа выбранных задач рекурсия та же, но начальные значения другие:E(0,0)=0,E(0,k>0)=−∞. Это запрещает добавить один интервал к якобы готовому набору из несуществующего количества задач. Если поставить 0 всюду, точный режим незаметно превратится в режим «не более».

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

Не выводите ограниченный оптимум из одного неограниченного ответа

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

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

Один длинный против двух коротких

Условие. A=[0,2),B=[2,4),C=[4,6) имеют веса 5,5,5;D=[0,6) — вес 13. Сравните неограниченный оптимум, не более двух и ровно две задачи.

  1. Без ограничения выбираются A,B,C с суммой 15;D весит только 13.
  2. При не более двух любые две короткие дают 10, а одна D даёт 13. Поэтому ограниченный оптимум равен 13.
  3. При ровно двух D нельзя дополнить другой задачей, так как она перекрывает все три. Остаются пары коротких с весом 10.
  4. Таким образом, ответы 15,13,10 различаются. В точной DP переход к D из состояния пустого префикса с остаточным бюджетом 1 должен быть невозможным.

Ответ. Без бюджета 15;не более двух 13;ровно две 10.

Проверка. Полный перебор 16 подмножеств независимо подтверждает все три максимума. Пары A,B и B,C допустимы из-за полуоткрытых общих границ.

Где легко ошибиться. Нулевое начальное значение для невозможного точного количества делает задачу слабее. Используйте отдельный маркер−∞ и проверяйте размер восстановленного набора.

Проверьте понимание

Каков лучший вес при не более двух задачах?

Вопросы к этой главе

Нужно ли выбирать ровно K при положительных весах?

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

Можно сократить память до одного бюджета?

Требуются значения совместимых префиксов p(i), поэтому обычного соседнего слоя по i недостаточно без дополнительной структуры. Оптимизацию хранения нужно доказывать для конкретного порядка вычислений.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • UW CSE417: Weighted Interval Scheduling

    Первичное чтение курса: сверены совместимость при равном конце/начале и разбиение DP на выбор/пропуск. Дополнительная координата бюджета, случай ровно K и собственная четвёрка задач выведены отдельно.

Минимум комнат равен максимуму перекрытий интервалов

Чтобы выполнить все интервальные работы, нужно распределить их по минимальному числу ресурсов. Максимальное одновременное перекрытие даёт нижнюю границу, а жадное назначение по началу достигает её.

Перед началом: Полуоткрытый интервал; Приоритет по времени освобождения.

Каждое перекрытие требует разных ресурсов

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

Считаем интервалы[s,f) с s<f. Завершение в t освобождает комнату для старта в t. При проходе по событиям окончания обрабатываются раньше начал с тем же временем. Если порядок поменять, глубина будет завышена на общих границах. Нулевую длительность в эту модель не включаем, чтобы не создавать неоднозначных фиктивных потребителей ресурса.

Повторно используйте самую рано освобождённую комнату

Сортируем работы по началу. Для каждой смотрим минимальное время окончания среди занятых комнат. Если оно не больше нового начала, комнату можно использовать снова;иначе открываем новую. Куча окончаний позволяет выполнять проверку и обновление за O(logn), сохраняя номер комнаты для восстановления.

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

Другой критерий требует другого жадного порядка

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

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

Три одновременные работы

Условие. Даны A=[0,3),B=[1,4),C=[3,5),D=[4,6),E=[2,3). Найдите минимум комнат и одно распределение.

  1. В момент 2 активны A,B,E, поэтому нужны минимум 3 комнаты. Общие окончания A,E в 3 не пересекаются со стартом C.
  2. По началам распределяем A вкомнату 1,B в 2,E в 3. В 3 освободились 1 и 3;C можно назначить в 1.
  3. Для D в 4 можно использовать комнату 3, свободную с 3. Итог: комната 1 содержит A,C;комната 2 —B;комната 3 —E,D.
  4. Каждая комната имеет неперекрывающийся список. Использовано 3 ресурса, что совпадает с нижней границей глубины.

Ответ. Минимум 3 комнаты;подходит распределение{A,C},{B},{E,D}.

Проверка. Прямой подсчёт активных интервалов на всех промежутках между событиями даёт глубины 1,2,3,2,2,1. Ни одна граница не создаёт четвёртого одновременного потребителя.

Где легко ошибиться. Не считайте окончание и начало в одной точке одновременным занятием при договоре[s,f). Порядок событий является частью модели, а не только деталью сортировки.

Проверьте понимание

Сколько комнат необходимо в задаче?

Вопросы к этой главе

Почему выбирается минимальное окончание?

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

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

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Nisarg Shah: CSC373, Interval Partitioning

    Первичные авторские слайды: прочитаны полуоткрытые интервалы, нижняя граница depth и доказательство greedy≤depth. Собственные пять интервалов и порядок событий созданы отдельно; PrincetonPDF403 не выдаются за прочитанные.

Взвешенные интервалы на окружности: разрез нельзя выбрать произвольно

В периодическом расписании работа может начинаться до полуночи и завершаться после неё. Обычная сортировка окончаний после произвольного разреза теряет такие работы. Точный метод отдельно рассматривает отсутствие работы через разрез и каждый возможный выбор одной такой работы.

Перед началом: Взвешенное интервальное расписание на прямой; Полуоткрытые интервалы и совместимость границ.

Выбранные дуги могут пересечь разрез только по одной

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

Значит, все допустимые расписания разбиваются на исчерпывающие случаи. Первый не содержит ни одной дуги через разрез. Каждый следующий принудительно включает одну конкретную дугу, содержащую разрез. Остальные работы в таком случае должны целиком помещаться в её дополнение. Это дополнение разворачивается в обычный линейный промежуток.

Каждый остаток решается взвешенной динамикой

В линейном случае сортируем допустимые работы по окончанию. Обозначим p(j) индекс последней работы, заканчивающейся не позже начала j. Значение D(j) равно max(D(j−1), wj+D(p(j))), а D(0)=0. Переход сравнивает пропуск последней работы с её включением и оптимальным совместимым префиксом.

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

Проверяются и геометрия дуг, и целевая величина

Простой вариант перебирает не больше числа работ случаев и каждый раз заново решает линейную задачу. Это даёт полиномиальный алгоритм, например O(m² log m) при независимой сортировке каждого остатка. Более быстрые специальные методы возможны, но для корректности этого разбиения они не требуются.

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

Выгодная работа через границу периода

Условие. Период P=12. Работы заданы как начало→конец и вес: A:10→2,8; B:1→4,4; C:3→5,3; D:5→7,3; E:7→9,3; F:9→11,8; G:2→3,1; H:9→10,2. Найдите максимальный суммарный вес.

  1. Разрезаем в точке 0. Только A пересекает разрез. Поэтому достаточно двух случаев: не брать A либо обязательно взять A.
  2. Без A линейная динамика по окончаниям G,B,C,D,E,H,F даёт значения 1,4,4,7,10,12,18. Например, B,D,E,F дают допустимый вес 18.
  3. При включении A её дополнение равно [2,10). Работы B и F пересекаются с A и исключаются. Остаются G,C,D,E,H, которые идут подряд и имеют суммарный вес 12.
  4. С учётом A получаем вес 8+12=20. Общие границы 2 и 10 допустимы: A заканчивается перед G и начинается после H.
  5. Сравниваем оба исчерпывающих случая: max(18,20)=20. Оптимальное расписание состоит из A,G,C,D,E,H и содержит шесть работ.

Ответ. Максимальный вес равен 20; его достигает {A,G,C,D,E,H}.

Проверка. Полный перебор 256 подмножеств, с проверкой круговых пересечений через полуоткрытые части дуг, независимо даёт максимум 20. Ограничение без A даёт 18, что подтверждает необходимость второго случая.

Где легко ошибиться. Не удаляйте переходящие работы только потому, что их окончание численно меньше начала. Такое удаление исключает часть допустимых решений ещё до оптимизации.

Проверьте понимание

Каков максимальный суммарный вес кругового расписания из примера?

Вопросы к этой главе

Почему нельзя выбрать две работы через разрез?

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

Можно ли вместо динамики всегда выбирать раннее окончание?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • University of Washington CSE417: Weighted Interval Scheduling

    Раздел 2.1: разбор включения и пропуска последнего интервала, поиск совместимого префикса и взвешенная рекурсия. Круговой разбор случаев обоснован непосредственно в главе.

  • Chang et al.: maximum weight independent sets in circular-arc graphs

    Авторская университетская карточка исследования о максимальных взвешенных независимых множествах интервальных и круговых графов; связь постановок через пересечения дуг.

Два ресурса для взвешенных интервалов: поток по шкале времени

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

Перед началом: Полуоткрытые интервалы и совместимость на границе; Целочисленный поток минимальной стоимости.

Два пути передают два ресурса через всю шкалу

Два одинаковых ресурса, фиксированные полуоткрытые интервалы [a,b) с a<b и целые ценности; работу выбирают целиком не более одного раза, простой разрешён.

Сортируем все разные начала и окончания. Создаём по вершине на каждый момент и дугу простоя между соседними моментами с ёмкостью 2 и стоимостью 0. Из самого раннего момента в самый поздний требуется передать ровно две единицы. Поэтому оба ресурса существуют на всей шкале, даже если один не выполняет ни одной работы.

Для работы j добавляем дугу из aⱼ в bⱼ с ёмкостью 1 и стоимостью −wⱼ. Переход сразу к окончанию означает занятость ресурса на всём интервале. Все дуги идут строго вперёд во времени, так что исходная сеть ациклична; отрицательная стоимость работы не создаёт в ней отрицательного цикла.

Целочисленность превращает поток в расписания

Целочисленный поток величины 2 раскладывается на два пути. На одном пути следующие работы начинаются не раньше окончания предыдущей. Ёмкость рабочей дуги 1 запрещает использовать одну и ту же работу на обоих путях. Дуги простоя заполняют свободные промежутки без изменения полезности.

Обратно, два допустимых расписания задают два пути по соответствующим рабочим дугам и простоям. Их суммарная стоимость равна минус суммарной ценности выбранных работ. При целочисленных ёмкостях и требованиях обычная потоковая задача имеет целочисленный оптимум, поэтому минимальная стоимость сети даёт максимальную ценность исходного выбора.

Остаточная сеть может отменить ранний жадный выбор

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

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

Оптимальна сумма двух цепочек, а не всех полезных работ

Условие. Работы: A=[0,4),9; B=[1,3),8; C=[2,5),7; D=[3,6),8; E=[4,7),9; F=[5,7),5. Выберите максимум ценности для двух одинаковых ресурсов через сеть времени.

  1. Разные моменты равны 0,1,2,3,4,5,6,7. Между соседними создаём дуги простоя ёмкости 2, а шесть рабочих дуг имеют ёмкости 1 и стоимости −9,−8,−7,−8,−9,−5.
  2. Первый допустимый путь выполняет A, затем E с общей ценностью 18. Второй простаивает до 1, выполняет B, сразу в 3 начинает D и после 6 простаивает до конца. Его ценность 16.
  3. Два пути дают выбранный набор {A,B,D,E}, стоимость −34 и ценность 34. Общие границы 3 и 4 не создают конфликтов, поскольку интервалы полуоткрытые.
  4. Работу C нельзя просто добавить: в промежутке [2,3) уже заняты оба ресурса работами A,B. Работу F также нельзя добавить к этому набору из-за D,E на [5,6). Независимый перебор всех 64 наборов находит максимальную допустимую сумму 34.

Ответ. Оптимальная ценность 34, минимальная стоимость потока −34. Подходит распределение {A,E} и {B,D}.

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

Где легко ошибиться. Не заменяйте общий поток двумя независимыми оптимизациями одного ресурса. Ограничения совместного выбора работ связывают оба пути и требуют возможности перераспределения.

Проверьте понимание

Какова оптимальная суммарная ценность двух ресурсов в разобранном наборе шести работ?

Вопросы к этой главе

Почему требуется ровно две единицы, если можно использовать один ресурс?

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

Можно поставить ёмкость рабочей дуги 2?

Тогда одна работа могла бы дать ценность дважды, по одному разу на каждом ресурсе. В исходной постановке работа выбирается только один раз, поэтому её ёмкость равна 1.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Google OR-Tools — Minimum Cost Flows

    Первичная документация модели: стоимости, ёмкости и фиксированные балансы потока. Сведение двухресурсных интервалов, его двустороннее доказательство и шесть работ составлены отдельно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться