Сортировка и обоснование выбора

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

Запись, ключ и порядок

Запись объединяет поля одного объекта. Например, у мероприятия есть начало и конец, у товара артикул, цена и статус. Ключ сортировки представляет признаки, по которым сравниваются записи. Сортировка переставляет целые записи, поэтому начало мероприятия сохраняет связь с его собственным концом. Независимая сортировка двух столбцов эту связь уничтожает.

Ключ из нескольких полей сравнивается последовательно: сначала первое, при равенстве второе, затем следующее. Такой порядок называют лексикографическим. Убывание и возрастание могут сочетаться. Пусть score обозначает балл, а number номер объекта. В Python при обычной сортировке ключ (-score, number) ставит больший балл раньше, а при равном балле меньший номер раньше.

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

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

Допустимость и критерии качества

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

При двух последовательных критериях сначала находится лучший основной результат. Лишь среди наборов с этим результатом сравнивается дополнительный. Например, для количества k и конца t сначала максимизируется k, затем t. Расписание из двух мероприятий с поздним концом не лучше расписания из трёх, каким бы ни был их конец. Сумма этих двух величин не выражает исходную цель.

Когда локальный выбор даёт лучший итог

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

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

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

Для положительных масс другое основание: сумма k самых лёгких объектов не больше суммы любых других k объектов. Поэтому, если даже минимальная сумма для k+1 не помещается, ни один набор такого размера не поместится. Этот довод относится к общей вместимости. При отдельных контейнерах нужно проверять соответствие каждой пары груз–контейнер.

Начальная часть и второй критерий

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

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

Аналогично первые k-1 самых лёгких грузов занимают минимальную массу и оставляют наибольший запас последнему. Однако это не универсальное правило "улучшить последний объект". Оно опирается на доказанное свойство префикса и конкретный второй критерий. Если дополнительная цель зависит сразу от нескольких замен, такого основания может не быть.

Состояние сохраняет важные различия

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

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

Если размеры ограничены целыми значениями до B, для каждого материала можно хранить массив максимумов по порогу размера. Значение при пороге x учитывает все уже обработанные коробки размером не меньше x. При движении от больших размеров к меньшим оно получается сравнением прежнего максимума и результатов текущего размера. Тогда запрос по порогу s+D не требует повторного просмотра всех коробок. Среди конечных состояний наибольшей длины выбирается нужный размер самой маленькой коробки.

Группировка и обработка событий

Группировка объединяет записи с общим признаком до дальнейшей обработки. Для свободных мест в одном ряду общим признаком служит ряд; для свободных кресел перед данным общим является номер кресла. После сортировки соседних занятых координат a<b число свободных целых позиций между ними равно b-a-1. В учебном примере между занятыми позициями 2 и 6 свободны 3,4,5: всего 6-2-1=3 позиции. Если для покупки выбирается последняя, пятая, перед ней остаются только третья и четвёртая: два свободных кресла. Поэтому покупаемое кресло уменьшает число свободных перед ним ещё на единицу.

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

В примере резервного копирования при переполнении ↗ сначала проверяется, поместится ли запрос. При превышении вместимости копируется прежнее содержимое, а запрос добавляется после очистки. Объём копии и время её создания относятся к разным частям события: объём существовал до запроса, время задаётся вызвавшим копирование запросом. Сохранение этого порядка важнее самого факта сортировки.

От обоснования к решению

Почему раннее окончание помогает получить максимальное количество мероприятий, но не даёт сразу самый поздний конец последнего? Как дополнительное условие о материале коробок разрушает простой выбор самой большой? Эти вопросы рассмотрены на законченных и коротких примерах в статье "Задание №26. Сортировка и выбор объектов".