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

Ю. В. Бугаев; С. В. Чикунов

doi:10.20914/2310-1202-2018-2-73-76

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

Ю. В. Бугаев, С. В. Чикунов

https://doi.org/10.20914/2310-1202-2018-2-73-76

Полный текст:

Аннотация

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

Ключ. слова

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

УДК: 519.852

Об авторах

Ю. В. Бугаев

Воронежский государственный университет инженерных технологий
Россия
д.ф-м.н., профессор, кафедра высшей математики и информационных технологий, пр-т Революции, 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 Y.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

Обратные ссылки

Обратные ссылки не определены.

Контент доступен под лицензией Creative Commons Attribution 4.0 License.

ISSN 2226-910X (Print)
ISSN 2310-1202 (Online)

Логин
Пароль