Алгоритмы проектирования сетей связи с применением жадных эвристик разных типов

Abstract

Рассмотрены две часто возникающие задачи при моделировании сети связи, связанные с построением графа сети связи, удовлетворяющего определенным условиям. Предложен алгоритм, к которому может быть сведено решение обеих задач, относящийся к классу жадных алгоритмов. Исследован вопрос о единственности решения поставленных задач. Получен положительный результат решения вопроса и выявлены достаточные условия единственности. Проведенные исследования и разработка соответствующего программного обеспечения имеют практическую значимость при проектировании реальных сетей связи. We consider two frequently occurring problems in the modeling of the communication network associated with the construction of a graph of the communication network that satisfies certain conditions. We propose an algorithm to which the solution of both problems can be reduced, which belongs to the class of greedy algorithms. The question of the uniqueness of the solution of the tasks is investigated. A positive result of the solution of the problem is obtained and sufficient conditions of uniqueness are revealed. The conducted researches and development of the corresponding software have practical significance at design of real communication networks.