Нотатки про програмування, музику, подорожі та плівку
Про мене  •  Список нотаток  •  Плівка

Алгоритм поиска Ли

Алгоритм поиска пути в планарном графе. Зачастую используется в схемотехнике и в играх (стратегиях) для поиска кратчайшего пути.

Алгоритм состоит из 3 шагов:

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

Также есть 2 способа поиска пути: ортогональный и ортогонально-диагональный. Ниже на скриншотах можно увидеть работу этих двух способов.

Ортогональный поиск.
Ортогонально-диагональный поиск.

Псевдокод

Взято из Википедии.

Инициализация

Пометить стартовую ячейку 
d := 0

Распространение волны

ЦИКЛ
  ДЛЯ каждой ячейки loc, помеченной числом d
    пометить все соседние свободные непомеченные ячейки числом d + 1
  КЦ
  d := d + 1
ПОКА (финишная ячейка не помечена) И (есть возможность распространения волны)

Восстановление пути

ЕСЛИ финишная ячейка помечена
ТО
  перейти в финишную ячейку
  ЦИКЛ
    выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке
    перейти в выбранную ячейку и добавить её к пути
  ПОКА текущая ячейка — не стартовая
  ВОЗВРАТ путь найден
ИНАЧЕ
  ВОЗВРАТ путь не найден

Пример кода, который реализует алгоритм и выводит на экран путь (C#).

Надіслати
Поділитись
Запінити