В производственных задачах на платформе 1С часто возникает необходимость подбора комплектующих с очень жесткими допусками. Рассмотрим типичную ситуацию: у нас есть два вида пружин, каждая из которых характеризуется двумя параметрами — высотой в свободном состоянии и прогибом. Нам необходимо собрать 4 набора по 8 пружин в каждом так, чтобы внутри одного набора разница между любыми двумя пружинами по обоим параметрам не превышала 2 мм. При этом важно максимально эффективно использовать имеющийся складской запас, чтобы минимизировать необходимость закупки новых позиций.
В этой статье мы подробно проанализируем, как отойти от простого перебора и реализовать математически обоснованный алгоритм подбора, который обеспечит оптимальное заполнение комплектов.
Прежде всего, проанализируем условия. У нас есть двухмерное пространство параметров (X — высота, Y — прогиб). Ограничение в 2 мм означает, что если мы выберем одну пружину как эталон, все остальные пружины в наборе должны попасть в "квадрат" со стороной 4 мм (±2 мм от эталона) или, что более правильно, разница между максимальным и минимальным значением в группе не должна превышать 2 мм.
С точки зрения математики, мы имеем дело с метрикой Чебышёва. В отличие от привычного евклидова расстояния (корень из суммы квадратов), метрика Чебышёва определяет расстояние между точками как максимальную разность их координат. Именно она идеально подходит для нашей задачи.
Рассмотрим один из наиболее интуитивно понятных подходов — поиск "центра масс" или центроида. Этот метод позволяет найти наиболее "плотное" скопление пружин на складе и начать сборку именно с него.
Разберем алгоритм по шагам:
Проанализируем пример логики выбора на языке 1С для поиска подходящих кандидатов:
// Допустим, у нас есть ТаблицаПружин с колонками Параметр1 и Параметр2
// Текущие границы набора: Мин1, Макс1, Мин2, Макс2
Для Каждого СтрокаПружина Из ТаблицаПружин Цикл
// Проверяем, впишется ли новая пружина в ограничение 2 мм
НовыйМин1 = Мин(Мин1, СтрокаПружина.Параметр1);
НовыйМакс1 = Макс(Макс1, СтрокаПружина.Параметр1);
НовыйМин2 = Мин(Мин2, СтрокаПружина.Параметр2);
НовыйМакс2 = Макс(Макс2, СтрокаПружина.Параметр2);
Если (НовыйМакс1 - НовыйМин1 <= 2) И (НовыйМакс2 - НовыйМин2 <= 2) Тогда
// Пружина подходит, добавляем в список потенциальных кандидатов
КонецЕсли;
КонецЦикла;
Если нам нужна максимальная эффективность, рассмотрим задачу как поиск максимальных клик в графе. Представим каждую пружину как вершину графа. Проведем ребро между двумя вершинами, если пружины совместимы (разница параметров ≤ 2 мм).
В этом случае наша задача — найти в графе полные подграфы (клики) размером 8. Выясним преимущества этого метода: он гарантирует, что любая пружина внутри набора совместима с любой другой пружиной этого же набора. Для реализации в 1С можно использовать упрощенный алгоритм Брона-Кербоша, однако стоит учитывать, что при большом количестве пружин (более 500) вычислительная сложность может возрасти.
Поскольку параметров два, обычная сортировка по одному из них (например, только по высоте) будет неэффективной. Проанализируем ситуацию: пружина может идеально подходить по высоте, но иметь критическое отклонение по прогибу. Для ускорения поиска в 2D-пространстве в информатике используются KD-деревья.
Суть метода заключается в циклическом разделении пространства пополам то по одной, то по другой координате. Это позволяет выполнять запрос типа "найти всех соседей в радиусе 2 мм" за логарифмическое время O(log n), а не перебирать весь склад каждый раз.
Рассмотрим структуру поиска:
Одной из главных проблем, озвученных в обсуждении, является риск собрать три идеальных полных набора, из-за чего на четвертый не хватит всего одной пружины, которая "ушла" в первый набор. Чтобы избежать этого, применим поиск с возвратом.
Посмотрим на алгоритм действий:
Для эффективной работы в среде 1С:Предприятие рекомендуем придерживаться следующих правил:
Во-первых, используйте Таблицу Значений с индексами для предварительной фильтрации данных. Даже если вы не реализуете полноценное KD-дерево, простая предварительная сортировка по одному из параметров позволит вам использовать НайтиСтроки() для быстрого отсечения заведомо неподходящих вариантов.
Во-вторых, используйте геометрическую концепцию Bounding Box (ограничивающей рамки). Для каждого формируемого набора храните четыре числа: МинимальнаяВысота, МаксимальнаяВысота, МинимальныйПрогиб, МаксимальныйПрогиб. При проверке новой пружины вам достаточно сравнить её параметры с этими четырьмя числами, а не со всеми 7-ю пружинами, уже включенными в набор.
В-третьих, учитывайте требование по двум видам пружин. Поскольку пружины разных видов в наборе не связаны требованиями по отклонению между собой (только внутри своего вида), алгоритм следует запускать дважды независимо для каждого вида, а затем просто объединять результаты в карточке комплекта.
Выясним, какой метод выбрать. Если пружин на складе немного (до 100 штук), достаточно жадного алгоритма с методом центроидов. Если счет идет на тысячи, стоит задуматься о пространственной кластеризации (DBSCAN) или использовании упрощенных моделей линейного программирования.