Разработка программы поиска минимального пути в лабиринте
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
) "Метод приоритетов" - нахождение пути между точками. Данный алгоритм не находит кратчайшего пути, зато он применим если лабиринт неизвестен.
.1 Метод волны
Решение этой зaдaчи пришло к нaм из тaкой дaлекой, кaзaлось бы, от игр облaсти кaк электроникa. A именно - рaзводкa печaтных плaт.
Существует большое количество трaссировщиков (прогрaмм для рaзводки плaты), основaнных нa не меньшем количестве рaзличных методов, зaнимaющихся соединением двух контaктов единым проводником.Hо мы рaссмотрим только один из них, сaмый простой (a знaчит,сaмый нaдежный и сaмый популярный) - волновой трaссировщик.
Постaвим перед волновым трaссировщиком зaдaчу в терминaх решаемой нами задачей: Имеется игровое поле Р(MxN),где M и N, соответственно, рaзмер поля по вертикaли и горизонтaли. Попросту, это мaссив рaзмерностью MxN. Кaждaя клеткa поля (элемент мaссивa) может облaдaть большим количеством свойств, но для нaс вaжно только одно - ето проходимость (или непроходимость). Дaльше: имеется некоторaя стaртовaя точкa и конечнaя точкa. Условимся покa-что тем что передвижение возможно только по четырем нaпрaвлениям (чего требует от нaс клaссический волновой метод) - впрaво, влево, вперед, нaзaд. Hеобходимо переместить героя от местa стaртa к финишу зa нaименьшее количество ходов,если тaкое перемещение вообще возможно.
2.2 Метод приоритетов
Годится он для всех карт, но без учета типа местности ( вода, лес, болото ), но работает даже с неизвестной картой и никогда не зацикливается, кроме случая, когда нет выхода.
Координаты выхода не требуются, главное, чтобы было ясно, что является выходом. Сам алгоритм прост, сначала смотрим вокруг и в какой клетке мы были меньше всего раз и идем туда, прибавляя к той, где стояли 1. Так повторяем пока не найдем выход.
Это алгоритм обхода местности. Поиск не оптимален. Фактически поиск ведется по фронту волны. При добавлении эвристики (учет направления до цели), возможно улучшение оптимальности. Главное, что затраты на поиск по времени минимальны!
3. ОСОБЕННОСТИ РАБОТЫ В СРЕДЕ VISUAL C++
Важной вехой в развитии программирования явилось создание и широкое распространение языка С++. Этот язык, сохранив средства ставшего общепризнанным стандартом для написания системных и прикладных программ языка С (процедурно-ориентированный язык), ввел в практику программирования возможности нового технологического подхода к разработке программного обеспечения, получившего название "объектно-ориентированное программирование". Внедрение в практику программирования объектно-ориентированной парадигмы дает развитие новых областей информатики, значительное повышение уровня технологичности создаваемых программных средств, сокращение затрат на разработку и сопровождение программ, их повторное использование, вовлечение в процесс расширения интеллектуальных возможностей ЭВМ. Объектный подход информационного моделирования предметных областей все более успешно применяется в качестве основы для структуризации их информационных отражений и, в частности , баз знаний.
С++ - это язык программирования общего назначения, хорошо известный своей эффективностью, экономичностью, и переносимостью. Указанные преимущества С++ обеспечивают хорошее качество разработки почти любого вида программного продукта. Использование С++ в качестве инструментального языка позволяет получать быстрые и компактные программы. Во многих случаях программы, написанные на С++, сравнимы по скорости с программами, написанными на языке ассемблера.
Перечислим некоторые существенные особенности языка С++:
С++ обеспечивает полный набор операторов структурного программирования;
С++ предлагает необычно большой набор операций. Многие операции С++ соответствуют машинным командам и поэтому допускают прямую трансляцию в машинный код. Разнообразие операций позволяет выбирать их различные наборы для минимизации результирующего кода;
С++ поддерживает указатели на переменные и функции. Указатель на объект программы соответствует машинному адресу этого объекта. Посредством разумного использования указателей можно создавать эффективно выполняемые программы, т.к. указатели позволяют ссылаться на объекты тем же самым путем, как это делает ЭВМ. С++ поддерживает арифметику указателей, и тем самым позволяет осуществлять непосредственный доступ и манипуляции с адресами памяти.
4. ПРОГРАМНАЯ РЕАЛИЗАЦИЯ
.1 Описание алгоритма и структуры программы
В данной программе реализованы 2 метода поиска пути в либиринте, "метод волны" и "метод приоритетов".
Создается массив для хранения лабиринта labirint и массив для прорисовки лабиринта labSet. Генерация лабиринта происходит автоматически. С помощью функции Volna создается массив lb и ряд вспомогательных переменных для вычисления минимального пути, "методом волны", между заданными точками в лабиринтемассив. С помощью функции Prior реализуется "метода приоритетов", там также создается вспомогательная функция lb. В обе эти функции передается адрес исходного лабиринта и количество входов-выходов.
После реализации каждого из методов результат работы этих функций выводится на экран с помощью функции LabOut, в которую передается исходный лабиринт и массив для его прорисовки.
Общий принцип алгоритма волны:
В нашей программе для удобства имена переменных были изменены.
. Снaчaлa необходимо создaть рaбочий мaссив R(MxN),рaвный по рaзмеру мaссиву лабиринта P(MxN).
.Кaжд