Задача поиска маршрута формально определяется следующим образом:

• Дан набор точек. Одна из них помечена, как начальная, другая — как конечная.
• Для каждой пары точек A и B, определено расстояние от A до B. Расстояние может равняться "бесконечности", если A и B непосредственно не соединены. Расстояние из A в B может быть не равно расстоянию из B в A (как, например, для дороги с односторонним движением).
• Путь — это подмножество точек A₁, A₂, A₃, и т. д., A_N. Определим путь без циклов, как путь, точки которого не повторяются. Длина пути — это сумма расстояний из A₁ в A₂, из A₂ в A₃, и т. д., из A_N-1 в A_N.
• Рассмотрим множество всех путей между начальной точкой A, и конечной B. Если какой-нибудь путь между этими точками существует, такое множество не пусто и, следовательно, имеет элемент с наименьшей длиной. Очевидно, что это и если тот кратчайший путь, который нам предстоит найти.

Алгоритм полного перебора

Одно из возможных решений — это полный перебор всех возможных. маршрутов. Если путь существует, он состоит не более, чем из N точек. Таким образом, предполагаемый алгоритм строит путь с началом в точке A во всех возможных направлениях до тех пор, пока не будет достигнута точка B, или не исчерпано N шагов.

На первом шаге может быть до N-1 ветвлений; на втором — N-2 для каждой из N-1 точек, достигнутых на предыдущем шаге, и так далее. На каждом следующем шаге количество ветвлений уменьшается, чтобы предотвратить зацикливание.

В худшем случае, программа должна будет выполнить (N-1)! шагов. Это число растет лишь немногим медленнее, чем N^N. В то же самое время, полный перебор является единственным способом оптимизации маршрута, когда, например, длина перемычек между точками может меняться в зависимости от уже пройденного пути. Вот почему практически все стратегические игры (которые не содержат заранее рассчитанного решения) используют подобный алгоритм для оценки будущих ходов.

Оптимизированный алгоритм

Вернемся к задаче поиска оптимального маршрута на статической карте. Поскольку соединения между точками не изменяются, существует решение, требующее гораздо меньших вычислительных ресурсов. Как читатель может заметить, предыдущий алгоритм будет просматривать ветку даже в случае, когда уже известен более короткий путь в ту же точку. Таким образом, трюк заключается в том, чтобы выбросить из рассмотрения часть путей, не потеряв при этом кратчайшего.

Я сначала опишу короткий алгоритм и затем докажу, что он действительно находит оптимальный путь. Также будет подсчитано количество действий, которое этот алгоритм затрачивает. Будем использовать двумерный массив A[i,j], содержащий расстояние из точки номер i в точку номер j. Введем массивы R[i] и L[i], содержащие, соответственно, точку, предшествующую i в пути до i, и длину пути из начальной точки до i. По своему смыслу, массив R содержит информацию о "пути возврата".

Программа выполняет N шагов. На каждом шаге строится список рассматриваемых точек, по смыслу аналогичный расходящимся кругам на воде. На первом шаге список содержит только начальную точку, на втором — точки, непосредственно доступные из нее... На каждом последующем шаге, список будет содержать точки, непосредственно доступные из точек, бывших в списке на предыдущем шаге.

До сих пор все выглядит так же, как и для алгоритма полного перебора, описанного выше. Но сейчас мы зададим ограничение на процесс помещения точек в список. На каждом шаге программа запоминает кратчайшее расстояние до рассматриваемой точки в массиве L, и путь возврата в массиве R. При просмотре очередной ветки, программа проверяет, существует ли уже известный путь в эту точку, и короче ли он.

Это делается сравнением значения L[i], где i — номер вновь добавляемой точки, с длиной нового пути L[j]+A[j,i], где j — предыдущая точка в нем.

Если новый маршрут в точку i короче, программа записывает новую длину пути в L[i] и новое направление возврата в R[i]. В противном случае этот маршрут удаляется из рассмотрения. Кроме того, программа должна гарантировать, что каждая точка представлена в списке не более одного раза. Попробуйте предложить способ такой проверки, который не содержит дополнительных циклов, прежде чем посмотреть ответ.

Эта процедура удаляет из рассмотрения только более длинные пути. Другими словами, если некоторый путь удален, то обязательно существует другой путь в ту же точку, и он короче. Таким образом, кратчайший маршрут никогда не будет удален.

Оценим количество действий, которое программа должна совершить для выполнения этого алгоритма. Так как общее число шагов равно N и на каждом шаге рассматривается не более N точек, общее количество циклов не превышает N². Более того, в случае если количество перемычек, которые могут соединяться с одной точкой, ограничено, (как, например, для двумерного лабиринта) то количество действий становится пропорционально N¹. Я оставляю доказательство этого факта читателю.