Об использовании особых структур данных в алгоритмах покрытия

Abstract

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

Мета даної роботи – це підвищення ефективності методів і алгоритмів вирішення задачі знаходження покриття. Під ефективністю розуміється мінімальна затримка процедури, яка реалізує даний метод. Для підвищення ефективності методу «Розкладання по стовпцю» в процедуру побудови дерева рішення вводиться характеристичний вектор (ХВ), отриманий підсумовуванням одиниць в стовпцях/рядках таблиці покриття (ТП); він характеризує поточний стан таблиці покриття. Ідея цього методу полягає в поетапному розкладанні ТП на підтаблиці з використанням їх скорочення за певними правилами. Розглядаються 3 способи скорочення вихідної таблиці / поточних підтаблиць в методах: 1) «Граничний перебір по увігнутій множини»; 2) «Використання властивостей таблиці покриття»; 3) «Мінімальний стовпець – максимальний рядок». В останньому способі вперше застосований ХВ, який дозволив до півтора разів прискорити процедуру знаходження покриття. Обчислюються оцінки складності для розглянутих методів покриття; маємо: S1 = O (n ^ 3); S2 = O (2 ^ n); S3 = O (n ^ 2), де n – визначальний параметр завдання про покриття (кількість стовпців), і визначаються межі застосування даних методів. Показується, що застосування характеристичних векторів в методах 1 і 2 недоцільно.

The aim of this work is to increase the efficiency of methods and algorithms for solving the problem of finding coverage. Efficiency is understood as the minimum delay of the procedure that implements this method. To increase the efficiency of the “Columnization” method, a characteristic vector (CV) is introduced into the decision tree construction procedure, obtained by summing the units in columns / rows of the coverage table (CT); it characterizes the current state of the coverage table. The idea of this method is to gradually decompose CT into sub-tables using their reduction according to certain rules. We consider 3 ways to reduce the original table / current sub-tables in the methods: 1) "Border search over a concave set"; 2) "Using the properties of the coverage table"; 3) "The minimum column is the maximum row." In the latter method, CV was used for the first time, which made it possible to accelerate the coating finding procedure up to one and a half times. The complexity estimates for the considered coating methods are calculated; we have: S1 = O (n ^ 3); S2 = O (2 ^ n); S3 = O (n ^ 2), where n is the determining parameter of the coverage problem (number of columns), and the applicability limits of these methods are determined. It is shown that the use of CV in methods 1 and 2 is impractical.