Цель работы - это повышение эффективности методов и алгоритмов решения задачи нахождения покрытия. Под эффективностью понимается минимальная задержка процедуры, которая реализует данный метод. Для повышения эффективности метода "Разложение по столбцу" в процедуру построения дерева решения вводится характеристический вектор (ХВ), полученный суммированием единиц в столбцах/строках таблицы покрытия (ТП); он характеризует текущее состояние таблицы покрытия. Идея этого метода состоит в поэтапном разложении ТП на подтаблицы с использованием их сокращения по определенным правилам. Рассмотрены 3 способа сокращения исходной таблицы/текущих подтаблиц в методах: "Граничный перебор по вогнутому множеству"; "Использование свойств таблицы покрытия"; "Минимальный столбец - максимальная строка". В последнем способе впервые применен ХВ, который позволил до полутора раз ускорить процедуру нахождения покрытия. Вычисляются оценки сложности для рассмотренных методов покрытия; имеем: S1 = O(n^3); S2 = O(2^n); S3 = O(n^2), где n - определяющий параметр задачи о покрытии (количество столбцов), и определяются границы применимости данных методов. Показывается, что применение характеристических векторов в методах 1 и 2 нецелесообразно.

 Наукова періодика України 

---

Додаткова інформація про автора(ів) публікації:
(cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці)

• Комлева Наталія Олегівна (технічні науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"