Оценка мощности полного множества альтернатив паретовских подграфов в графе
Аннотация
На практике часто встречаются задачи построения оптимального подграфа определённого вида в заданном графе. В качестве возможных приложений используются задачи поиска оптимальной структуры технологических сетей, проектирования архитектуры вычислительных устройств, моделирования искусственного интеллекта и многие другие. Всё более актуальными становятся многокритериальные варианты указанных задач. Существенным сдерживающим фактором совершенствования методов многокритериальной оптимизации на графах является проблема их экспоненциальной вычислительной сложности, вызванной большой размерностью задачи. Ряд данных свидетельствует, что теоретическая оценка сложности, построенная для методов полного перебора, не соответствует действительности, и сделанные выводы не имеют достаточного обоснования. Среди эффективных решений наибольший интерес представляет так называемое полное множество альтернатив, мощность которого может быть на порядки ниже, чем мощность множества Парето. С учётом перечисленных фактов в данной работе изложен результат исследований, состоящий в построении оценки сверху для мощности полного множества альтернатив задачи нахождения парето-оптимальных подграфов для заданного графа.
Об авторах
Ю. В. Бугаев
Воронежский государственный университет инженерных технологий
Россия
д.ф-м.н., профессор, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия
Россия
д.ф-м.н., профессор, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия
С. В. Чикунов
Воронежский государственный университет инженерных технологий
к.т.н., доцент, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия
к.т.н., доцент, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия
Список литературы
1. Мелькумов В.Н., Кузнецов И.С., Кобелев В.Н. Задача поиска оптимальной структуры тепловых сетей // Научный вестник Воронежского государственного архитектурно-строительного университета. Строительство и архитектура. 2011. № 2. С. 37–42.
2. Ильясова Н.Ю., Корепанов А.О., Чикулаев П.М. Метод выделения центральных линий кровеносных сосудов на диагностических изображениях // Компьютерная оптика. 2006. № 29. С. 146–150.
3. Попов А.Ю. О реализации алгоритма Форда-Фалкерсона в вычислительной системе с многими потоками команд и одним потоком данных // Наука и образование. 2014. № 9. С. 162–180.
4. Williams J., Massie Ch., George A.D., Richardson J. et al. Characterization of Fixed and Reconfigurable Multi-Core Devices for Application Acceleration // ACM Transactions onReconfigurable Technology and Systems. 2010. V. 3, №. 4. Art. №. 19.
5. Nguyen Q.H., Ong Y.S., Krasnogor N.A. Study on the Design Issues of Memetic Algorithm // IEEE Congress on Evolutionary Computation (CEC 2007). 2007. P. 2390–2397.
6. Ong Y.S., Lim M.H., Zhu N., Wong K.W. Classification of adaptive memetic algorithms: A comparative study // IEEE Transactions on Systems, Man and Cybernetics. Part B: Cybernetics. 2006. V. 36. № 1. P. 141–152.
7. Jie J., Zeng J. Improved Mind Evolutionary Computation for Optimizations // Proceedings of 5 th World Congress on Intelligent Control and Automation. 2004. V. 3. P. 2200–2204.
8. Liang J.J., Qu B.Y., Suganthan P.N. Problem Definitions and Evaluation Criteria for the CEC 2014 Special Session and Competition on Single Objective Real-Parameter Numerical Optimization. Technical Report 201311. Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China; Technical Report. Singapore: NanyangTechnologicalUniversity, 2013. 32 p.
9. Бугаев Ю.В., Музалевский Ф.А. Полиномиальная оценка мощности множества паретовских путей в графе // Вестник Нижегородского университета. 2013. № 2–1. С. 168–170.
10. Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов: Учеб. пособие. М. БИНОМ: Лаборатория знаний, 2010. 311 с.
Рецензия
Для цитирования:
Бугаев Ю.В., Чикунов С.В. Оценка мощности полного множества альтернатив паретовских подграфов в графе. Вестник Воронежского государственного университета инженерных технологий. 2018;80(2):73-76. https://doi.org/10.20914/2310-1202-2018-2-73-76
For citation:
Bugaev Yu.V., Chikunov S.V. Power estimation of the full set of alternatives to Paret's subgraphs in a graph. Proceedings of the Voronezh State University of Engineering Technologies. 2018;80(2):73-76. (In Russ.) https://doi.org/10.20914/2310-1202-2018-2-73-76
Просмотров: 375
Послать статью по эл. почте 
Оставить комментарий 
