Алгоритм нахождения структуры оптимального подмножества на основе паретовских слоев в задаче о ранце

  • Сергей Викторович Чебаков Объединенный институт проблем информатики Национальной академии наук Беларуси, ул. Сурганова, 6, 220012, г. Минск, Беларусь
  • Лия Валентиновна Серебряная Белорусский государственный университет информатики и радиоэлектроники, ул. П. Бровки, 6, 220013, г. Минск, Беларусь https://orcid.org/0000-0001-7189-7378
DOI: https://doi.org/10.33581/2520-6508-2020-2-97-104

Аннотация

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

Биографии авторов

Сергей Викторович Чебаков, Объединенный институт проблем информатики Национальной академии наук Беларуси, ул. Сурганова, 6, 220012, г. Минск, Беларусь

кандидат физико-математических наук; старший научный сотрудник лаборатории вычислительных сетей

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

кандидат технических наук, доцент; доцент кафедры программного обеспечения информационных технологий факультета компьютерных  систем и сетей

Литература

  1. Мartello S, Toth P. Knapsack problems: algorithms and computer implementations. Chichester: John Wiley & Sons; 1990. 308 p.
  2. Posypkin MA, Sigal IKh. Parallel combined algorithm for solving knapsack problems. In: Proceedings of the 4th International conference «Parallel computations and control problems»; 2008 October 27–29; Moscow, Russia. Moscow: Institute of Control Sciences; 2008. p. 177–189. Russian.
  3. Chebakov SV. [Two-criteria model for constructing an optimal subset of alternatives with a maximum total probability of achieving a goal]. Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series. 2005;2:112–118. Russian.
  4. Chebakov SV, Serebryanaya LV. Finding of optimal subset structure in the knapsack problem. Doklady BGUIR. 2019;6:72–79. Russian. DOI: 10.35596/1729-7648-2019-124-6-72-79.
  5. Kung HT, Luccio F, Preparata FP. On finding the maxima of a set of vectors. Journal of the Association for Computing Machinery. 1975;22(4):469–476.
Опубликован
2020-07-30
Ключевые слова: задача о ранце, многокритериальная оптимизация, множество Парето, паретовский слой
Как цитировать
Чебаков, С. В., & Серебряная, Л. В. (2020). Алгоритм нахождения структуры оптимального подмножества на основе паретовских слоев в задаче о ранце. Журнал Белорусского государственного университета. Математика. Информатика, 2, 97-104. https://doi.org/10.33581/2520-6508-2020-2-97-104
Выпуск
№ 2 (2020): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Дискретная математика и математическая кибернетика

Copyright (c) 2020 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).