© EVILEG 2015-2018
Рекомендует хостинг
TIMEWEB

Реализация Волнового алгоритма (Алгоритма Ли) на Java

алгоритм ли, волновая трассировка, волновой алгоритм, Java

Иногда перед нами встает задача найти минимальный путь от точки А до точки В . "Карта передвижения"  может иметь преграды и быть подобием лабиринта. Подобные задачи встречаются при разработке игр, проектировании печатных плат и разработке GPS-навигаторов и т.д.

Алгоритмов поиска минимального пути большое множество. Но, наиболее простым и эффективным является Алгоритм волновой трассировки (Алгоритм Ли) , который основан на методах поиска в ширину.

В работе данного алгоритма не сложно разобраться. Он будет понятен даже новичку в программировании.

Я буду приводить пример своей работы. У меня имеется подобие клеточного автомата (граф, состоящий из узлов и ребер между ними). На нем будем реализовывать Алгоритм Ли .

Реализация алгоритма состоит из 3-х этапов:

  1. Инициализация начальных данных;
  2. Распространение волны;
  3. Восстановление пути.

Первый этап - Инициализация начальных данных

Вам нужно иметь массив объектов (узлов, ячеек). У меня это класс Node .

Каждый объект, кроме иных, имеет поле near типа, например, ArrayList. В данное поле вы записываете всех "соседей" ( соседние узлы данного узла ).

Каждый узел получает отметку "проходимый / непроходимый".

Записываются стартовый и финишный узлы.

Второй этап -  Распространение волны

Вы должны иметь численный массив (по количеству ячеек), куда будут записываться числа (отметки)  для каждой ячейки. По умолчанию все значения ячеек равны нулю.

Стартовый узел получает значение 1.

Проверяете все "соседние" узлы данного узла на "проходимость", и проверяете нет ли на них уже отметки. Так как отметка должна ставиться только один раз.

Если все удовлетворительно ставите отметку на 1 больше , чем у предыдущего узла. Далее проверка его "соседних узлов".

Так до тех пор, пока не дойдете до финишной ячейки .


Пример кода:
public int[] WavePropagation(int fromNode, int toNode, ElementManager elementManager) {  // распространение волны

        int[] markedNode = new int[elementManager.GetNumberOfAllNodes()]; // массив, где будут хранится "отметки" каждого узла
        int markNumber = 1;                        // счетчик
        markedNode[fromNode] = markNumber;         // инициализация стартового узла
        while (markedNode[toNode] == 0) {          // пока не достигли финишного узла
            for (int i = 0; i < markedNode.length; i++) { 
                if (markedNode[i] == markNumber) {                                          // начинаем со стартового узла
                    for (int j = 0; j < elementManager.GetNode(i).near.size(); j++) {       // просматриваем все соседние узлы
                        if(markedNode[elementManager.GetNode(i).near.get(j).number] == 0    // если он еще не получил "отметку"
                           && elementManager.GetNode(i).near.get(j).isEnable){              // если доступен 
                            markedNode[elementManager.GetNode(i).near.get(j).number] = (markNumber + 1);
                        }
                    }
                }
            }
            markNumber++;
        }
        return markedNode;
    }

Третий этап -  Восстановление пути

В массив пути заносите финишный узел .

Просматриваете отметки всех  узлов, "соседних" к финишному узлу. Заносите в массив пути тот узел, отметка которого на 1 меньше , чем у финишного узла.

Повторяете это действие, пока не будет достигнут стартовый узел .

Пример кода:
public ArrayList<Integer> PathRecovery(int fromNode, int toNode, int[] markedNode, ElementManager elementManager) {  // восстановление пути
        ArrayList<Integer> paramsPaveTheRoute = new ArrayList<>();      // массив, где хранится путь
        if (markedNode[elementManager.GetNode(toNode).number] != 0) {   // еще раз проверяем дошел ли алгоритм до финишного узла
            paramsPaveTheRoute.add(toNode);                             // добавляем финишный узел к пути
            ElementManager.Node currentNode = elementManager.GetNode(toNode);
            while (currentNode.number != fromNode) {                     // пока не дошли до стартового узла   
                for (int i = 0; i < currentNode.near.size(); i++) {      // проверяем соседние узлы
                    if (markedNode[elementManager.GetNode(currentNode.near.get(i).number).number]
                            == markedNode[currentNode.number] - 1) {     // если значение пометки узла на 1 меньше, чем у предыдущего узла
                        currentNode = elementManager.GetNode(currentNode.near.get(i).number); //узел становится текущим
                        paramsPaveTheRoute.add(currentNode.number);      // заносится в массив
                    }
                }
            }
        }
        return paramsPaveTheRoute;
    }
