Метод достижения цели на графовой модели при двух критериях качества

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

1. Авдошин, С. М. Дискретная математика. Алгоритмы: теория и практика / С. М. Авдошин, А. А. Набебин. М.: ДМК Пресс, 2019. 282 с.

2. Алексеев, В. Е. Структуры данных и модели вычислений / В. Е. Алексеев, В. А. Таланов; 2-е изд., испр. М.: ИНТУИТ, 2016. 256 с.

3. Костюкова, Н. И. Графы и их применение. Комбинаторные алгоритмы для программистов / Н. И. Костюкова; 2-е изд., испр. М.: ИНТУИТ, 2016. 305 с.

4. Чебаков, С. В. Алгоритм нахождения множества Парето на конечном наборе начальных данных / С. В. Чебаков, Л. В. Серебряная // Информатизация образования. 2017. Т. 79, № 1. С. 84–94.

5. Чебаков, С. В. Оптимизация решения задачи с ограничением на ресурсы / С. В. Чебаков, Л. В. Серебряная // Доклады БГУИР. 2016. Т. 102, № 8. С. 46–52. 6.

6. 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.