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

Министерство образования и науки Российской Федерации

Агентство по образованию

Тихоокеанский государственный экономический университет

Экономический институт

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

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

Выполнил: Иванов Б.Н.

Владивосток 2009

Содержание

1. Введение

2. Формальная постановка задачи

3. Методы решения

4. Модульная организация приложения

4.1 Общая схема взаимодействия модулей

4.2 Описание модулей

5. Текст программы

6. Руководство пользователя

7. Тестовый пример игры

Заключение

Список литературы

1. Введение

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

Целью представленной работы является разработка приложения “Поиск кратчайшего пути”, которое создает лабиринт и находит кратчайший путь его прохождения и отображает его.

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

Если же путь не найден программа выдает сообщение, о том что данный путь не существует.

2. Формальная постановка задачи

Для программной реализации необходимо формализовать структуры данных задачи и рассмотреть методы ее решения. Лабиринт мы задаем во входном файле матрицей, состоящих из 8, 0 и 1. Каждая запись массива определяет комнату лабиринта — восьмерка характеризует саму комнату и четыре координаты вокруг нее (0- стена или 1- проход) есть или нет проход. Так же во входном файле задаются координаты входа, выхода и размерность массива. Именно с этим массивом работает программа при нахождении пути.

3. Методы решения задачи

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

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

Возьмем простой граф для каждого ребра определим вес, то есть длина любого ребра больше 0. Найдем кратчайший путь между вершинами которые мы определили как начала и конец. Несуществующие ребра будем считать ребрами с бесконечными весами. Сумму весов ребер в пути будем называть весом или длиной пути. Алгоритм поиска кратчайшего пути, начинаем из вершины которую мы обозначили как начало, просматривает граф в ширину помечая пройденные вершины значениями-метками их расстояния от начала. Метки могут быть временные и окончательные. Окончательная метка- это минимально расстояние на графе от начала до пройденной вершины. Таким образом, в каждый момент времени работы алгоритма некоторые вершины будут иметь окончательные метки, а остальная их часть – временные. Алгоритм заканчивается, когда конечная вершина получает окончательную метку, то есть расстояния от начала до конца.

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

1. Каждой вершине, не имеющей окончательной метки, присваивается новая временная метка – наименьшая из ее временной и числа, которому присвоена окончательная метка на предыдущем шаге.

2. Определяется наименьшая из всех временных меток, которая и становится окончательной меткой своей вершины. В случае равенства выбирается любая из них.

Циклический процесс п.1 и п.2 продолжается до тех пор, пока конечная вершина не получит окончательной метки. Легко видеть, что окончательная метка каждой вершины – это кратчайшее расстояния между начальной и конечной вершинами.

4. Модульная организация приложения

Реализация проекта выполнена в рамках трех модулей. Каждый из них выполняет определенные для него функции. Разделение функций модулей выполнено в соответствии с задачами проекта. В общем случае разделение выполняется на две составные части: проведение расчетов и визуализация полученных данных.

4.1 Общая схема взаимодействия модулей

4.2 Описание модулей

Каждый из модулей реализует свой класс. Описание модулей призываются к описанию классов (их назначения) и методов классов (решения определенных задач класса).

1). UnWay — модуль реализации класса TWay проведения всех вычисления нахождения кратчайшего пути.

Методы класса T Way.

Procedure TWay.Input — процедура ввода перегородок комнаты

Procedure TWay.CreateAdj — процедура формирование матрицы смежности комнат

Procedure TWay.ShortRoom – процедура поиска минимального пути

2). UnDraw — модуль реализации класса TOcno

Методы кла

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать