Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.abitu.ru/en2002/closed/viewwork.html?thesises=66 Дата изменения: Fri May 5 15:24:57 2006 Дата индексирования: Tue Oct 2 03:04:51 2012 Кодировка: koi8-r

Тезисы работы
Основной целью этой работы была задача моделирования движения
транспортного средства с заданной грузоподъемностью по местности, которая
задается графом. В процессе выполнения работы изучена теория графов:
понятия графа, ребер и вершин, понятие ориентированный и неориентированный
граф, петля, цепь, маршрут, понятие связности, понятие Эйлерова графа и
Эйлерова цикла, понятие Гамильтонова графа и Гамильтонова цикла.
Данная задача относится к классу транспортных задач. Для решения таких
задач можно использовать: алгоритм Дейкстры, алгоритм Флойда, алгоритм
Уоршалла, волновой алгоритм, алгоритм Прима-Краскалла (проверить), алгоритм
Мальгранжа.
Особенностью рассматриваемой задачи является то, что решением является
конечное количество оптимальных маршрутов, длина которых минимальна и
включают все вершины графа.
В задаче использованы алгоритм Дейкстры для нахождения всех кратчайших
путей для указанной вершины графа к остальным, и волновой алгоритм для
проверки связности пары вершин.
Ограничения:
. Число вершин обрабатываемого графа не может превышать 65535. В противном
случае пользователь получит соответствующее сообщение.
. Граф может быть так же орграфом (для орграфа допустимо, что AB?BA, где A
и B - две различные вершины графа).
. Обрабатываемый граф не может содержать петель, т.е. ребра, для которых
конечная и начальная вершины совпадают, не допустимы.
Для программной реализации использован объектно-ориентированный подход.
Граф и результирующий список определены как объекты. Для них были
определены поля, определяющие структуру объекта, и методы, позволяющие
управлять этими структурами.
Для объекта граф определены методы инициализации графа, добавления вершин,
удаления вершин, проверки связности вершины, возврат веса ребра, которое
соединяет пару вершин графа.
Для объекта результирующего списка определены методы создания списка,
добавления и удаления элемента, удаления списка.
Для реализации интерфейса программы была использована среда разработки
Borland Delphi 5.0. В интерфейсе использованы формы, в которых содержатся
кнопки, горизонтальное меню приложения, панели, объекты Image, надписи,
рабочая область, переключатели, флажки, поля ввода, текстовые поля,
диалоги.
Используя объектно-ориентрованный подход к разработке приложения, удалось
достичь наглядности и удобства пользовательского интерфейса. Помимо этого
были освоены особенности наследования классов (объектов), механизм
взаимодействия между ними, область действия объектов, их полей и методов.
Объектно-ориентированный подход к разработке позволил повысить абстракцию
программы и работать с экземпляром класса как с черным ящиком, зная только
его интерфейсную часть.
Приложение можно использовать для расчета оптимального пути движения
автомобиля, с ограниченной грузоподъемностью, по городу с целью сбора и
доставки однородных объектов из заданного пункта в определенную
пользователем конечную точку. Транспортным средством может быть городской
мусоросборник, грузовой автомобиль, объезжающий сеть городов.
Дальнейшей модификацией программы будет возможность загрузки графического
изображения как фоновый рисунок, являющийся схемой некоторой местности, для
наглядного и точного задания графа.
Разбиение единого процесса вычисления на несколько с целью повышения
полезного действия многопроцессорных станций.
Печать маршрутных листов в виде, приближенном к документации предприятия.
Визуализация процесса обхода на графе.