Результат работы программы:

Таким образом, я думаю, вы убедились, что Алгоритм Волновой трассировки (Алгоритм Ли) совсем не сложен для реализации. Он выполняет поиск минимального пути, делая небольшое количество вычислений. При желании, данный универсальный алгоритм можно усложнить.

Комментарии

Комментарии

Только авторизованные пользователи могут оставлять комментарии.
Пожалуйста, Авторизуйтесь или Зарегистрируйтесь
20 августа 2018 г. 9:14
nayk1982

C++ - Тест 001. Первая программа и типы данных

  • Результат 86баллов,
  • Очки рейтинга6
20 августа 2018 г. 9:07
nayk1982

Qt - Тест 001. Сигналы и слоты

  • Результат 84баллов,
  • Очки рейтинга4
19 августа 2018 г. 10:43
Виктор Попов

Qt - Тест 001. Сигналы и слоты

  • Результат 78баллов,
  • Очки рейтинга2
Последние комментарии
20 августа 2018 г. 17:02
Евгений Ереметько

Qt/C++ - Урок 027. Полиморфизм в Qt на примере геометрических фигур в QGraphicsScene

Добрый день, начал только изучать Qt C++. Никак не могу понять, как удалять последний созданный элемент. Заранее спасибо.
17 августа 2018 г. 15:47
Евгений_Канусовский@1981

PyQt5 - Урок 003. QSystemTrayIcon - Как свернуть приложение в трей

Решение проблемы нашел в интернете)) Лечится так:File - Settings - Project:{name_my_project} - Project Interpreter - устанавливаем нужную нам версию интерпретатора(python 3.6.2 например) -...
16 августа 2018 г. 17:20
Евгений_Канусовский@1981

PyQt5 - Урок 003. QSystemTrayIcon - Как свернуть приложение в трей

Добрый вечер Евгений и форумчане! Не подскажите почему в при запуске данного кода в PyCharm выдаётся сообщение: "ModuleNotFoundError: No module named 'PyQt5'"?
10 августа 2018 г. 13:40
Alex

Работа с триггерными функциями в PostgreSQL

Приветствую! Если вы создаете новую таблицу, почему бы просто не сделать вьюху ? Просто от одного названия "триггер" как-то не хочется его использовать, а уж кода сколько писа...
Сейчас обсуждают на форуме
20 августа 2018 г. 13:18
LittleTux

Странное поведение сингелтона, а может быть, и не в нем проблема...

Лучше возвращать ссылку на экземпляр класса:PaletteUtils& PaletteUtils::instance(){ static PaletteUtils _instance; return _instance;}и если уж делать singleton, то хорошо было ...
20 августа 2018 г. 6:45
LittleTux

Как правильно сбросить позицию touchscreen в 0, как это делается с курсором QCursor::setPos(0,0)?

Ранее не сталкивался с разработкой под устройства с touchscreen, но вот наступило такое время... и возникла проблема: есть у нас mainWidget, на нем лежит stackwidget, в котором есть пару видже...
19 августа 2018 г. 12:38
Alex

Подключение карты через плагин OSM. С localhost Qt/QML

наткнулся на возможное решение, конкретно для geoserver'a http://localhost/gwc/tms/1.0.0/gis:service@EPSG%3A900913@png/{z}/{x}/{-y}.png
17 августа 2018 г. 20:35
Чарльз Грин

Как вывести видео на 2 QVideoWidget?

Есть прога, в ней qvideowidget предпросмотр, а нужно, чтоб с этого же плеера видео выводилось и на второй монитор одновременно и управлялось одними эл. управления. Подскажите пожалуйста как эт...
17 августа 2018 г. 8:52
nayk1982

Помогите разобраться с версиями библиотек, компиляторов короче запутался с этим Qt

https://www.qt.io/download-qt-installer   - Качайте Online инсталлятор под нужную ОС и устанавливайте через него нужные версии библиотек.

Рекомендуемые страницы