Найти

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

• БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ РЕШЕНИЯ ИНВАРИАНТНЫХ ГРАФОВЫХ ЗАДАЧ

  О.Б. Лебедев , А.А. Жиглатый

  2022-11-01

  Аннотация ▼

  Предлагается биоинспирированный метод решения набора инвариантных комбина-
  торно-логических задач на графах: формирования паросочетания графа, выделения внут-
  ренне-устойчивого множества вершин, выделения клики графа. Описывается модифициро-
  ванная парадигма муравьиной колонии использующая, в отличие от канонического метода,
  механизмы формирования решений на модели пространства поиска в виде звездного графа.
  Задача формирования в графе внутренне-устойчивого множества вершин может быть
  сформулирована, как задача разбиения. На начальном этапе на всех ребрах звездного графа
  H откладывается одинаковое (небольшое) количество феромона ξ/m, где m=|E|. Процесс
  поиска решений итерационный. Каждая итерация l включает три этапа. Агенты облада-
  ют памятью. На каждом шаге t в памяти агента ak имеется количество феромона фj(t),
  отложенного на каждом ребре графа H. На первом этапе каждый агент ak популяции
  конструктивным алгоритмом находит решение Ur
  0k, рассчитывает оценку решения
  ξk(Ur
  0k) и значение степени пригодности полученного агентом решения φk (количество фе-
  ромона, соответствующее оценке). На втором этапе, после полного формирования всеми
  агентами решений на текущей итерации, феромон ωj, накопленный в j-ой ячейке в буфер-
  ном массиве КЭПб, добавляется в каждую j-ю ячейку основного массива Q2={qj|j=1,2,…,m}
  коллективной эволюционной памяти КЭПo. На третьем этапе происходит общее испаре-
  ние феромона на множестве ребер E звездного графа H. Временная сложность алгоритма,
  полученная экспериментальным путем, совпадает с теоретическими исследованиями и для
  рассмотренных тестовых задач составляет О(n2).

• АЛГОРИТМ ЭФФЕКТИВНЫХ УПРАВЛЕНИЙ В НЕСТОХАСТИЧЕСКИХ ПРИЧИННЫХ МОДЕЛЯХ В ОТСУТСТВИИ НАБЛЮДАЕМЫХ ПЕРЕМЕННЫХ ДЛЯ СИСТЕМ ПРИНЯТИЯ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ

  А. Н. Целых , В. С. Васильев , Л.А. Целых

  2021-11-14

  Аннотация ▼

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

• АЛГОРИТМ РЕКОНСТРУКЦИИ МАТРИЦЫ СМЕЖНОСТИ ПРИЧИННЫХ ГРАФОВЫХ МОДЕЛЕЙ В ОТСУТСТВИИ НАБЛЮДАЕМЫХ ПЕРЕМЕННЫХ

  А. Н. Целых, В.С. Васильев , Л. А. Целых

  2021-11-14

  Аннотация ▼

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

• ИССЛЕДОВАНИЕ ПРИМЕНИМОСТИ МУЛЬТИМОДЕЛЬНЫХ ХРАНИЛИЩ ДАННЫХ В ИГРОВОЙ ИНДУСТРИИ

  А.А. Коблов , О.М. Ромакина , А.С. Клемешева , А. З. Арсеньева

  105-121

  2025-12-30

  Аннотация ▼

  Проводится исследование целесообразности и эффективности применения мультимодельных баз данных для хранения и обработки данных в игровой индустрии. Современные игровые проекты характеризуются высокой сложностью и разнородностью данных: от строго структурированной информации об игроках, предметах и квестах до слабоструктурированных и сильносвязанных данных, таких как системы рецептов, диалоговые деревья, отношения между кланами и внутриигровые энциклопедии. Существующие подходы, основанные на реляционных или одномодельных NoSQL-хранилищах, часто не обеспечивают необходимой гибкости, производительности и удобства разработки для таких комплексных сценариев. Целью исследования является проектирование и сравнительный анализ производительности мультимодельного решения в контексте типовых игровых механик. Авторами разработана структура мультимодельного хранилища на базе СУБД ArangoDB, которая интегрирует документную, графовую и ключ-значение модели данных. Архитектура решения охватывает ключевые компоненты RPG-игр: управление игроками и инвентарём, систему квестов, диалогов, рецептов крафта, таблиц добычи, клановых взаимоотношений, а также полнотекстовый поиск по внутриигровой энциклопедии с использованием ArangoSearch. Экспериментальная часть включает подробное сравнение производительности разработанного мультимодельного хранилища с реляционной СУБД PostgreSQL и документной MongoDB на реалистичных наборах данных и запросах. Результаты демонстрируют значительное преимущество мультимодельного подхода при выполнении операций, требующих обхода сложных связей: например, поиск враждебных игроков через граф клановых отношений в ArangoDB выполняется в среднем в 11 раз быстрее, чем аналогичный JOIN-запрос в PostgreSQL.
  В то же время, для сценариев с частыми модификациями линейно организованных данных (например, обновление статуса квестов) мультимодельное хранилище показывает несколько более низкую производительность по сравнению с реляционной моделью, что однако является допустимым в контексте общей архитектуры игрового проекта. Исследование подтверждает, что мультимодельные СУБД, в частности ArangoDB, представляют собой перспективное решение для игровой индустрии, позволяя в рамках единой платформы эффективно комбинировать различные модели данных, упрощать разработку и достигать высокой производительности на сложносвязанных данных, что является критически важным для современных многопользовательских игр

• ИССЛЕДОВАНИЕ АЛГОРИТМОВ МНОГОПУТЕВОЙ МАРШРУТИЗАЦИИ СООБЩЕНИЙ С ИСПОЛЬЗОВАНИЕМ ТРЕХМЕРНЫХ ГРАФОВЫХ МОДЕЛЕЙ СЕТЕЙ АНПА

  Н.В. Колесов , А. М. Грузликов , Ю.М. Скородумов , В.С. Тюльников

  2026-04-29

  Аннотация ▼

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