76231

Автор(ы): 

Автор(ов): 

4

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

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

ISBN/ISSN: 

0869-6527

DOI: 

10.14357/08696527230305

Наименование источника: 

  • Системы и средства информатики

Обозначение и номер тома: 

Т. 33. вып. 3.

Город: 

  • Москва

Издательство: 

  • ФИЦ ИУ РАН

Год издания: 

2023

Страницы: 

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

Библиографическая ссылка: 

Барашов Е.Б., Егоркин А.В., Лемтюжникова Д.В., Посыпкин М.А. Анализ эффективности алгоритма редукции в решении задачи об упаковке в контейнеры // Системы и средства информатики. 2023. Т. 33. вып. 3. С. 61-75.