МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
ДГТУ
Факультет Информатика и вычислительная техника
Кафедра «ПОВТ и АС»
ОТЧЕТ
по распределенной компьютерной 2 курса практике
в ДГТУ
в период с «__»_________________20__г. по «__»______________20__ г.
студента группы ВПР22 Гевало Ивана Александровича
Руководитель практики
от кафедры старший преподаватель Романенко Е.А.
Оценка
Ростов-на-Дону
2013 Г.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ………………………………………………………………………… 3
1 ПОСТАНОВКА ЗАДАЧИ……………………………………………………... 4
2 АЛГОРИТМИЧЕСКОЕ КОНСТРУИРОВАНИЕ……………………………. 5
2.1 Формальное описание алгоритма…………………………………….….… 5
2.2 Блок-схема алгоритма…………………………………………………….…. 5
3 ПРОГРАММНОЕ КОНСТРУИРОВАНИЕ…………………………………... 11
4 КОНТРОЛЬНЫЙ ПРИМЕР…………………………………………………….. 12
5 РЕКОМЕНДАЦИИ ПОЛЬЗОВАТЕЛЮ…………………………………….. 15
6 РЕКОМЕНДАЦИИ ПРОГРАММИСТУ…………………………………….. 16
7 ЗАКЛЮЧЕНИЕ………………………………………………………………… 19
8 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ…………………………… 20
Приложение А. Код программы…………………………...……………………... 21
ВВЕДЕНИЕ
При разработке программного обеспечения перед программистом встает вопрос о реализации тех или иных алгоритмов. В рамках определенной задачи разработчику требуется либо самому разрабатывать эти алгоритмы, либо обращаться уже к известным, так называемым «классическим», алгоритмам.
Тема данной работы - «Программная реализация алгоритма Ли», также известного как волновой алгоритм. Алгоритм позволяет найти минимальный путь в графе с ребрами единичной длины. Он основан на алгоритме поиска в ширину. Имеет широкое применение при разработке компьютерных игр таких жанров, как RTS (стратегия в реальном времени) и RPG (ролевые игры). Помимо всего прочего это один из основных алгоритмов при автоматизированной трассировке печатных плат.
Несмотря на свою простоту, алгоритм очень эффективен при поиске пути от одной точки до другой, учитывая обход различных препятствий. Волновой алгоритм имеет несколько разновидностей: алгоритм Ли (классический вариант), заполнение по матрице в 8 направлений, алгоритм A* (A-star).
1 Постановка задачи
Целью является программная реализация классического варианта волнового алгоритма – алгоритма Ли. Разрабатываемое программное средство должно автоматизировать процесс построения пути между двумя указанными точками, учитывая возможные препятствия, находящиеся на «карте». Необходимо также реализовать программный вывод всей необходимой информации: начальная (стартовая) позиция, целевая (финишная) позиция, количество волн, построенных в процессе одного такта работы программы, фронт каждой построенной волны. Кроме того, необходимо обозначить путь, преодолеваемый перемещаемым объектом. Следует также обеспечить возможность реорганизации «карты» для отработки и тестирования работы алгоритма в разных ситуациях. Таким образом, конечное программное средство должно отвечать следующим требованиям:
полная работоспособность программы;
вывод всей необходимой информации;
обеспечение работы алгоритма в разных ситуациях;
удобный и понятный пользовательский интерфейс.
2 Алгоритмическое конструирование
2.1 Формальное описание алгоритма
На двумерной клетчатой карте (матрице), состоящей из «проходимых» и «непроходимых» клеток, обозначена клетка старта и клетка финиша. Цель алгоритма – проложить кратчайший путь от клетки старта к клетке финиша, если это возможно. От финиша во все направления распространяется волна, причем каждая пройденная волной клетка помечается как «пройденная». Волна, в свою очередь, не может проходить через клетки, помеченные как «пройденные» или «непроходимые». Волна движется, пока не достигнет точки старта или пока не останется не пройденных клеток. Если волна прошла все доступные клетки, но так и не достигла клетки старта, значит, путь от старта до финиша проложить невозможно. После достижения волной старта, от финиша прокладывается путь до старта.