Preview

Доклады БГУИР

Расширенный поиск

ОПРЕДЕЛЕНИЕ СТРУКТУРЫ ОПТИМАЛЬНОГО ПОДМНОЖЕСТВА В ЗАДАЧЕ О РАНЦЕ

https://doi.org/10.35596/1729-7648-2019-124-6-72-79

Аннотация

Рассматривается алгоритм решения задачи о ранце на основе предлагаемой многокритериальной модели. Реализация алгоритма позволяет определить структуру оптимального подмножества в виде объединения определенных элементов группы паретовских слоев, на которые разбивается множество начальных данных. Первым таким слоем является множество Парето. Определение структуры оптимального подмножества позволяет найти такое подмножество начальных данных, элементы которого не могут войти в оптимальное подмножество. Наиболее трудоемкими являются задачи о ранце с большим набором начальных данных. В статье показано, что при небольшом значении объема ранца число элементов, требуемых для нахождения оптимального подмножества, значительно меньше их общего числа в исходном множестве, что может привести к существенному уменьшению общего времени решения комбинаторной задачи.  

Об авторах

С. В. Чебаков
Объединенный институт проблем информатики НАН Беларуси
Беларусь

Кандидат физико-математических наук, старший научный сотрудник

 



Л. В. Серебряная
Белорусский государственный университет информатики и радиоэлектроники
Беларусь

Серебряная Лия Валентиновна, кандидат физико-математических наук, доцент кафедры программного обеспечения информационных технологий

220013, г. Минск, ул. П. Бровки, 6



Список литературы

1. Альсведе Р., Вегенер И. Задачи поиска. М.: Мир, 1982. 367 c.

2. Посыпкин М.А. Комбинированный параллельный алгоритм решения задачи о ранце // Труды IV Междунар. конф. «Параллельные вычисления и задачи управления». Москва, 27–29 октября 2008 г. С. 177–189.

3. Martello S., Toth P. Knapsack Problems: Algorithms and Computer Implementations. N.Y.: John Wiley&Sons, 1990. 308 p.

4. Чебаков С.В. Двухкритериальная модель построения оптимального подмножества альтернатив с максимальной суммарной вероятностью достижения цели // Вести НАН Беларуси. Сер. физ.-мат. наук. 2005. № 2. С. 112–118.

5. Kung H.F., Preparata F.P. On finding the maxima of a set of vectors // Journal of the Association for Computing Machinery. 1975. Vol. 22. P. 469–476.


Рецензия

Для цитирования:


Чебаков С.В., Серебряная Л.В. ОПРЕДЕЛЕНИЕ СТРУКТУРЫ ОПТИМАЛЬНОГО ПОДМНОЖЕСТВА В ЗАДАЧЕ О РАНЦЕ. Доклады БГУИР. 2019;(6):72-79. https://doi.org/10.35596/1729-7648-2019-124-6-72-79

For citation:


Chebakov S.V., Serebryanaya L.V. FINDING OF OPTIMAL SUBSET STRUCTURE IN THE KNAPSACK PROBLEM. Doklady BGUIR. 2019;(6):72-79. (In Russ.) https://doi.org/10.35596/1729-7648-2019-124-6-72-79

Просмотров: 431


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1729-7648 (Print)
ISSN 2708-0382 (Online)