Visual Basic нахождение кратчайшего пути курсовая

  • 07 апр. 2011 г.
  • 3982 Слова
СОДЕРЖАНИЕ:

Введение 3
1 Постановка задачи 5
2 Обзор алгоритмов нахождения кратчайшего пути……………………6
3 Обзор средств программирования, использованных при
разработке проекта 15
4 Разработка интерфеса приложения 17
5 Описние и структура программных модулей 20
6 Режим работы программы…………………………………………..…33
Заключение ..36
Списоклитературы 37

ВВЕДЕНИЕ

В нашем динамичном и подчас очень сложном мире незнание своего местонахождения является непозволительной роскошью. Задача позиционирования человека в пространстве стара как мир, - были изобретены компас, навигация по звездам, и много других способов, сменявших друг друга с течением развития цивилизации. В наши дни определить свое местоположение достаточно легко. Составленыподробные карты и планы поверхности земли, практически весь земной шар сфотографирован из космоса. Благодаря стараниям различных организаций, теперь каждый человек на планете способен рассмотреть любой ее уголок и представить, что в нем находится.
Но, несмотря на улучшившуюся ситуацию с позиционированием человека на местности, проблем, недоработок и просто белых пятен на карте все еще много.Навигационные системы используют различные технологии и наиболее продвинутой из них является спутниковая GPS навигация. Определение своего положения с помощью этой технологии является достаточно точным практически для всех жизненных ситуаций, но имеются и ограничения. Главное из них то, что сигнал спутника не способен проникнуть в здания и под землю. В таком случае в дело вступаютлокальные системы позиционирования.
Несмотря на большую популярность GPS навигаторов, алгоритмы, которые они используют в своей работе, не столь хорошо известны. Попробуем описать некоторые из них.
Среди всех алгоритмов, отвечающих за работу спутниковых навигаторов, ярко выделяются два. Первый позволяет определить положение приемника по сигналам со спутников GPS, второй определяет кратчайший путьиз точки А (в которой Вы находитесь) в точку Б (в которую Вы желаете попасть). Существуют и другие алгоритмы, определяющие в основном визуальное отображение маршрута, но первые два являются наиболее важными.
Целью данного курсового проекта является изучение алгоритмов нахождения кратчайшего мути между двумя заданными точками А и В и реализация одного из них.

ПОСТАНОВКА ЗАДАЧИОбозначим основные задачи, которые были поставлены для реализации данного курсового проекта:
➢ изучение методов поиска кратчайшего пути;
➢ определить оптимальный метод для конкретного случая;
➢ разработать приложение в среде программирования Visual Basic 6.0, которое будет определять кратчайший путь между двумя заданными точками.

Требования к проекту:▪ прорисовка поля с препятствиями;
▪ препятствия формируются случайным образом;
▪ возможность изменения размерности поля;
▪ возможность выбора начальной и конечной точки пути;
▪ вывод оптимального количества полей между заданными точками.

2 ОБЗОР АЛГОРИТМОВ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ

Хотя поиск пути не тривиальная задача, существуетнесколько хороших, надежных алгоритмов, которые заслуживают большей известности в сообществе разработчиков.
Некоторые алгоритмы поиска пути не очень эффективны, но их изучение позволяет постепенно вводить концепции. Так можно понять, как решаются различные проблемы.
Типичной проблемой в поиске пути является обход препятствий. Наипростейшим подходом к проблеме является игнорированиепрепятствий до столкновения с ними. Такой алгоритм будет выглядеть примерно так:
Пока не цель не достигнута
Выбрать направление для движения к цели
Если это направление свободно для движения
Двигаться туда
Иначе
Выбрать другое направление в
соответсвии со стратегией обхода

Этот подход прост, так как он предъявляет совсем немного требований: все, что...