Статьи Королевства Дельфи
Определение кратчайшего пути между двумя точками
| лес, дата публикации 02 июня 2003г. |
| Предпосылки. |
Недавно мне пришлось столкнуться с проблеммой нахождения кратчайшего пути между двумя точками. Существует несколько методов для решения этой задачи (метод Флойда, алгоритм Дейкстры и др.) Но описания этих методов мне показались сложными (и для меня - не математика - не совсем понятными), поэтому хотелось найти, что-нибудь более простое.
Эта тема уже поднималась на страницах нашего сайта (в рубрике Подземелье магов, А. Моисеевым ). Там была приведена реализация алгоритма Дейкстры. Но эта реализация оперирует не совсем понятными мне понятиями типов территорий (всего 6 типов) и, несомненно, предоставляя бОльшие возможности разработчику, становится сложнее по определению. Мне же было необходимо определить всего две вещи: существует ли в принципе какой-нибудь путь, и, если существует, найти кратчайший. (Как это происходит в известных играх Lines или Sokoban).
Здесь я хотел бы описать метод, разработанный мной и моим коллегой Манфредом Рауером (Manfred Rauer). Мы не претендуем на приоритет но, так как не являемся профессиональными математиками и не знаем известен ли уже этот алгоритм (во всяком случае я не нашел похожего описания), мы назвали его Алгоритмом Кегелеса-Рауера.
| Задача. |
Определить кратчайший путь между двумя точками на плоскости, обходя имеющиеся на ней препятствия.
| Алгоритм. |
Плоскость (поле) на которой следует определить путь представляется массивом чисел (integer), в котором преграда получает значение "-1", точка финиша (цель) - значение "1", а все остальные точки - значения "0". Затем от цели (элемент со значением "1") веером во все стороны, пока не встретиться преграда (-1) элементам массива, имеющим нулевое значение присваиваются значения на единицу большие, чем у соседнего элемента.
Выглядит это, приблизительно так, если поле символически изобразить таким образом: ####### # S # # ### # # # # F # ####### где # - преграда, S и F - точки старта и финиша; то массив будет иметь следующий вид: после инициализации: после заполнения значениями: -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 6 7 8 7 6 -1 -1 0 -1 -1 -1 0 -1 -1 5 -1 -1 -1 5 -1 -1 0 0 0 0 0 -1 -1 4 3 2 3 4 -1 -1 0 0 1 0 0 -1 -1 3 2 1 2 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
