Details

Title: Поиск пути на графе с помощью алгоритма A* на основе бинарных решающих диаграмм: выпускная квалификационная работа бакалавра: направление 02.03.02 «Фундаментальная информатика и информационные технологии» ; образовательная программа 02.03.02_02 «Информатика и компьютерные науки»
Creators: Ткачук Андрей Сергеевич
Scientific adviser: Шошмина Ирина Владимировна
Other creators: Локшина Екатерина Геннадиевна
Organization: Санкт-Петербургский политехнический университет Петра Великого. Институт компьютерных наук и технологий
Imprint: Санкт-Петербург, 2021
Collection: Выпускные квалификационные работы; Общая коллекция
Subjects: бинарные решающие диаграммы; программирование в ограничениях; логический агент; мир Вампуса; поиск пути; binary decision diagrams; restricted programming; logical agent; Vampus world; path finder
Document type: Bachelor graduation qualification work
File type: PDF
Language: Russian
Level of education: Bachelor
Speciality code (FGOS): 02.03.02
Speciality group (FGOS): 020000 - Компьютерные и информационные науки
Links: Отзыв руководителя; Отчет о проверке на объем и корректность внешних заимствований
DOI: 10.18720/SPBPU/3/2021/vr/vr21-3126
Rights: Доступ по паролю из сети Интернет (чтение, печать, копирование)
Record key: ru\spstu\vkr\14156

Allowed Actions:

Action 'Read' will be available if you login or access site from another network Action 'Download' will be available if you login or access site from another network

Group: Anonymous

Network: Internet

Annotation

Работа посвящена созданию модуля составления марш-рута между двумя узлами в графе, символизирующем карту игры «Мир Вампуса». При обучении математической логике с помощью средств дистанционной платформы существует необходимость наглядной демонстрации применения теоретических концепций математической логики на практике. Для этих целей среди прочего существует логический агент для обучающего тренажера «Мир Вампуса», но скорость его модуля поиска пути низкая для больших размеров полей. В рамках данной научно-исследовательской работы были проанализированы различные способы поиска пути, а именно неинформированные алгоритмы поиска, такие как поиск в глу-бину и поиск в ширину, алгоритм Дейкстры, и информирован-ные алгоритмы: поиск по первому наилучшему совпадению и алгоритм А*. Было выяснено, что наиболее эффективные ре-зультаты следует ожидать от последнего. Программная часть работы, заключающаяся в реализации выбранного алгоритма написана на языке 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.

Document access rights

Network User group Action
ILC SPbPU Local Network All Read Print Download
External organizations N2 All Read
External organizations N1 All
Internet Authorized users SPbPU Read Print Download
Internet Authorized users (not from SPbPU, N2) Read
Internet Authorized users (not from SPbPU, N1)
-> Internet Anonymous

Table of Contents

  • Список обозначений
  • Введение
  • Глава 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. Проверка быстродействий модулей пути
  • Заключение
  • Литература

Usage statistics

stat Access count: 3
Last 30 days: 1
Detailed usage statistics