DOI: https://doi.org/10.24144/2616-7700.2017.1(30).133-142

Бінарні алгоритми пошуку лексикографічних екстремумів множин у задачах про покриття та упаковку скінченої множини

С. В. Чупов

Анотація


Однiєю з можливостей вiдшукання розв'язкiв задач про покриття та упаковку множини є алгоритми лексикографiчного пошуку. Ключовою складовою у таких алгоритмах є пошук лексикографiчних екстремумiв множин, якi є пiдмножинами множини допустимих розв'язкiв задачi. Коефiцiєнти матрицi обмежень у задачах про покриття та упаковку - булевi. Тому стовпцi матрицi обмежень задачi це булевi вектори, якi можна розглядати як цiлi числа, записанi у двiйковiй системi числення. У роботi описуються та обґрунтовуються алгоритми пошуку лексикографiчних екстремумiв множин для вищевказаних задач у яких, на вiдмiну вiд стандартних алгоритмiв лексикографiчного пошуку, усi дiї - порозряднi операцiї -and- i
-or- над стовпцями матрицi обмежень вiдповiдної задачi. Аналiз ефективностi роботи запропонованих алгоритмiв свiдчить про значну перевагу у порiвняннi з стандартними алгоритмами лексикографiчного пошуку.

Повний текст:

PDF

Посилання


Чупов С.В. Новые подходы к решению задач дискретного программирования на основе лексикографического поиска // Кибернетика и систем. анализ. -- 2016.-- № 4.-- С. 43--54.

Чупов С.В. Эффективные алгоритмы поиска лексикографического минимума множества// Компьютерная математика. -- К.: Ин-т кибернетики имени В.М. Глушкова НАН Украины, 2015.-- № 2.-- С. 123--131.

Чупов С.В. Модифікації алгоритму пошуку лексикографічного максимуму множини// Наук. вісник Ужгород. ун-ту. Сер. матем. і інформ. -- 2015.-- Вип. № 2(27). -- С. 168--173.


Посилання

  • Поки немає зовнішніх посилань.


Copyright (c) 2019 С. В. Чупов