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

АННОТАЦИЯ

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

• Программа предназначена для использования в учебных заведениях, в познавательных целях. Также возможно использование в целях самопроверки.
• В данной работе приводятся диаграммы потоков данных, диаграммы состояния, диаграммы взаимодействия модулей. Доступным языком описывается методология создания программы.
• Разработана спецификация функций программы, описано поведение программы в критических ситуациях, приводится спецификация модулей. В документации также приведены текст программы и результаты тестирования программы.
• 1 Техническое задание
• Введение
• Полное название разработки ”Поиск кратчайшего пути”. Данная разработка предназначена для использования в учебных заведениях. Она выполняет нахождение кратчайшего пути между входом в лабиринт и его выходом. Также возможно использование для самопроверки решения, принятого человеком.
• 1.1 Основания для разработки
• Данный проект разрабатывается на основании задания на курсовую работу, выданного преподавателем Сусловым С.В. студенту 4152 группы Заволоке А.А.
• Наименование темы разработки “Поиск кратчайшего пути”.
• 1.2 Назначение разработки
• Программа “Поиск кратчайшего пути” предназначается для нахождения кратчайшего пути между входом в лабиринт и его выходом.
• 1.3 Требования к программе
• 1.3.1 Требования к функциональным характеристикам
• Для контакта пользователя с программой необходимо выполнение ряда функций:
• создание сетки лабиринта;
• добавление комнат в лабиринте;
• удаление комнат в лабиринте;
• добавление дверей в лабиринте ;
• удаление дверей в лабиринте ;
• ввод входа и выхода, между которыми необходимо найти кратчайший путь;
• отображение решения;
• сохранение лабиринта;
• - загрузка сохраненного лабиринта
• Входными данными являются комнаты и двери лабиринта, которые вводятся пользователем с клавиатуры при помощи передвигающегося курсора и нажатия определённой клавиши для комнат и для дверей.
• Выходными данными является отображение на экране в графическом режиме лабиринта и кратчайшего пути.
• 1.3.2 Требования к надёжности
• Программное изделие должно быть защищено от непродуманных действий пользователя. Должен быть предусмотрен максимально возможный анализ входной информации, вводимой пользователем. В случае ввода некорректных данных игнорировать попытку ввода.
• 1.3.3 Условия эксплуатации
• Программа устойчиво и корректно функционирует при нормальных условиях эксплуатации ПЭВМ. Дополнительных условий эксплуатации не требует.
• 1.3.4 Требования к составу и параметрам технических средств
• Необходимы следующие технические средства:
• 1) ПЭВМ с тактовой частотой процессора 100 Mhz и выше.
• Монитор, поддерживающий режим VGA;
• 8 Мбайт ОЗУ и выше;
• Клавиатура.
• 1.3.5 Требования к информационной и программной совместимости
• Программа должна корректно функционировать в ОС Windows'9x.
• 1.3.6 Требования к маркировке и упаковке
• Готовое программное изделие предоставляется (хранится) на дискете 3.5 Дюйма. Требований к маркировке не предъявляется.
• 1.3.7 Требования к транспортировке и хранению
• Хранить программный продукт нужно при нормальных условиях на дискете 3.5 дюйма, то есть дискета должна храниться в герметичной, сухой, не гнущейся коробке вдали от источников тепла, влаги и от магнита.

1.4 Требования к программной документации

Программная документация должна состоять из:

хорошо прокомментированного текста программы;

общего функционального описания;

краткого описания составляющих программу функций;

схем, иллюстрирующих проект и словесного их описания;

5) руководства пользователя.

1.5 Технико-экономические показатели

Создание бесплатной альтернативы существующим на сегодня программам подобного профиля;

Быстрота вычислений.

1.6 Стадии и этапы разработки

Техническое задание

Плановые сроки начала и окончания работы:

Начало: 15.02.07

Окончание: 01.03.07

Эскизный проект

Плановые сроки начала и окончания работы:

Начало: 01.03.07

Окончание: 22.03.07

Технический проект

Плановые сроки начала и окончания работы:

Начало: 22.03.07

Окончание: 12.04.07

Рабочий проект

Плановые сроки начала и окончания работы:

Начало: 12.04.07

Окончание: 17.05.07

Ввод в эксплуатацию

Плановые сроки начала и окончания работы:

Начало: 17.05.07

Окончание: 24.05.07

1.7 Порядок контроля и приёмки

Испытание должно проводиться совмесно с заказчиком и разработчиком в соответствии с “Программой и методикой испытаний “.

2. Эскизный проект

2.1 Контекстная диаграмма

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

При работе с данной программой необходимо наличие трёх главных компонентов : пользователь, компьютер и программа (рис.2.1).

Рисунок 2.1 - Контекстная диаграмма

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

2.2 Словарь данных

Лабиринт - множество комнат, соединённых между собой дверьми.

Комната - символически изображенный квадрат, заданный в лабиринте.

Дверь -устройство, соединяющее комнаты.

Данные редактирования - изменение лабиринта, т.е. ввод комнат и дверей, а также их удаление.

Результат - Кратчайший путь в лабиринте.

2.3 Диаграмма состояний

Рисунок 2.3 - Диаграмма состояний

Состояние 0 - загрузка программы - начальное состояние, в котором находится программа после загрузки. В этом состоянии пользователь может ознакомиться с управлением или выйти из программы.

Состояние 1 - создание лабиринта - состояние, в котором формируется лабиринт.

Состояние 2 - ввод комнаты - в этом состоянии пользователь может ввести комнату.

Состояние 3 - ввод двери - в этом состоянии пользователь может ввести дверь.

Состояние 4 - удаление комнаты - в этом состоянии пользователь (при необходимости) может удалить существующую комнату.

Состояние 5 - удаление двери - в этом состоянии пользователь (при необходимости) может удалить существующую дверь.

Состояние 6 - сохранение лабиринта - пользователю предоставляется возможность сохранить лабиринт.

Состояние 7 - загрузка лабиринта - пользователю предоставляется возможность загрузить, ранее сохраненный, лабиринт.

2.4 Построение модели пользовательского интерфейса

Для удобства ввода, редактирования и удаления элементов лабиринта, необходимо создать удобный, дружественный интерфейс.

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

После ввода лабиринта в левом верхнем углу экрана выдаётся приглашение: “Введите вход в лабиринт ” после чего ожидается выбор одной из комнат в лабиринте, с помощью клавиш управления курсром и клавиши <Enter>, при этом выдаётся пиглашение: “Введите выход из лабиринта”. После выбора выхода программа выдаёт сообщение: “Кратчайший путь найден ” - в том случае, если он найден или “пути нет ” - если пути не существует. Если кратчайший путь найден, то он будет показан на графе в виде подсветки красным цветом. Далее предлагается выйти из программы путём нажатия клавиши <Esc> или начать ввод нового лабиринта нажав при этом любую клавишу. При этом существует клавиша <c> и <з> соответственно для сохранения лабиринта или загрузки уже существующего.

3 Технический проект

3.1 Диаграмма потоков данных

Программа имеет 4 основных процесса, отражающие основные функции программы:

Рисунок 3.1 - Диаграмма 1-го уровня

Страницы: 1, 2, 3, 4