Решение задач перебора путей в сложных графах

Обложка

Цитировать

Полный текст

Аннотация

Моделирование различных систем связано с перебором значений параметров элементов структуры и учетом всех характеристик функционирования и взаимодействия компонентов для нахождения определенного набора решений, определяющих конфигурацию системы. Такие задачи относятся к задачам переборного типа и подразумевают, что некоторое количество очередных решений из этого набора получается из предыдущего решения в определенном порядке. Известно, что достаточно большое количество задач переборного типа решается только методами полного перебора и других методов для их точного решения пока не существует. В статье представлен новый метод перебора путей в графе – метод трансформации узлов-графов. По предварительной оценке, предложенный метод, в отличие от существующих, позволяет значительно быстрее осуществлять поиск всех простых путей в ориентированном графе произвольной структуры. В известных методах перебора в графе (Breadth First Search и Depth First Search) объектом перебора является путь. Всё количество таких путей в графе определяет размер пространства перебора. Основная идея метода трансформации узлов-графов заключается в значительном уменьшении размера пространства перебора за счет укрупнения объектов перебора. Укрупнение объектов перебора осуществляется кластеризацией путей в комбинаторные объекты, объединяющие по определенному регламенту некоторое множество путей одинаковой длины. Такие комбинаторные объекты названы узлами-графами. Узел-граф относится к центрально-периферическим комбинаторным объектам и для перебора всех путей в графе разработаны специфические операции преобразования узлов-графов, которые позволяют найти следующие пути на основе предыдущих. Метод может использоваться как базовый инструментарий для уменьшения размерности пространства поиска решений NP-полных задач, сохраняя универсальность и точность перебора.

Об авторах

В. Н Куделя

АО «Институт Сетевых Технологий»

Email: Kudelia.Viktor@int.spb.ru
17-я линия В.О. 54-1

Список литературы

  1. Monch C., Rizk A. Directed Acyclic Graph-Type Distributed Ledgers via Young-Age Preferential Attachment // Stochastic Systems. 2023. vol. 13. no. 3. pp. 377–397.
  2. Chopra S., Park H., Shim S. Extended Graph Formulation for the Inequity Aversion Pricing Problem on Social Networks // INFORMS Journal on Computing. 2022. vol. 34. no. 3. pp. 1327–1344.
  3. Vidal T., Martinelli R., Pham T.A., Ha M.H. Arc Routing with Time-Dependent Travel Times and Paths // Transportation 2021 Science. vol. 55. no. 3. pp. 706–724.
  4. Гасников А.В. Об эффективной вычислимости конкурентных равновесий в транспортно-экономических моделях // Математическое моделирование: 2015. Т. 27. № 12. С. 121–136.
  5. Волков А.С., Баскаков А.Е. Разработка алгоритма многопутевой маршрутизации в программно-конфигурируемых сетях связи // T-Comm: Телекоммуникации и транспорт. 2021. Т. 15. № 9. С. 17–23.
  6. Ray A., Ventresca M., Kannan K. A Graph-Based Ant Algorithm for the Winner Determination Problem in Combinatorial Auctions // Information Systems Research. 2021. vol. 32. no. 4. pp. 1099–1114.
  7. Glasserman P., de Larrea E.L. Maximum Entropy Distributions with Applications to Graph Simulation. Operations Research. 2023. vol. 71. no. 5. pp. 1908–1924.
  8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М. Мир. 1982. 419 с.
  9. Батенков К.А. Точные и граничные оценки вероятностей связности сетей связи на основе метода полного перебора типовых состояний // Труды СПИИРАН. 2019. Т. 18. № 5. C. 1093–1118.
  10. Тимошенко А.В., Кочкаров Р.А., Кочкаров А.А. Выделение условий разрешимости NP-полных задач для класса предфрактальных графов // Моделирование и анализ информационных систем. 2021. Т. 28. № 2. С. 126–135.
  11. Левин Л.А. Универсальные задачи перебора // Проблемы передачи информации. 1973. Т. 9. № 3. С. 115–116.
  12. Gavanelli M., Mancini T. RCRA 2007: Experimental evaluation of algorithms for solving problems with combinatorial explosion. Journal of Algorithms. 2008. vol. 63. no. 1–3. pp. 1–2. doi: 10.1016/j.jalgor.2008.02.002.
  13. Кристофидес Н. Теория графов Алгоритмический подход // М.: Мир, 1978. 432 с.
  14. Kudelia V.N. Full enumeration methods on graphs // T-Comm. 2023. vol. 17. № 7. pр. 57–64. doi: 10.36724/2072-8735-2023-17-7-57-64.
  15. Куделя В.Н. Методы перечисления путей в графе // Наукоемкие технологии в космических исследованиях Земли. 2023. Т. 15. № 5. С. 28–38.
  16. Ott F., Markovic D., Strobel A., Kiebel S.J. Dynamic integration of forward planning and heuristic preferences during multiple goal pursuit // PLOS Computational Biology. 2020. vol. 16. no. 2. doi: 10.1371/journal.pcbi.1007685.
  17. Banville F., Gravel D., Poisot T. What constrains food webs? A maximum entropy framework for predicting their structure with minimal biases // PLOS Computational Biology. 2023. vol. 19. no. 9. doi: 10.1371/journal.pcbi.1011458.
  18. Harary F., Palmer E.M. Graphical enumeration. Academic Press New York and London, 1972. 271 p.
  19. Kelil A, Dubreuil B, Levy E.D, Michnick S.W. Exhaustive search of linear information encoding protein-peptide recognition. PLOS Computational Biology. 2017. vol. 13. no. 4. doi: 10.1371/journal.pcbi.1005499.
  20. Рыбалов А.Н. О генерической сложности проблемы распознавания гамильтоновых путей // Прикладная дискретная математика. 2021. № 53. С. 120–126.
  21. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов // М. Радио и связь. 1986. 408 с.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).