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

Размещено на http://www.allbest.ru/

МО РБ

Полоцкий государственный университет

Кафедра информационных технологий

Курсовая работа

по курсу: “Конструирование программ и языки программирования”

на тему: “Поиск кратчайшего пути в лабиринте”

Разработала: Дягилева Н.В.

Проверил: Чеботарёв С.П.

Новополоцк 2003

Введение

В начале компьютерной эры программисты были рабами вычислительных машин. Разработчики программного обеспечения должны были писать свои команды на единственном языке, который понимали компьютеры, - в двоичном коде, и программы выглядели как последовательность нулей и единиц. По мере того как время шло и алгоритмы усложнялись, программирование требовало всё больше времени, а внесение изменений в программы и их модернизация становились практически невозможными. Так появились языки программирования высокого уровня: Фортран, Бейсик, Паскаль. Требования к программам росли, времени для их написания отводилось всё меньше, программистам надо было сосредоточится на сложных алгоритмах, их эффективной реализации, не отвлекаясь на внутреннюю структуру компьютера. А тут ещё проблемы переносимости программ на новые компьютеры с новыми возможностями. Был необходим новый подход - и он появился в виде объектно-ориентированного программирования.

В данной курсовой работе при написании программы был использован язык Си. Язык Си - это универсальный язык программирования, для которого характерны экономичность выражения, современный набор операторов и типов данных. Язык Си не является языком "очень высокого уровня" и не предназначается для некоторой специальной области применения, но отсутствие ограничений и общность языка делают его для многих задач более удобным и эффективным, чем языки, предположительно более мощные. Язык Си не связан с какими- либо определенными аппаратными средствами или системами, и на нем легко писать программы, которые можно пропускать без изменений на любой ЭВМ, имеющей Си-компилятор.

1. Постановка задачи

Задача данной курсовой работы состоит в разработке и написании программы на языке Си для поиска кратчайшего пути в лабиринте. Теория о нахождении кратчайших путей имеет весьма важное значение и широко применяется. Например, используется при нахождении оптимального маршрута между двумя объектами на местности, также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета 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 используется в тех случаях, когда более интеллектуальные решения невозможны. Количество таких задач ограничено. Например, поиск оптимума с полным перебором всех вариантов, поиск любого решения с выходом при его отыскании или поиск оптимального решения с оптимизацией полного перебора (отсечением вариантов, которые заведомо хуже ранее найденного оптимального решения). К такому методу относится волновой алгоритм.

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

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

2. Проектирование программы

Прежде всего построим модель задачи. Здесь мы должны решить, то означают слова: "карта лабиринта", "непроходимый участок", "кратчайший маршрут".

Всю карту можно представить в виде двухмерного целочисленного массива Map, индексы которого -- координаты соответствующих точек, а значения -- признак возможности прохождения точки с координатами х и у. Map [х, у] = 0, если участок проходим, и равно --1, если нет. Две точки будем называть соседними, если они имеют только одну различную координату (например, точки Map [5, 4] и Map [6, 4] -- соседние, а точки Map [5, 4] и Map [6, 3] -- нет). Маршрутом будем считать последовательность соседних точек карты. Длиной маршрута будем считать число клеток в нем.

В терминах этой модели исходная задача формулируется так: даны двухмерный числовой массив Map с элементами, равными 0 и --1, и две пары индексов (две точки): x_begin, y_begin и x_end, y_end. Требуется построить последовательность соседних элементов с нулевыми значениями такую, чтобы первым элементом в ней был Map [x_begin, y_begin], а последним -- Map [x_end, y_end], причем число элементов в ней было бы минимальным из всех возможных.

Содержательное описание волнового алгоритма таково:

1. Начальный этап. Пометим начальную точку числом 1 (в эту точку ведет маршрут длины 0).

2. Распространение волны. Если рассматриваемая точка помечена числом К > 0 (в нее можно попасть за К--1 шагов), то все соседние точки, помеченные нулем, надо пометить числом К + 1 (в них можно попасть за К шагов). Распространение волны осуществляется до тех пор, пока это возможно (есть еще соседние, помеченные нулем, точки) и целесообразно (еще не дошли до конечной точки).

3. Проверка возможности построения пути. Если после распространения волны конечная точка помечена некоторым числом К > 0, то в нее можно попасть за К-- 1 шаг. В противном случае эта точка недостижима из начальной.

4. Построение пути. Для того чтобы построить оптимальный маршрут, необходимо, начиная с конечной точки, выбирать соседнюю с ней, помеченную числом на единицу меньше. Затем проделать это же с новой точкой. И так далее, пока не доберемся до начальной.

