Найти

Результаты поиска

• ПРОГРАММНАЯ ПОДСИСТЕМА ДЛЯ РЕШЕНИЯ NP-СЛОЖНЫХ КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ НА ГРАФАХ

  В.В. Курейчик , Вл. Вл. Курейчик

  2021-07-18

  Аннотация ▼

  Работа посвящена созданию программной подсистемы для решения NP- трудных и
  NP-сложных комбинаторно-логических задач на графах. В статье приведено описание
  комбинаторно-логических задач на графах. Для эффективного их решения предлагаются
  новые многоуровневые архитектуры поиска, такие как простая комбинированная, парал-
  лельная комбинированная, двухуровневая, интегрированная и гибридная. Данные архитек-
  туры основаны на методах, инспирированных природными системами. Ключевым отличием данных архитектур является разделение поиска на два или три уровня и применение на
  них различных алгоритмов эволюционного моделирования и биоинспирированного поиска.
  Это позволяет получать наборы квазиоптимальных решений выполнять параллельную
  обработку и частично устранять проблему преждевременной сходимости. В статье при-
  ведено подробное описание разработанной программной подсистемы и ее модулей. В каче-
  стве модулей в подсистеме имеется пять разработанных архитектур и набор разрабо-
  танных алгоритмов эволюционного моделирования и биоинспирированного поиска, таких
  как эволюционный, генетический, пчелиный, муравьиный, светлячковый и обезьяний. Благо-
  даря модульной структуре в подсистеме имеется возможность конструировать более 50
  различных вариантов комбинаций поиска. Это позволяет использовать все достоинства
  методов биоинспирированной оптимизации для эффективного решения NP-сложных ком-
  бинаторно-логических задач на графах. Для подтверждения эффективности разработан-
  ной программной подсистемы был проведен вычислительный эксперимент на тестовых
  примерах. Проведенные серии тестов и экспериментов показали преимущество использо-
  вания программного продукта для решения комбинаторно-логических задач на графах
  большой размерности, по сравнению с известными алгоритмами, что говорит о перспек-
  тивности применения такого подхода. Временная сложность разработанных алгоритмов
  в лучшем случае O(nlogn), в худшем случае – О(n3).