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

Обложка

Цитировать

Полный текст

Аннотация

Моделирование различных систем связано с перебором значений параметров элементов структуры и учетом всех характеристик функционирования и взаимодействия компонентов для нахождения определенного набора решений, определяющих конфигурацию системы. Такие задачи относятся к задачам переборного типа и подразумевают, что некоторое количество очередных решений из этого набора получается из предыдущего решения в определенном порядке. Известно, что достаточно большое количество задач переборного типа решается только методами полного перебора и других методов для их точного решения пока не существует. В статье представлен новый метод перебора путей в графе – метод трансформации узлов-графов. По предварительной оценке, предложенный метод, в отличие от существующих, позволяет значительно быстрее осуществлять поиск всех простых путей в ориентированном графе произвольной структуры. В известных методах перебора в графе (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

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

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