bsuirДоклады БГУИРDoklady BGUIR1729-76482708-0382БГУИР10.35596/1729-7648-2023-21-4-84-92bsuir-3686Research ArticleЭЛЕКТРОНИКА, РАДИОФИЗИКА, РАДИОТЕХНИКА, ИНФОРМАТИКАELECTRONICS, RADIOPHYSICS, RADIOENGINEERING, INFORMATICSМетод достижения цели на графовой модели при двух критериях качестваMethod of Achieving the Goal on a Graph Model with Two Quality CriteriaЧебаковС. В.ChebakovS. V.

Кандидат физико-математических наук, старший научный сотрудник.

Минск

Sergey V. Chebakov - Cand. of Sci., Senior Researcher.

Minsk

СеребрянаяЛ. В.SerebryanayaL. V.

Серебряная Лия Валентиновна - кандидат технических наук, заведующая кафедрой информационных технологий и математики БИП – Университет права и социально-информационных технологий, доцент кафедры программного обеспечения информационных технологий БГУИР.

220013, Минск, ул. П. Бровки, 6. Тел.: +375 29 773-95-09

Serebryanaya Liya Valentinovna - Cand. of Sci., Head of the Department of Information Technologies and Mathematics BIP – University of Law and Social-Information Technologies, Associate Professor at the Information Technology Software Department BSUIR.

220013, Minsk, P. Brovki St., 6. Tel.: +375 29 773-95-09

l_silver@mail.ruОбъединенный институт проблем информатики НАН БеларусиJoint Institute for Informatics Problems of the National Academy of Sciences of BelarusБИП – Университет права и социально-информационных технологий; Белорусский государственный университет информатики и радиоэлектроникиBIP – University of Law and Social-Information Technologies; Belarusian State University of Informatics and Radioelectronics2023290820232148492Copyright © Чебаков С.В., Серебряная Л.В., 20232023Чебаков С.В., Серебряная Л.В.Chebakov S.V., Serebryanaya L.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.bsuir.by/jour/article/view/3686

Рассмотрены особенности построения и применения графовых моделей для решения прикладных задач. Предложена графовая модель с двумя критериями качества, на которой выполняется поиск оптимальных путей между заданными вершинами графа. Каждое ребро графа имеет весовой коэффициент, определяющий количество временных единиц, требуемых для прохождения данного ребра. Каждая вершина может находиться в одном из двух состояний: «открыто» или «заблокировано». Первоначально все вершины открыты, однако их состояния могут изменяться в процессе решения задачи. Поиск решения ограничен заданным временем. Если в ходе движения по выбранному маршруту вершины графа становятся заблокированными, требуется искать альтернативные пути достижения цели. Определено понятие допустимого пути на графе. Построено паретовское множество, из которого по заданному правилу выбраны допустимые пути. Для этого разработана процедура выбора пути из множества Парето. По завершении выбора путь считается оптимальным для движения по нему из начальной вершины в целевую. Представлены ситуации, которые могут происходить в процессе выбора пути и прохождения по нему. Их появление – следствие изменения состояний вершин графа. На основе процедуры выбора разработан алгоритм поиска оптимальных путей между заданными вершинами на графовой модели.

The features of the construction and application of graph models for solving applied problems are considered. A graph model with two quality criteria is proposed, on which the search for optimal paths between given graph vertices is performed. Each edge of the graph has a weighting factor that determines the number of time unitsrequired to pass this edge. Each vertex can be in one of two states: “open” or “locked”. Initially, all vertices are open, but their states may change in the process of problem solving. The search for a solution is limited by a given time. If during the movement along the chosen route the graph vertices become blocked, it is necessary to look for alternative ways to achieve the goal. A method for constructing a Pareto set from which admissible paths are selected is proposed. The notion of an admissible path on a graph is defined. A procedure for choosing a path from the Pareto set has been developed. Upon completion of the choice, the path is considered optimal for follo wing it from the initial vertex to the target. Situations that can occur in the process of choosing a path and passing along it are presented. Based on the selection procedure, an algorithm for finding optimal paths bet ween given vertices on a graph model has been developed.

графовая модельоптимальный путьмножество Паретосостояние вершиныалгоритм поискаgraph modeloptimal pathPareto setvertex statesearch algorithmReferencesАвдошин, С. М. Дискретная математика. Алгоритмы: теория и практика / С. М. Авдошин, А. А. Набебин. М.: ДМК Пресс, 2019. 282 с.Avdoshin S. M., Nabebin A. A. (2019) Discrete Mathematics. Algorithms: Theory and Practice. Moscow, DMK Press Publ. 282 (in Russian).Алексеев, В. Е. Структуры данных и модели вычислений / В. Е. Алексеев, В. А. Таланов; 2-е изд., испр. М.: ИНТУИТ, 2016. 256 с.Alekseev V. E., Talanov V. A. (2016) Data Structures and Computational Models. 2nd ed., rev. Moscow, INTUIT Publ. 256 (in Russian).Костюкова, Н. И. Графы и их применение. Комбинаторные алгоритмы для программистов / Н. И. Костюкова; 2-е изд., испр. М.: ИНТУИТ, 2016. 305 с.Kostyukova N. I. (2016) Graphs and their Application. Combinatorial Algorithms for Programmers. 2nd ed., rev. Moscow, INTUIT Publ. 305 (in Russian).Чебаков, С. В. Алгоритм нахождения множества Парето на конечном наборе начальных данных / С. В. Чебаков, Л. В. Серебряная // Информатизация образования. 2017. Т. 79, № 1. С. 84–94.Chebakov S. V., Serebryanaya L. V. (2017) Algorithm for Finding the Pareto Set on a Finite Set of Initial Data. Informatization of Education. 79 (1), 84–94 (in Russian).Чебаков, С. В. Оптимизация решения задачи с ограничением на ресурсы / С. В. Чебаков, Л. В. Серебряная // Доклады БГУИР. 2016. Т. 102, № 8. С. 46–52. 6.Chebakov S. V., Serebryanaya L. V. (2016) Optimization of the Solution of a Problem with a Constraint on Resources. Doklady BSUIR. 102 (8), 46–52 (in Russian).Kung, H. F. On Finding the Maxima of a Set of Vectors / H. F. Kung, F. P. Preparata // Journal of the Association for Computing Machinery. 1975. No 22. Р. 469–476.Kung H. F., Preparata F. P. (1975) On Finding the Maxima of a Set of Vectors. Journal of the Association for Computing Machinery. (22), 469–476.

The authors declare that there are no conflicts of interest present.