Участник:Финютин Максим

Версия 00:41, 28 февраля 2009

Финютин Максим

Финютин Максим

МОУ лицей №6

11 Класс

Название работы: Сравнительный анализ эффективности алгоритмов прохода лабиринта и разработка программ-роботов, реализующих этих алгоритмы.

Название номинации: алгоритмические языки

Краткая аннотация представленной работы

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

Постановка задачи: написать программу-робота, которая максимально эффективно будет находить клад в сгенерированном лабиринте и выход из него.

Программы написаны на языке C++, с использованием библиотек OpenGL.

Выводы 1. Проанализирована возможность создания наиболее эффективного алгоритма обхода любых лабиринтов.

2. Реализованы собственные алгоритмы обхода лабиринтов для двух соревнующихся программ-роботов, при этом были модернизированы известные алгоритмы: алгоритм Люка-Тремо и правило «одной руки».

3. Реализована визуализация работы соревнующихся программ для трехмерного случая с помощью библиотек OpenGL.

4. Опытным путем доказана эффективность алгоритма Люка-Тремо.