ISSN 2071-6168
Язык: ru

ИЗВЕСТИЯ ТУЛЬСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА. ТЕХНИЧЕСКИЕ НАУКИ

ОЦЕНКИ МОЩНОСТИ МНОЖЕСТВА РЕШЕНИЙ ЗАДАЧ ПОИСКА ПАРЕТО-ОПТИМАЛЬНЫХ ПОДГРАФОВ СВЯЗНОГО ГРАФА (2024)

Теория графов составляет существенную часть математических методов, применяемых в экономике для решения самых разнообразных задач. Из этого многообразия следует выделить задачи построения оптимальных подграфов определенного вида в заданном связном графе. В последние десятилетия все более актуальными становятся многокритериальные варианты указанных задач. Однако широкому практическому распространению алгоритмов их решения препятствуют имеющиеся сведения об экспоненциальном росте мощности множества Парето-оптимальных решений с ростом размерности задачи, в результате чего наблюдается преждевременное исчерпание вычислительных ресурсов. Чтобы научиться бороться с этой проблемой, надо получить «хорошую», желательно достижимую оценку мощности множества Парето. Это должно способствовать созданию метода диагностирования неконтролируемого роста числа эффективных решений многокритериальных задач и в дальнейшем помочь в разработке методов борьбы с этим ростом. С практической точки зрения среди эффективных решений наибольший интерес представляет так называемое полное множество альтернатив (ПМА). Поэтому построению оценки мощности именно ПМА посвящена настоящая работа. В результате проведенных исследований были найдены две универсальных оценки мощности ПМА для произвольных подграфов и доказаны теоремы об их корректности. Отдельно были рассмотрены подграфы двух видов - пути и остовные деревья. Для них приведены примеры достижимости одной из оценок в случае двух критериев. Получены асимптотические оценки вычислительной сложности двух алгоритмов поиска Парето-оптимальных путей в графе. Из полученной оценки следует, что при ограниченности значений весов ребер графа эти алгоритмы относятся к классу псевдополиномиальных, т.е. при определенных условиях их вычислительная сложность ниже экспоненциальной.

Тип: Статья
Автор (ы): Бугаев Юрий Владимирович, Шурупова Ирина Юрьевна, Коробова Людмила Анатольевна
Ключевые фразы: граф, ПОДГРАФ, ЗАДАЧА МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ, ПАРЕТО-ОПТИМАЛЬНОЕ РЕШЕНИЕ, ПОЛНОЕ МНОЖЕСТВО АЛЬТЕРНАТИВ, ЭФФЕКТИВНЫЙ ПУТЬ НА ГРАФЕ, ОСТОВНОЕ ДЕРЕВО, ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ АЛГОРИТМА

Идентификаторы и классификаторы

УДК
519.178. Алгоритмические вопросы теории графов
eLIBRARY ID
61758092
Текстовый фрагмент статьи