Анализ эффективности алгоритма редукции в решении задачи об упаковке в контейнеры

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