Оценка мощности полного множества альтернатив паретовских подграфов в графе

Бесплатный доступ

На практике часто встречаются задачи построения оптимального подграфа определённого вида в заданном графе. В качестве возможных приложений используются задачи поиска оптимальной структуры технологических сетей, проектирования архитектуры вычислительных устройств, моделирования искусственного интеллекта и многие другие. Всё более актуальными становятся многокритериальные варианты указанных задач. Существенным сдерживающим фактором совершенствования методов многокритериальной оптимизации на графах является проблема их экспоненциальной вычислительной сложности, вызванной большой размерностью задачи. Ряд данных свидетельствует, что теоретическая оценка сложности, построенная для методов полного перебора, не соответствует действительности, и сделанные выводы не имеют достаточного обоснования. Среди эффективных решений наибольший интерес представляет так называемое полное множество альтернатив, мощность которого может быть на порядки ниже, чем мощность множества Парето. С учётом перечисленных фактов в данной работе изложен результат исследований, состоящий в построении оценки сверху для мощности полного множества альтернатив задачи нахождения парето-оптимальных подграфов для заданного графа.

Еще

Граф, подграф, множество парето, полное множество альтернатив

Короткий адрес: https://readera.ru/140238612

IDR: 140238612   |   DOI: 10.20914/2310-1202-2018-2-73-76

Список литературы Оценка мощности полного множества альтернатив паретовских подграфов в графе

  • Мелькумов В.Н., Кузнецов И.С., Кобелев В.Н. Задача поиска оптимальной структуры тепловых сетей//Научный вестник Воронежского государственного архитектурно-строительного университета. Строительство и архитектура. 2011. № 2. С. 37-42.
  • Ильясова Н.Ю., Корепанов А.О., Чикулаев П.М. Метод выделения центральных линий кровеносных сосудов на диагностических изображениях//Компьютерная оптика. 2006. № 29. С. 146-150.
  • Попов А.Ю. О реализации алгоритма Форда-Фалкерсона в вычислительной системе с многими потоками команд и одним потоком данных//Наука и образование. 2014. № 9. С. 162-180.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Бугаев Ю.В., Музалевский Ф.А. Полиномиальная оценка мощности множества паретовских путей в графе//Вестник Нижегородского университета. 2013. № 2-1. С. 168-170.
  • Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов: Учеб. пособие. М. БИНОМ: Лаборатория знаний, 2010. 311 с.
Еще
Статья научная