Участник:Финютин Максим
Финютин Максим
МОУ лицей №6
11 Класс
Название работы: Сравнительный анализ эффективности алгоритмов прохода лабиринта и разработка программ-роботов, реализующих этих алгоритмы.
Название номинации: алгоритмические языки
Краткая аннотация представленной работы
С глубокой древности лабиринты несли ощущение тайны и загадки. Один из первых лабиринтов, известных человечеству, описывает Геродот - это был египетский Лабиринт, в котором было 5000 комнат. Со временем лабиринты утратили свое религиозно-мистическое значение и стали объектами развлечений, превратившись в сады и парки в виде зеленых изгородей сложной конфигурации. Разгадывание лабиринтов всегда являлось увлекательнейшим занятием, но еще более увлекательным является создание машин, способных пройти Лабиринт.
Постановка задачи: написать программу-робота, которая максимально эффективно будет находить клад в сгенерированном лабиринте и выход из него.
Программы написаны на языке C++, с использованием библиотек OpenGL.
Выводы 1. Проанализирована возможность создания наиболее эффективного алгоритма обхода любых лабиринтов. 2. Реализованы собственные алгоритмы обхода лабиринтов для двух соревнующихся программ-роботов, при этом были модернизированы известные алгоритмы: алгоритм Люка-Тремо и правило «одной руки». 3. Реализована визуализация работы соревнующихся программ для трехмерного случая с помощью библиотек OpenGL. 4. Опытным путем доказана эффективность алгоритма Люка-Тремо.
