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

Что у вас тут происходит?

Алгоритм получает на вход:

• массив «отрезков» (структур с полями ДанныеОтрезка и ДлинаОтрезка);

• целевую сумму;

• количество итераций повторного поиска (по умолчанию 15).

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

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

Как это работает (немного магии)

Разберу ключевые моменты на примере кода.

1. Основной цикл – перебор итераций

Для каждой итерации мы сбрасываем переменные:

• МассивПодходящихОтрезков – текущая комбинация;

• КоэффициентПогрешности = 0 – сначала пытаемся уложиться точно;

• РезультатСложенияОтрезков = 0;

• НижняяГраница = ЦелеваяСумма, ВерхняяГраница = ЦелеваяСумма.

Затем запускаем внутренний цикл, который продолжается, пока результат не попадёт в границы или пока не сработает флаг УвеличитьТочность (о нём чуть позже).

2. Правила добавления отрезков

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

• Если Результат + ДлинаОтрезка <= ВерхняяГраница – отрезок добавляется.

• Если нет – вызывается функция ВыбратьСамыйПодходящийОтрезок, которая среди всех доступных ищет отрезок, максимально приближающий оставшуюся длину к цели, но не выходящий за верхнюю границу.

Если и такой не находится – значит, мы зашли в тупик. Тогда удаляем последний добавленный отрезок и увеличиваем коэффициент погрешности на 0.01 (т.е. разрешаем итоговой сумме отклоняться на 1% от цели в обе стороны). Это ключевой механизм «отступления»: алгоритм постепенно расширяет допустимый коридор, пока не сможет завершить комбинацию.

3. «Доводка» точности

Когда сумма уже находится в пределах границ, алгоритм не останавливается, а пытается её улучшить. Для этого он снова ищет самый подходящий отрезок (по разнице с оставшейся длиной). Если добавление этого отрезка уменьшает разницу с целевой суммой, он добавляется, и если после этого сумма стала меньше цели – выставляется флаг УвеличитьТочность. Это заставляет внутренний цикл продолжиться, давая шанс добавить ещё отрезков и приблизиться к цели ещё ближе.

4. Отбор лучшей комбинации

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

Плюсы, которые меня порадовали

1. Скорость. Даже при 15 итерациях и массиве из 30–40 элементов алгоритм отрабатывает за доли секунды. Никаких вложенных переборов, всё линейно относительно количества итераций и размера массива.

2. Адаптивность. За счёт плавающего коэффициента погрешности и механизма возврата алгоритм сам «нащупывает» возможную комбинацию, даже если точное попадание невозможно.

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

4. Регулируемая точность. Параметр КоличествоИтерацийПовторногоПоиска позволяет найти баланс между скоростью и вероятностью нахождения оптимального решения. В моих тестах 15 итераций дают 99% точных попаданий.

Подводные камни и как можно улучшить

Конечно, идеального не бывает, и у этого подхода есть свои ограничения.

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

• Маленькие отрезки огромные суммы. С данной комбинацией алгоритм хорошо справляется, но, например, если средняя длинна отрезка у вас 100, то при установке целевой суммы в 10 000 000, алгоритм будет искать значение ~20секунд (значительно быстрее если снизить количество итераций повторного поиска).

• Не учитывает возможность повторного использования отрезков. В текущей реализации каждый отрезок может быть выбран несколько раз? Да, так как выбор случайный, то в процессе построения комбинации один и тот же отрезок может быть добавлен повторно. Это может быть как плюсом (если нужно многократное использование), так и минусом (если отрезки уникальны). При необходимости легко добавить проверку на уникальность.

Где это можно применить в 1С

Я использовал этот алгоритм для:

• Комплектации заказов – подбор товаров на складе по сумме заказа (с учётом веса или стоимости).

• Раскроя материалов – из заготовок разной длины нужно набрать детали с минимальным отходом.

• Оптимизации тары – подобрать коробки так, чтобы они максимально заполнили контейнер по объёму.

• Формирование путевых листов - если нет точной информации о том, где проехал водителей за месяц свои 1000 км, то можно подобрать маршруты так, что они будет равны этим 1000 км.

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

Вместо заключения

Я не претендую на то, что мой алгоритм – панацея, но он честно решает поставленную задачу. Главное его достоинство – в простоте и скорости. Если вам нужно быстро получить результат с высокой точностью, тогда этот код станет отличным инструментом.

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

Все исходники прилагаются. Удачи в автоматизации!

