Курсовая работа: Поиск кратчайшего пути в лабиринте 2
Выполнил: Иванов Б.Н.
Владивосток 2009
Содержание
1. Введение
2. Формальная постановка задачи
3. Методы решения
4. Модульная организация приложения
4.1 Общая схема взаимодействия модулей
4.2 Описание модулей
5. Текст программы
6. Руководство пользователя
7. Тестовый пример игры
Заключение
Список литературы
1. Введение
Условие решаемой задачи дословно по заданию звучит следующим образом: «Задан лабиринт, составленный из комнат, у каждой из которой имеется не менее одной и не более трех дверей, соединяющих между собой различные комнаты. Одна из дверей называется входом в лабиринт, другая — выходом. Найти кратчайший путь от входа в лабиринт к его выходу ».
Целью представленной работы является разработка приложения “Поиск кратчайшего пути”, которое создает лабиринт и находит кратчайший путь его прохождения и отображает его.
Лабиринт задается во входном файле, в том же файле указываются координаты входа и выхода, и для начала работы нам необходимо выбрать нужный лабиринт, программа должна выдать размер кратчайшего пути, нарисовать лабиринт и показать этот путь.
Если же путь не найден программа выдает сообщение, о том что данный путь не существует.
2. Формальная постановка задачи
Для программной реализации необходимо формализовать структуры данных задачи и рассмотреть методы ее решения. Лабиринт мы задаем во входном файле матрицей, состоящих из 8, 0 и 1. Каждая запись массива определяет комнату лабиринта — восьмерка характеризует саму комнату и четыре координаты вокруг нее (0- стена или 1- проход) есть или нет проход. Так же во входном файле задаются координаты входа, выхода и размерность массива. Именно с этим массивом работает программа при нахождении пути.
3. Методы решения задачи
Существует довольно много различных методов решения подобной задачи, каждый из которых основывается на своих принципах и приемах, имеет уникальные преимущества и, соответственно, недостатки. В данной работе был использован метод нахождения кратчайшего пути на графе.
Этот алгоритм определяет расстояние между вершинами в простом орграфе с неотрицательными весами. Если граф не взвешен, то можно считать, что все ребра имеют одинаковый вес.
Возьмем простой граф для каждого ребра определим вес, то есть длина любого ребра больше 0. Найдем кратчайший путь между вершинами которые мы определили как начала и конец. Несуществующие ребра будем считать ребрами с бесконечными весами. Сумму весов ребер в пути будем называть весом или длиной пути. Алгоритм поиска кратчайшего пути, начинаем из вершины которую мы обозначили как начало, просматривает граф в ширину помечая пройденные вершины значениями-метками их расстояния от начала. Метки могут быть временные и окончательные. Окончательная метка- это минимально расстояние на графе от начала до пройденной вершины. Таким образом, в каждый момент времени работы алгоритма некоторые вершины будут иметь окончательные метки, а остальная их часть – временные. Алгоритм заканчивается, когда конечная вершина получает окончательную метку, то есть расстояния от начала до конца.
--> ЧИТАТЬ ПОЛНОСТЬЮ <--