ISSN 2071-6168
Язык: ru

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

Читать онлайн

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

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

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

УДК
519.178. Алгоритмические вопросы теории графов
eLIBRARY ID
61758092
Для цитирования:
БУГАЕВ Ю. В., ШУРУПОВА И. Ю., КОРОБОВА Л. А. ОЦЕНКИ МОЩНОСТИ МНОЖЕСТВА РЕШЕНИЙ ЗАДАЧ ПОИСКА ПАРЕТО-ОПТИМАЛЬНЫХ ПОДГРАФОВ СВЯЗНОГО ГРАФА // ИЗВЕСТИЯ ТУЛЬСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА. ТЕХНИЧЕСКИЕ НАУКИ. 2024. № 1
Текстовый фрагмент статьи