СОЗДАНИЕ ЛАБИРИНТА С НЕСКОЛЬКИМИ ПРОХОДАМИ, ПОИСК ВСЕХ ПУТЕЙ В НЕМ И ИХ РЕДАКТИРОВАНИЕ


УДК 519.688
DOI: 10.26102/2310-6018/2019.25.2.030

Э.С.Симонян , О.А.Медведева , С.Н.Медведев


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

Ключевые слова: генерация лабиринта, муравьиный алгоритм, алгоритм Уилсона, вычислительный эксперимент.

Полный текст статьи:
SimonyanSoavtori_2_19_1.pdf