Волновой алгоритм - это алгоритм, который позволяет вам найти минимальный путь на графе. В основе этого метода лежит алгоритм поиска по ширине. В основном, волновой алгоритм используется для нахождения кратчайшего пути на графе, в общем случае он находит только его длину.
Целью волнового алгоритма (как и большинства других алгоритмов) является задача прокладки или нахождения пути на карте между начальной и конечной точкой (ячейкой). С описанием волнового алгоритма можно ознакомиться более подробно по этой ссылке: http://orionxl.ru/volnovoj-algoritm.html
Для взаимодействия программы и пользователя необходима реализация следующих функций:
- чтение данных из xml-файла
- генерация лабиринта (с учетом пользовательского ввода)
- поиск минимального пути (с использованием волнового алгоритма)
- отображение выхода из лабиринта
Основная информация: случайный лабиринт с пустотами и препятствиями.
Полученная информация: отображение минимального пути в случайном лабиринте в консольном режиме.
В этом проекте минимальный маршрут выбирается с применением алгоритма Ли (волновой алгоритм). В начале работы программа выводит таблицу (обычную сетку) с размером, считанным из файла, где 99 - обозначение препятствия, а -1 - свободная ячейка.
Далее алгоритм предлагает ввести координаты начальной и конечной точек (от 1 до 13 в x и y для данного примера). После ввода программа выводит на консоль таблицу, в которой нули показывают путь от начала до конечной точки. И в конце - координаты точек маршрута, соединяющих начало и конец.
Найденный кратчайший путь помечается нулями.
Основные методы в программе:
- Метод WaveAlg – построение волнового алгоритма
- метод Block – заполнение карты препятствиями
- Метод findPath – реализация поиска кратчайшего пути
- Метод WaveOut – вывод координат пути в лабиринте
- Метод TraceOut – вывод лабиринта в виде таблицы
Поиск по кратчайшему пути реализован с использованием следующих структур данных, а именно: списка, файла и массива. Список - это набор элементов одного типа, где количество элементов больше или равно 0.
В программе эта структура используется для объекта wave. В основном списки реализованы на основе другой структуры - массивов, в нашем случае – двумерного массива (матрицы), который генерирует лабиринт, а также выводит таблицу, отображающую кратчайший путь от начальной до конечной точки. Для того чтобы сгенерировать лабиринт, вам необходимо получить данные из xml-файла.
Во время разработки программы "поиск кратчайшего пути в лабиринте" была проведена проверка на обнаружение ошибок, программа функционирует корректно, при этом никакого дополнительного тестирования не проводилось. Проверка работы программы заключалась в вводе различных исходных данных и получении соответствующих результатов.
| Исходные данные | Полученные данные |
|---|---|
| 1, 1, 13, 13 | 1 - 1, 2 -1, 3 - 1, 4 - 1, 5 -1, 6 - 1, 7 - 1, 8 - 1, 8 - 2, 8 - 3, 8 - 4, 8 - 5, 9 - 5, 10 - 5, 10 - 6, 11 - 6, 12 - 6, 13 - 6, 13 - 7, 13 - 8, 13 - 9, 13 - 10, 13 - 11, 13 -12, 13 – 13 |
| ! и другие символы | отображается сообщение об ошибке в отношении введенных значений |
Полученные результаты свидетельствуют об эффективности и качестве разработанной программы. Но для более детального тестирования необходимо провести несколько тестов.