Работа посвящена созданию модуля составления марш-рута между двумя узлами в графе, символизирующем карту игры «Мир Вампуса». При обучении математической логике с помощью средств дистанционной платформы существует необходимость наглядной демонстрации применения теоретических концепций математической логики на практике. Для этих целей среди прочего существует логический агент для обучающего тренажера «Мир Вампуса», но скорость его модуля поиска пути низкая для больших размеров полей. В рамках данной научно-исследовательской работы были проанализированы различные способы поиска пути, а именно неинформированные алгоритмы поиска, такие как поиск в глу-бину и поиск в ширину, алгоритм Дейкстры, и информирован-ные алгоритмы: поиск по первому наилучшему совпадению и алгоритм А*. Было выяснено, что наиболее эффективные ре-зультаты следует ожидать от последнего. Программная часть работы, заключающаяся в реализации выбранного алгоритма написана на языке C++ с применением библиотеки BuDDy, как и оригинальный логический агент, в среде разработки Visual Studio с применением системы контроля версий git. В результате модуль поиска пути для логического агента был протестирован на сгенерированной выборке уровней и по-казал сокращение общего времени работы.

The work is devoted to the creation of a module for drawing up a route between two nodes in a graph symbolizing the map of the game "Wampus World". When teaching mathematical logic using the means of a remote platform, there is a need for a visual demonstration of the application of theoretical concepts of mathematical logic in prac-tice. For these purposes, among other things, there is a logical agent for the Wampus World training simulator, but the speed of its pathfinding module is low for large fields. As part of this research work, various pathfinding methods have been analyzed, namely uninformed search algorithms such as depth-first search and breadth-first search, Dijkstra's algorithm, and informed algorithms: best-first search and BUT*. It was found that the most effective results should be expected from the latter. The software part of the work, which consists in imple-menting the selected algorithm, is written in C ++ using the BuD-Dy library, like the original logical agent, in the Visual Studio de-velopment environment using the git version control system. As a result, the implemented module for finding the path for this logical agent was tested on the generated test sample of lev-els and showed a reduction in the total operating time of the logical agent.

• Список обозначений
• Введение
• Глава 1. Проблема поиска пути на графе
  • § 1.1. Описание задачи поиска на графе и соотношение с «миром Вампуса»
    • 1.1.1. Описание «Мира Вампуса»
    • 1.1.2. Программирование в ограничениях
    • 1.1.3 Бинарные решающие диаграммы
  • § 1.2 Обзор алгоритмов, находящих путь на графе
    • 1.2.1 Поиск в глубину
    • 1.2.2 Поиск в ширину
    • 1.2.3 Поиск по критерию стоимости
    • 1.2.4. Жадный поиск по первому наилучшему совпадению
    • 1.2.5. Алгоритм A*
  • § 1.3 Постановка задачи поиска пути в «мире Вампуса»
• Глава 2. Задача поиска пути c помощью бинарных решающих диаграмм
  • § 2.1. Программные пакеты для представления BDD
  • § 2.2. Описание алгоритма A* с использованием BDD
    • 2.2.1 Доказательство оптимальности и полноты A*
• Глава 3. Реализация улучшенного алгоритма поиска пути
  • § 3.1. Текущая реализация мира Вампуса
    • 3.1.1 Описание общей подхода к решению
    • 3.1.2 Описание базы знаний и используемых логических переменных
  • § 3.2. Описание особенностей нашей реализации
• Глава 4. Проверка реализации
  • § 4.1. Описание генератора уровней для мира Вампуса
  • § 4.2. Проверка быстродействий модулей пути
• Заключение
• Литература