Из описания алгоритма видно, что он распадается на два этапа: распространение волны (включая начальный этап) и построение пути.

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

Для реализации данных возможностей были написаны следующие модули:

GRAPHICA;

SHORTWAY;

MOUSE;

MAIN.

В модуле GRAPHICA содержатся функции рисования различных графических объектов.

В модуле SHORTWAY содержатся функции для нахождения пути, а также функции для работы с файлами и функции для создания и работы с меню программы.

В модуле MOUSE содержатся функции для работы с мышью.

Модуль MAIN является главным, потому что он содержит функцию MAIN и управляет работой всей программы.

В данной курсовой используются следующие типы данных:

динамические массивы целых чисел MAP и WAY для хранения карты и пути;

динамический список для хранения имён файлов, в которые записываются карты.

Далее рассмотрим более подробно функции каждого модуля, их назначение при работе программы, установим связи между функциями и между самими модулями.

3. Реализация программы

3.1 Модуль GRAPHICA

Данный модуль содержит следующие функции:

- void InitGraph() - инициализирует графический режим;

- int Size_of_Map(int &maxx,int &maxy) - рисует окно для введения размеров карты и возвращает эти размеры(int maxx,int maxy);

- void Draw_Menu() - рисует меню;

- void Draw_Map(int maxx,int maxy) - принимает в качестве параметров размеры карты(int maxx,int maxy) и рисует по ним “пустую” карту;

- int DrawObject(int &i) - в правом нижнем углу экрана отбражает текущий объект(block - стена; Start - начальная точка; Finish - конечная точка) и по нажатию правой клавиши мыши меняет объект, в качестве параметра принимает текущий номер объекта(0 - block; 1 - start; 2- finish) по ссылке, при необходимости меняет его и возвращает в момент вызова функции;

- void DrawBlock(int maxx,int maxy) - рисует на карте по значениям массива MAP cоответствующие объекты(-1 - стена; 0 - проход; 1 - S; 2 - F), принимает в качестве параметров размеры карты;

- int Menu() - реализует возможность перемещения по меню и по нажатию клавиши ENTER возвращает код выбранного значения(0 - DRAW; 1 - LOAD; 2 - SAVE; 3 - FIND; 4 - HELP; 5 - EXIT );

- void DrawPath(int maxx,int maxy,int x_end, int y_end) - по значениям массива WAY рисует на карте массив.

3.2 Модуль SHORTWAY

Данный модуль кроме функций (см. ниже) содержит также такие глобальные переменные как int **Way - двойной указатель на массив указателей одномерных массивов(массив пути), int **Map - массив карты.

Функции Move_Head(),Move_Next(),Move_Prev(),CreateData(), Destroy(), Add() нужны для работы с динамическим списком, в котором хранятся имена файлов, хранящих карты.

- void Move_Head() - устанавливает текущий указатель на начало списка;

- void Move_Next() - перемещает указатель по списку вперёд;

- void Move_Prev() - перемещает указатель по списку назад;

- void CreateData() - считывает из файла BASEDAT.TXT в список имена файлов;

- void Destroy() - удаляет список из памяти, предворительно записав значения в файл BASEDAT.TXT;

- int Add(char str[12]) - добовляет в конец списка очередное значение, прочитанное либо из файла BASEDAT.TXT, либо введённое при сохранении карты в функции Save(); в качестве параметра функция принимает значение типа char(имя файла), а возвращает целочисленное значение(1 - если добавление произошло и 0 - в противном случае);

- void CreateMap(int Length_Map,int Width_Map) - создаёт массив MAP, при чём если данный массив уже существовал, то происходит его удаление из памяти, а затем уже создаётся новый массив; в качестве параметров функция принимает целочисленные значения (размеры карты);

- void Restore_Map(int maxx,int maxy) - возобнавляет карту(массив MAP) после распространения волны; в качестве параметров принимает размеры карты;

- void AddMap(int i,int j) - по нажатию левой клавиши мыши и при выбранном объекте Block добавляет в массив MAP -1 по соответствующим координатам; в качестве параметров принимает координаты стены;

- int Save(int maxx,int maxy) - сохраняет в файле карту; в качестве параметров принимает размеры карты, которые тоже записываются в этот же файл (это нужно для загрузки карты из файла);

int GetString(char *str, int x,int y) - позволяет прочитать строку (имя файла) при её вводе, а также производит проверку на правильность ввода имени файла; в качестве параметров принимает координаты, по которым будет производится ввод строки, возвращает строку, а также значение целого типа (-1 - произошёл выход из функции по ESC без считования в строку, 0 - ошибка в имени файла, 1 - произошло считование строки);

