Компактные разбиения на топологических графах большой размерности

Abstract

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

Relevance. Distributed systems containing hundreds and thousands of objects are usually built in the form of hierarchical structures. In these struc-tures, lower-level objects are combined into subsets for connection to the corresponding centers. The existing algorithms are not capable of suc-cessfully solving structuring problems on sets of this dimension. Therefore, new algorithms are needed that are suitable for solving structuring prob-lems on sets containing thousands of objects. Aim. To develop an algorithm for generating a compact partition on high-dimensional sets containing up to a thousand objects located in a given territory. Methods. Applied graph theory, linear programming methods, construction and analysis of the effectiveness of algorithms, the theory of compact partitions, compact sets of objects and their clusters. Results. It is proposed to represent the ter-ritorial location of many objects of a distributed system in the form of a topological graph. The paper introduces the concept of an active search zone for the nearest vertices to increase the efficiency of the algorithm for generating compact sets and identifying clusters. This makes it possible to replace the matrix of distances between graph vertices with a list of vertex incidentors generated based on the active search zone. The authors developed the algorithm for approximate solution to the problem of compact partitioning a set of objects of a topological graph, represented by a list of vertex incidentors, into a given number of subsets. For each object, the algorithm recursively increases the power of compact sets, analyzes the resulting clusters and, under certain conditions, proceeds to the formation of a compact partition. The problem of forming subsets of a compact par-tition based on clusters is formed as a linear programming problem of transport type. The algorithm presentation is accompanied by an example