Полный код обработки для теста и сам алгоритм:

// Процедура - Выполнить алгоритм
//
// Параметры:
//  МассивОтрезков	 					- Пример элемента: Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №1", 120 )).  
//  ЦелеваяСумма	 					- Число, которое нужно получить из отрезков. 
//  КоличествоИтерацийПовторногоПоиска  - Повышает точность, уменьшает скорость выполнения.
//
Процедура ВыполнитьАлгоритм(МассивОтрезков, ЦелеваяСумма, КоличествоИтерацийПовторногоПоиска = 15)
	
	//ОсновныеПеременные
	ГенераторСлучайныхЧисел    = Новый ГенераторСлучайныхЧисел();
	МассивПодходящихКомбинаций = Новый Массив;
	КоличествоЭлементовМассива = МассивОтрезков.Количество();
	НайденаТочнаяКомбинация    = Ложь;
	
	Если КоличествоЭлементовМассива И ЦелеваяСумма Тогда
		Для Счетчик = 0 По КоличествоИтерацийПовторногоПоиска Цикл
			
			МассивПодходящихОтрезков = Новый Массив;
			УвеличитьТочность = Ложь;
			ПовыситьКоэффициентПогрешности = Ложь;
			КоэффициентПогрешности = 0; //Устанавливаем начальную возможную погрешность, но сначала пробуем найти комбинации без неё.
			РезультатСложенияОтрезков = 0; //Сумма длин отрезков, добавляемых в массив.                 
			НижняяГраница = ЦелеваяСумма;  //Нижний предел за границы которого не может выйти фактическая сумма.  (меняется в зависимости от коэффициента погрешности)
			ВерхняяГраница = ЦелеваяСумма; //Верхний предел за границы которого не может выйти фактическая сумма. (меняется в зависимости от коэффициента погрешности)
			Пока (РезультатСложенияОтрезков <= НижняяГраница ИЛИ РезультатСложенияОтрезков >= ВерхняяГраница) ИЛИ УвеличитьТочность Цикл
				НижняяГраница  = ЦелеваяСумма * (1 - КоэффициентПогрешности); //Если отрезки будут выходить за пределы данных границ, тогда будем расширять эти границы и цикл не будет бесконечным.
				ВерхняяГраница = ЦелеваяСумма * (1 + КоэффициентПогрешности);

		    	СлучайныйИндекс = ГенераторСлучайныхЧисел.СлучайноеЧисло(0, КоличествоЭлементовМассива - 1);
				Отрезок = МассивОтрезков[СлучайныйИндекс];
				ДлинаОтрезка = Отрезок.ДлинаОтрезка;
				ОставшаясяДлина = ЦелеваяСумма - РезультатСложенияОтрезков;
				
				Если РезультатСложенияОтрезков + ДлинаОтрезка <= ВерхняяГраница Тогда //Если случайный отрезок не превышает верхнюю границу целевой суммы, то добавляем его.
					РезультатСложенияОтрезков = РезультатСложенияОтрезков + ДлинаОтрезка;
					МассивПодходящихОтрезков.Добавить(Отрезок);
					ОставшаясяДлина = ЦелеваяСумма - РезультатСложенияОтрезков;
				Иначе //Если случайный отрезок превышает верхнюю границу целевой суммы, то ищем тот который подойдет.
					Отрезок = ВыбратьСамыйПодходящийОтрезок(МассивОтрезков, ОставшаясяДлина, ВерхняяГраница, РезультатСложенияОтрезков);
					Если Отрезок <> Неопределено Тогда 
						РезультатСложенияОтрезков = РезультатСложенияОтрезков + Отрезок.ДлинаОтрезка;
	                	МассивПодходящихОтрезков.Добавить(Отрезок);
						ОставшаясяДлина = ЦелеваяСумма - РезультатСложенияОтрезков;
					Иначе //Если ни один случайный отрезок не подходит, тогда удаляем из массива предыдущий отрезок и ищем снова, но приэтом добавляя + 1% погрешности для верхней и нижней границ.
						КоличествоПодходящихОтрезков = МассивПодходящихОтрезков.Количество();
						Если КоличествоПодходящихОтрезков Тогда //Проверка на случай если отрезков еще не было добавлено в массив.
							РезультатСложенияОтрезков = РезультатСложенияОтрезков - МассивПодходящихОтрезков.Получить(КоличествоПодходящихОтрезков - 1).ДлинаОтрезка;
	                		МассивПодходящихОтрезков.Удалить(КоличествоПодходящихОтрезков - 1);	
						КонецЕсли;
						КоэффициентПогрешности = КоэффициентПогрешности + 0.01;
					КонецЕсли;
				КонецЕсли;
				
				Если РезультатСложенияОтрезков >= НижняяГраница И РезультатСложенияОтрезков <= ВерхняяГраница Тогда //Если сумма длин отрезков попала в диапозон. (НижняяГраница - - - ВерхняяГраница)
					Отрезок = ВыбратьСамыйПодходящийОтрезок(МассивОтрезков, ОставшаясяДлина, ВерхняяГраница, РезультатСложенияОтрезков); //Проверям можно ли получить наиболее близкое значение фактической суммы к целевой сумме.
					Если Отрезок <> Неопределено Тогда
						ОставшаясяДлинаПоДанномуОтрезку = ЦелеваяСумма - (РезультатСложенияОтрезков + Отрезок.ДлинаОтрезка); //Проверяем какая разница между целевой суммой и суммой длин отрезков с новым отрезком.
						Если ОставшаясяДлинаПоДанномуОтрезку < 0 Тогда
							ОставшаясяДлинаПоДанномуОтрезку = ОставшаясяДлинаПоДанномуОтрезку * (-1);
						КонецЕсли;
						
						Если ОставшаясяДлинаПоДанномуОтрезку < ОставшаясяДлина Тогда //Если разница между целевой суммой и суммой длин отрезков с новым отрезком меньше, чем была до этого, тогда добавляем этот новый отрезок. 
							РезультатСложенияОтрезков = РезультатСложенияОтрезков + Отрезок.ДлинаОтрезка;
	                		МассивПодходящихОтрезков.Добавить(Отрезок);
							Если РезультатСложенияОтрезков < ЦелеваяСумма Тогда //Если после добавления этого отрезка мы не вышли за пределы целевой суммы, тогда с помощью переменной <УвеличитьТочность> запускаем цикл ещё раз.
								УвеличитьТочность = Истина;
							КонецЕсли;	
						Иначе
							УвеличитьТочность = Ложь;
						КонецЕсли;
					Иначе
						УвеличитьТочность = Ложь;	
					КонецЕсли;
				КонецЕсли;
			КонецЦикла;
			МассивПодходящихКомбинаций.Добавить(Новый Структура("МассивПодходящихОтрезков, ДлинаОтрезка", МассивПодходящихОтрезков, РезультатСложенияОтрезков)); //Добавляем все полученные комбинации отрезков
			Если РезультатСложенияОтрезков = ЦелеваяСумма Тогда //Если сумма отрезков одной из комбинации равна целевой сумме, тогда мы нашли нужную комбинацию и прерываем цикл
				НайденаТочнаяКомбинация = Истина;
				Прервать;
			КонецЕсли;	
		КонецЦикла;	
	КонецЕсли;
	
	Если НайденаТочнаяКомбинация Тогда
		ПодходящаяКомбинация = МассивПодходящихКомбинаций.Получить(МассивПодходящихКомбинаций.Количество() - 1);	
	Иначе	
		ПодходящаяКомбинация = ВыбратьСамыйПодходящийОтрезок(МассивПодходящихКомбинаций, ЦелеваяСумма); // Если точная комбинация была не найдена, тогда из всех комбинаций выбираем самую точную с помощью дополнительной функции.
	КонецЕсли;
		
	//////////////////////////ВЫВОД_РЕЗУЛЬТАТОВ_ТЕСТА///////////////////////////////////////
	ЗаполнитьТЧРезультат(ПодходящаяКомбинация);
	//////////////////////////ВЫВОД_РЕЗУЛЬТАТОВ_ТЕСТА///////////////////////////////////////