- void Load(int &maxx,int &maxy) - производит загрузку из файла карты, возвращая по ссылке размеры карты;

- int ShortWay(int Length_Map,int Width_Map,int x_begin,int y_begin,int x_end,int y_end) - производит формирование массива WAY, принимая в качестве параметров размеры карты и кординаты начальной и конечной точек; возвращает 0 - если построение пути невозможно, в противном случае возвращает длину пути;

- void Wave(int x_begin,int y_begin,int x_end,int y_end,int Length_Map,int Width_Map) - функция распространения волны, в качестве параметров принимает конечной и начальной точек, а также размеры карты;

- void Way_Step(int x,int y,int step) - присоединяет очередную точку к маршруту, принимая в качестве параметров кординаты точки и шаг;

- void Track(int x_end,int y_end) - функция построения пути использует заполненный массив MAP и на его основе формирует массив WAY, начиная от конечной точки, принимает в качестве параметров координаты конечной точки.

3.3 Модуль MOUSE

Данный модуль содержит следующие функции:

- void MouseClose() - данная функция “гасит” мышь на экране;

- void InitMouse() - инициализирует мышь;

- int MouseHit(int &x,int &y) - возвращает код нажатой клавиши мыши (0 - никакая клавиша не нажата, 1 - нажата левая клавиша, 2 - нажата правая клавиша), а также по ссылке возвращает координаты мыши.

3.4 Описание работы программы

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

В модуле MAIN включены все остальные модули, а сам модуль содержит только функцию main. Поэтому описание работы программы начнём с описания функции main.

Итак, вначале инициализируем графический режим с помощью функции INITGRAPH, отрисовываем меню(Draw_Menu), создаём список Basedat для хранения имён файлов, отрисовываем объект(по умолчанию Block) c помощью функции DrawObject, инициализируем мышь.

Затем входим в цикл, выходом из которого является выбор в меню кнопки EXIT. Для входа в меню нажимаем F10. Если в меню выбираем DRAW, то выполняем следующий блок: гасим мышь(MouseClose), считываем размеры карты(Size_of_Map), отрисовывем меню(DrawMenu), отрисовываем объект(DrawObject), создаём карту(CreateMap) и отрисовываем её(DrawMenu), инициализируем мышь(InitMouse). Если в меню выбираем LOAD, то выпоняется следующий блок: гасим мышь(MouseClose), загружаем карту(Load), инициализируем мышь (InitMouse). Если в меню выбираем SAVE, то выполяется блок, в результате которого происходит сохранение карты в файл (основная функция - Save). Если в меню выбираем FIND, то выполняется блок, в котором получаем путь или собщение о том, что путь не существут(главная функция - ShortWay). Кроме работы с меню в главном цикле осуществляется считывание и анализ нажатой клавиши мыши (MoseHit). Если нажата левая клавиша, то в массив Map заносится определённое значение(AddMap), по которому затем на карте по сответсвующим координатам рисуется текущий объект(DrawBlock). Нажатие правой клавиши мыши позволяет сменить объект рисования.

Для организации такой работы программы необходимо, чтобы в модуле MAIN были включены остальные модули(MOUSE, SHORTWAY, GRAPHICA). Модуль MAUSE включен также в модуль GRAPHICA, а модули GHORTWAY и GRAPHICA включены друг в друга. Включение функций можно проследить по схеме вызова функций (Приложение Б).

4. Методика и результаты тестирования

При создании и отладке программы были произведены следующие тесты и получены следующие результаты.

TEST 1

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

Таблица 1

Массив МАР

MAP[7][13] ->MAP[1][1]

Таблица 2

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

Таблица 3

Массив WAY

TEST 2

Таблица 4

Массив МАР

MAP[1][2]->MAP[5][6]

Таблица 5

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

Таблица 6

Массив WAY

Заключение

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

Литература

1. Карпов Б., Баранова Т. С++:специальный справочник. СПБ: Питер, 2001.

2. Болсии М.И. Язык программирования Си. М.: Радио и связь, 1988.

3. Керниган Б., Ритчи Д., Фьюкор А. Язык программирования Си. Задачи по языку Си. М.: Финансы и статистика, 1985, 1992.

4. Хэнкок Л., Кригер М. Введение в программирование на языке Си. М.: Радио и связь, 1986. 4. Уэйт М., Прата С., Мартин Д. Язык Си. М.: Мир, 1988.

Приложение А

(Схема модулей)

Размещено на http://www.allbest.ru/

Приложение Б

Размещено на http://www.allbest.ru/

(Схема вызова функций)

Размещено на Allbest.ru