Использование теории графов для решения задач. Информационные структуры входных и выходных данных. Иерархическая схема программы. Руководство оператора: назначение и условия выполнения программы. Граф-схема FormCreate, Found, RassUpdate и Search.
Аннотация к работе
Данная программа позволяет находить маршруты между двумя точками города для перевозки пассажиров такси. Найденные маршруты выводятся для просмотра в текстовом поле с возможностью сохранения в отдельный файл.Требуется находить все возможные варианты перевозки пассажиров из одной точки в другую (возможно, через промежуточные точки) и рассчитывать стоимость перевозки.V - множество вершин графа (каждая вершина соответствует одному пункту); E - множество ребер графа (каждое ребро соответствует одному маршруту). Множество вершин графа представлено в формуле (2.2): V={V1:Авангардная 1:, V2:Буммашевская 3, V3:Ворошилова 14, V4:Гагарина 1, V5:М.Горького 2, V6: Орженикидзе 17, V7:Пушкинская 1, V8:Удмуртская 255, V9:Холмогорова 5,…, Vn} (2.2) где Ei j - ребро графа, соединяющее i-ую и j-ую вершины. Если нет прямого пути от вершины Vi до вершины Vj, то происходит переход на вершину Vk, смежную с вершиной Vi и еще не содержащуюся в пути, и ищется путь от вершины Vk до вершины Vj.Схема данных представлена на рис. Типизированный файл puti.dat - список маршрутов, по каждому из маршрутов указывается наименования пунктов, которые соединяет этот маршрут, стоимость перевозки и максимальный пассажиропоток маршрута. Пользовательские данные содержат наименование пункта отправления и пункта прибытия, а так же максимальное количество пассажиров. Типы: TPATH - маршрут (record). t1,t2 - название пунктов, которые соединяют маршрут. p1, p2 - порядковые номера пунктов, которые соединяет этот маршрут (byte). cost - стоимость маршрута (word). traf - количество пассажиров (word). Переменные: f1 - входной текстовый файл со списком пунктов (textfile). f2 - входной типизированный файл со списком маршрутов (file of tpath). colp - количество маршрутов (byte). colt - количество пунктов (byte). colw - количество найденных маршрутов (word). towns - массив пунктов (array of string). paths - массив доступных маршрутов (array of tpath). rel - динамический двумерный массив сопоставлений пунктов соседним пунктам (array of array of byte).Иерархическая схема программы представлена на рис. Спецификация: 1) Search - Проверяются все соседние пункты (рекурсивно), игнорируются пункты, которые уже встречались,при нахождении конечного пункта вызывается процедура Found. 2) Found - добавляется маршрут в таблицу,рассчитывается стоимость маршрута,увеличивается счетчик найденных маршрутов на единицу. 4) Button1Click - Открывается редактор пунктов,в котором можно добавить или удалить пункт.В ходе курсовой работы был создан программный продукт, удовлетворяющий всем поставленным задачам.Программа предназначена для поиска всех возможных маршрутов из одного пункта города в другой. Выбор исходного и конечного пунктов происходит одним из следующих способов: 1) выбор пунктов из предложенного программой списка. После этого программа проверяет возможно ли совершить выбранный маршрут. Программа разработана для операционных систем семейства Windows версии не ниже чем XP. В главном меню программы пользователь должен выбрать пункт отправления и пункт прибытия из предложенного списка, а также ввести количество человек, перевозимых за раз (рис.Граф-схема проц-ры FORMCREATE Граф-схема проц-ры Found Граф-схема проц-ры Button4Click Граф-схема проц-ры Button2Clickprocedure Found(way:string); COMBOBOX2.Items.Add(towns[i]) end; procedure TFORM1.Search(fin:byte;way:string); begin t:=Ord(way[length(way)]); If ((paths[k].p1=Ord(way[i]) 1) and (paths[k].p2=Ord(way[i 1]) 1)) or ((paths[k].p2=Ord(way[i]) 1) and (paths[k].p1=Ord(way[i 1]) 1)) then sum:=sum paths[k].cost*(((UPDOWN1.Position-1) div paths[k].
Вывод
В ходе курсовой работы был создан программный продукт, удовлетворяющий всем поставленным задачам. В результате использования языка Delphi, данный программный продукт легко расширяем и модифицируем.
В дальнейшем полученная программа может быть модифицирована с добавлением функции поиска самого быстрого или дешевого маршрута.
При выполнении работы частично была изучена теория графов, алгоритм поиска в глубину и язык программирования Delphi.
Список литературы
1. Силкин К.Ю. «Геоинформационная система Golden Software Surfer 8: Учебно-методическое пособие для вузов» - Воронеж, 2008. - 66 с.
2. Капралов Е.Г., Кошкарев А.В., Тикунов В.С. и др. «Геоинформатика: Учеб. для студ. Вузов» / Под ред. Тикунова В.С. - М: Издательский центр «Академия», 2005. - 480 с.