About using special data structures in coverage algorithms

Abstract

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.

Problems in programming 2020; 2-3: 138-148