Постановка задачи. 
Поиск кратчайшего пути в лабиринте

Задача данной курсовой работы состоит в разработке и написании программы на языке Си для поиска кратчайшего пути в лабиринте. Теория о нахождении кратчайших путей имеет весьма важное значение и широко применяется. Например, используется при нахождении оптимального маршрута между двумя объектами на местности, также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet, при проектировании и построении плат и мн. др.

Все алгоритмы, применяемые для нахождения кратчайшего пути можно разделить на два типа: алгоритмы на графах и алгоритмы на массивах.

Итак, как было отмечено выше, задачу о нахождении кратчайшего пути можно рассматривать при помощи математического объекта, называемого графом. Граф задается множеством точек (вершин) и множеством линий (ребер), соединяющих все или часть этих точек.

Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути на графе:

• 1) алгоритм Дейкстры. Используется для нахождения оптимального маршрута между двумя вершинами.
• 2) алгоритм Флойда. Используется для нахождения оптимального маршрута между всеми парами вершин.
• 3) алгоритм Йена. Используется для нахождения k-оптимальных маршрутов между двумя вершинами.

Самый распространенный пример подобных задач, это нахождение кратчайшего расстояния между двумя вершинами. В этом случае, весом дуги (хi, хj) будет являться расстояние между вершинами хi и хj, ну, а если такая дуга отсутствует, то ее вес полагается равным бесконечности (на практике — это максимальное число, возможное на данном языке программирования).

Наиболее эффективный алгоритм решения задачи о кратчайшем (s-t)-пути первоначально предложил Дейкстра (1959г.). В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины от s к этой вершине. Эти пометки (их величины) постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является временной, а дает точную длину кратчайшего пути от s к рассматриваемой вершине.

Только что описанный алгоритм Дейкстры применим для нахождения кратчайшего пути между двумя заданными вершинами s и t. Что бы найти кратчайшие пути между всеми парами вершин, можно n-раз воспользоваться алгоритмом Дейкстры, причем каждый раз в качестве начальной вершины s будут браться различные вершины. В этом случае время, необходимое для вычислений, будет пропорционально n3. Поэтому, если задача о нахождении кратчайшего пути имеет большую размерность, то ее не возможно решить с помощью последовательного применения этого алгоритма.

Есть совершенно иной подход к задаче нахождения кратчайших путей между всеми парами вершин. Он сэкономит почти 50% времени по сравнению с n-кратным применением алгоритма Дейкстры. Метод был предложен первоначально Флойдом (1962 г.) и развит Мерчлендом. Он базируется на использовании последовательности из n преобразований (итераций) начальной матрицы весов С. При этом на k-й итерации матрица представляет длины кратчайших путей между каждой парой вершин с тем ограничением, что путь между xi и xj (для любых xi и xj) содержит в качестве промежуточных только вершины из множества {x1, x2,…, xk}.

На практике часто требуется найти не только кратчайший путь, но также второй, третий и т. д. кратчайшие пути в графе. Располагая этими результатами, можно решить, какой путь выбрать в качестве наилучшего. Для решения этой задачи нужно воспользоваться алгоритмом Йена (1971г.). Этот алгоритм требует порядка Kn3 операций.

Существует тип алгоритмов, который в американской литературе фигурирует под названием backtracking algorithms, что в переводе означает «алгоритмы с откатом». Как правило, такие алгоритмы строятся на основе рекурсии. Эти алгоритмы отличаются от других тем, что ищут решения методом проб и ошибок, перебирая все или почти все варианты.

Backtracking используется в тех случаях, когда более интеллектуальные решения невозможны. Количество таких задач ограничено. Например, поиск оптимума с полным перебором всех вариантов, поиск любого решения с выходом при его отыскании или поиск оптимального решения с оптимизацией полного перебора (отсечением вариантов, которые заведомо хуже ранее найденного оптимального решения). К такому методу относится волновой алгоритм.

Основная часть алгоритма — построение на основе массива множества точек, до которых можно добраться за К шагов и нельзя быстрее (этот процесс аналогичен процессу распространения волны, откуда и произошло название алгоритма).

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