В практике автоматизации логистики и складского учета часто возникают задачи комбинаторной оптимизации. Одна из таких классических задач — распределение грузов с различными требованиями к условиям перевозки по минимальному количеству транспортных средств. Рассмотрим задачу на конкретном примере: необходимо определить минимальное количество грузовиков с термостатами для перевозки контейнеров, каждый из которых имеет свой допустимый температурный диапазон.
Особый интерес представляет требование решить эту задачу одним запросом, без использования постобработки в коде встроенного языка. Проанализируем предложенные подходы, разберем алгоритмическую суть проблемы и рассмотрим варианты реализации на языке запросов 1С.
Имеется N контейнеров. Для каждого задан температурный диапазон (от -100 до 100), внутри которого груз сохраняется. Грузовики оборудованы термостатами, поддерживающими одну фиксированную температуру. Вместимость грузовика считается неограниченной. Наша цель — найти минимальное количество грузовиков и для каждого указать температуру и список контейнеров.
Пример входных данных:
Нам необходимо сгруппировать эти строки так, чтобы внутри каждой группы существовало хотя бы одно число (температура), входящее в диапазоны всех контейнеров группы.
Прежде чем переходить к запросам, разберем, как эта задача решается классическим алгоритмическим путем. Это поможет нам понять логику, которую мы попытаемся переложить на язык запросов.
Суть задачи сводится к нахождению максимального кликового числа в интервальном графе или использованию алгоритма сканирующей прямой (sweep line). Рассмотрим процедурный подход, предложенный в обсуждении, который гарантированно дает верный результат.
Метод "Жадный алгоритм" с таблицей значений:
Этот метод надежен, но требует использования циклов и обработки таблиц значений в памяти, что противоречит условию "решить одним запросом".
Попытка решить задачу одним SELECT (ВЫБРАТЬ) сталкивается с проблемой отсутствия рекурсии в старых версиях платформы 1С. Запрос оперирует множествами, и "выкинуть" уже распределенные контейнеры для следующей итерации внутри одного простого запроса крайне сложно.
Тем не менее, рассмотрим вариант запроса, который позволяет найти пересечения и попытаться сгруппировать данные.
Сначала поместим входные данные во временную таблицу. Это стандартная практика для сложных запросов.
ВЫБРАТЬ
Т.Номер КАК Номер,
Т.НижТемп КАК НижТемп,
Т.ВерхТемп КАК ВерхТемп
ПОМЕСТИТЬ Данные
ИЗ
&Т КАК Т
;
Основная идея решения запросом заключается в том, чтобы соединить таблицу саму с собой. Мы ищем пары контейнеров, которые могут ехать вместе. Условие пересечения двух интервалов [A, B] и [C, D] выглядит так: A <= D И B >= C.
В обсуждении было предложено следующее решение, использующее левое соединение для поиска перекрывающихся диапазонов:
ВЫБРАТЬ
Т.Номер КАК Номер,
Т2.Номер КАК Номер2,
Т.НижТемп КАК НижТемп,
Т.ВерхТемп КАК ВерхТемп
ПОМЕСТИТЬ Наборы
ИЗ
Данные КАК Т
ЛЕВОЕ СОЕДИНЕНИЕ Данные КАК Т2
ПО (Т2.НижТемп = Т.НижТемп
ИЛИ Т.НижТемп = Т2.НижТемп) -- Обратите внимание на странное условие
;
Затем производится группировка, чтобы определить общую верхнюю границу для набора:
ВЫБРАТЬ
МИНИМУМ(Т.ВерхТемп) КАК ВерхТемп,
Т.Номер2 КАК Номер
ИЗ
Наборы КАК Т
СГРУППИРОВАТЬ ПО
Т.Номер2
УПОРЯДОЧИТЬ ПО
ВерхТемп
;
В ходе обсуждения данного решения возник интересный спор касательно условия соединения. Обратим внимание на конструкцию:
ПО (Т2.НижТемп = Т.НижТемп ИЛИ Т.НижТемп = Т2.НижТемп)
С точки зрения математической логики и стандартного SQL, это условие избыточно. Выражение A = B тождественно B = A, поэтому A = B ИЛИ B = A равносильно просто A = B.
Однако, участники заметили, что в файловом варианте информационной базы удаление второй части (после ИЛИ) приводило к некорректной работе запроса (пропадали строки). В клиент-серверном (SQL) варианте запрос работал корректно и с одинарным условием.
Вывод: Это может свидетельствовать об особенностях работы оптимизатора запросов файловой версии 1С или специфическом баге платформы в конкретном релизе. Если вы сталкиваетесь с подобным поведением, рекомендуется перепроверить логику условия. Для надежного поиска пересечений (а не только совпадений границ) правильнее использовать неравенства:
ПО Т.НижТемп <= Т2.ВерхТемп И Т.ВерхТемп >= Т2.НижТемп
Важно понимать, что представленное выше решение запросом является лишь приближением. Оно хорошо работает для простых случаев, но может давать сбои на сложных "цепочках" пересечений.
Разберем пример, где простая логика может ошибиться:
Контейнер 1 пересекается с 2 (в точке 10). Контейнер 2 пересекается с 3 (в точке 20). Но 1 и 3 не пересекаются. Если мы попытаемся объединить их по принципу "кто с кем пересекается", мы можем ошибочно попытаться запихнуть их в один грузовик, но общей температуры для всех троих (0..10, 10..20, 20..30) не существует.
Для корректного решения задачи "упаковки" (bin packing) или раскраски интервального графа запросом требуется итерационный подход:
В обычных запросах 1С (без использования циклов во встроенном языке) это реализовать невозможно, так как язык запросов декларативен и не поддерживает изменение состояния данных между шагами выборки внутри одного пакета (за исключением использования сложных временных таблиц с искусственной нумерацией, что делает код крайне громоздким).
Если перед вами стоит производственная задача распределения грузов по температурным режимам, рекомендуем следующий комбинированный подход:
Для Каждого) и алгоритм "Сканирующей прямой" или жадный алгоритм. Это обеспечит O(N*logN) производительность и, главное, 100% корректность распределения, чего сложно добиться одним запросом.Пример логики для постобработки:
// Примерная структура алгоритма
Пока ТаблицаКонтейнеров.Количество() > 0 Цикл
// 1. Находим оптимальную температуру для оставшихся
// (можно перебором границ интервалов)
ЛучшаяТемпература = НайтиОптимальнуюТемпературу(ТаблицаКонтейнеров);
// 2. Формируем рейс
НовыйРейс = Результат.Добавить();
НовыйРейс.Температура = ЛучшаяТемпература;
// 3. Переносим подходящие контейнеры
МассивУдаления = Новый Массив;
Для Каждого Стр Из ТаблицаКонтейнеров Цикл
Если Стр.Ниж <= ЛучшаяТемпература И Стр.Верх >= ЛучшаяТемпература Тогда
// Добавляем в рейс
ЗаполнитьЗначенияСвойств(НовыйРейс.Контейнеры.Добавить(), Стр);
МассивУдаления.Добавить(Стр);
КонецЕсли;
КонецЦикла;
// 4. Удаляем распределенные
Для Каждого СтрУд Из МассивУдаления Цикл
ТаблицаКонтейнеров.Удалить(СтрУд);
КонецЦикла;
КонецЦикла;
Такой подход гарантирует, что ни один контейнер не будет потерян, и температурный режим будет соблюден строго. Попытки решить NP-полные задачи или сложные комбинаторные задачи одним SQL-запросом часто приводят к трудноуловимым ошибкам на граничных значениях.