КонецПроцедуры

Функция ВыбратьСамыйПодходящийОтрезок(МассивОтрезков, ОставшаясяДлина, ВерхняяГраница = 0, РезультатСложенияОтрезков = 0)
	ПодходящийОтрезок = Неопределено;
	ПерваяИтерация = Истина;
	МинимальнаяРазница = 0;
	Для каждого Стр Из МассивОтрезков Цикл //Ищем из всех отрезков отрезок с самой минимальной разницей между ним и значением, которого нам все еще не хватает до целевой суммы.
		Разница = ОставшаясяДлина - Стр.ДлинаОтрезка;
		Если Разница < 0 Тогда
			Разница = Разница * (-1);
		КонецЕсли;
		Если (ПерваяИтерация ИЛИ Разница < МинимальнаяРазница) И (Стр.ДлинаОтрезка + РезультатСложенияОтрезков <= ВерхняяГраница ИЛИ (ВерхняяГраница = 0 И РезультатСложенияОтрезков = 0)) Тогда
			МинимальнаяРазница = Разница;	
			ПодходящийОтрезок  = Стр;
			ПерваяИтерация = Ложь;
		КонецЕсли;
	КонецЦикла;
	
	Возврат ПодходящийОтрезок;
КонецФункции

&НаКлиенте
Процедура ВыполнитьАлгоритмНаКлиенте(Команда)
	////////////////////////////////ЗАПОЛНЯЕМ_ПАРАМЕТРЫ_ДЛЯ_ТЕСТА
	МассивОтрезков = Новый Массив;//////////////////////////////////////////////////////////////////                                                   
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №1", 120   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №2", 6     ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №3", 660   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №4", 6     ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №5", 10    ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №6", 14    ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №7", 14    ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №8", 20    ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №9", 10    ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №10", 30   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №11", 450  ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №12", 40   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №13", 30   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №14", 450  ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №15", 8	   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №16", 1200 ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №17", 23   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №18", 270  ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №19", 10   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №20", 20   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №21", 12   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №22", 20   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №23", 15   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №24", 52   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №25", 12   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №26", 28   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №27", 30   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №28", 260  ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №29", 10   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №30", 9    ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №31", 378  ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №32", 32   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №33", 10   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №34", 30   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №35", 28   ));//
	МассивОтрезков.Добавить(Новый Структура("ДанныеОтрезка, ДлинаОтрезка", "Отрезок №36", 30   ));//
	ВыполнитьАлгоритм(МассивОтрезков, ЦелеваяСумма, 15);///////////////////////////////НАЧИНАЕМ_ТЕСТ
	//////////////////////////////////////////////////
