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

Аннотация

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