КонецПроцедуры

Процедура ЗаполнитьТЧРезультат(ПодходящаяКомбинация)
	//////////////////////////ВЫВОД_РЕЗУЛЬТАТОВ_ТЕСТА///////////////////////////////////////
	Результат.Очистить();
	ОбщаяДлина = 0;
	Для каждого Стр Из ПодходящаяКомбинация.МассивПодходящихОтрезков Цикл
		НСтр = Результат.Добавить();
		НСтр.ДанныеОтрезка = Стр.ДанныеОтрезка;
		НСтр.ДлинаОтрезка  = Стр.ДлинаОтрезка;
		ОбщаяДлина = ОбщаяДлина + Стр.ДлинаОтрезка;
	КонецЦикла;
	Разница = ОбщаяДлина - ЦелеваяСумма;
	Если Разница < 0 Тогда
		Разница = Разница * (-1);
	КонецЕсли;
	Погрешность = Разница / ЦелеваяСумма * 100;
	//////////////////////////ВЫВОД_РЕЗУЛЬТАТОВ_ТЕСТА///////////////////////////////////////
КонецПроцедуры

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

Функция ВыбратьСамыйПодходящийОтрезок(МассивОтрезков, ОставшаясяДлина, ВерхняяГраница = 0, РезультатСложенияОтрезков = 0)
	ПодходящийОтрезок = Неопределено;
	ПерваяИтерация = Истина;
	МинимальнаяРазница = 0;
	Для каждого Стр Из МассивОтрезков Цикл //Ищем из всех отрезков отрезок с самой минимальной разницей между ним и значением, которого нам все еще не хватает до целевой суммы.
		Разница = ОставшаясяДлина - Стр.ДлинаОтрезка;
		Если Разница < 0 Тогда
			Разница = Разница * (-1);
		КонецЕсли;
		Если (ПерваяИтерация ИЛИ Разница < МинимальнаяРазница) И (Стр.ДлинаОтрезка + РезультатСложенияОтрезков <= ВерхняяГраница ИЛИ (ВерхняяГраница = 0 И РезультатСложенияОтрезков = 0)) Тогда
			МинимальнаяРазница = Разница;	
			ПодходящийОтрезок  = Стр;
			ПерваяИтерация = Ложь;
		КонецЕсли;
	КонецЦикла;
	
	Возврат ПодходящийОтрезок;
КонецФункции

Интерфейс обработки и несколько результатов по параметрам из кода выше:

P.S. Если у вас возникли вопросы или вы нашли способ улучшить алгоритм – пишите в комментариях, всегда открыт к обсуждению.