Рефераты Задача про транспортную систему. Подбор вариантов проезда с учетом кол-ва пересадо, длительности, видов транспорта (самолет, авто, поезд, водн.) и класса.

Вернуться в Остальное

Задача про транспортную систему. Подбор вариантов проезда с учетом кол-ва пересадо, длительности, видов транспорта (самолет, авто, поезд, водн.) и класса.
Новосибирский государственный технический университетКафедра прикладной математикиКурсовая работа по дисциплине "Структуры данных и алгоритмы" Факультет: ПМИГруппа: ПМ-71Студент: Гридасов А. Ю.Руководитель: Карманов В. С.Дата защиты: 15.05.98Новосибирск1998ОглавлениеОглавление 11. Условие задачи 32. Анализ задачи 33. Выбор и обоснование форм представления данных. 34. Алгоритм 45. Текст программы на языке Pascal 56. Выбор и обоснование набора тестов 127. Анализ результатов 148. Литература 149. Приложение 15 1. Условие задачиИмеется некоторое конечное число городов, которые связаны транспортной сетью, состоящей из авиа, железнодорожных, автомобильных и водных рейсов произвольного направления и включающих произвольное число городов. Стоимость проезда различна по классам. Рейсы отправляются по недельному расписанию. При пересадки между рейсами должно быть не менее 2-х часов. По заданным начальному и конечному городам, дате желаемого отправления, максимальному времени пути и максимальной стоимости и максимальному числу пересадок выдать все возможные маршруты, так, чтобы маршруты с меньшей датой и временем прибытия отображались раньше, чем с большим.2. Анализ задачи Транспортная схема представляет собой направленный взвешенный мультиграф. Каждая дуга характеризуется принадлежностью к рейсу, временем пути, ценой каждого из классов, временем отправления. Входными данными является:a) Транспортная система. (города и все рейсы)b) Начальный, конечный город, ориентировочная дата и время отправления, максимальное время пути максимальная цена, максимальное количество пересадок.Причем данные первой группы изменяются крайне редко и задаются разработчиком транспортной системы, а данные второй группы изменяются от задачи к задачи и задаются каждым пользователем.Результатом работы программы является конечное множество маршрутов. Два маршрута мы будем считать различными, если они отличаются хотя бы одним городом следования или хотя бы одним рейсом. После того, как найдены все маршруты они сортируются по времени прибытия.Метод решения - метод последовательных испытаний. Поиск решений будет осуществляться рекурсивно, причем максимальная глубина рекурсии будет равна максимальному количеству пересадок. Так как мы имеем ограничения по некоторым параметрам то мы можем отсечь заведомо ошибочную ветвь поиска решений, сделав проверку на превышение параметров. Это позволит выиграть дополнительное время. (о реализации более подробно п.4)3. Выбор и обоснование форм представления данных.Так как транспортная система включает в себя достаточно большой объем информации, в целях доступа к большему объему памяти, также в целях более рационального использования памяти и по причине недопустимости использования статических объектов в некоторых случаях, в программе для внутреннего представления широко используются динамические объекты.Для объединения большого количества данных в одном объекте, а также для реализации динамических объектов используется комбинированный тип (запись).Для внутреннего хранения информации о рейсах используется цепь (однонаправленный список) PFlight с 7-ю информационными полями различных типов:1) Для хранения названия компании-перевозчика используется тип string[20] так по понятным причинам.2) Для хранения номера рейса используется тип string[10] т.к. в номерах рейса часто используются различные не цифровые шифры, индексы, коды. 3) Общее количество городов - интервальный тип. Автоматическая проверка границ этого типа повышает надежность программы.4) Таблица отправления представляется своим динамическим типом. Этот динамический тип представляет совой цепь с одним информационным полем , содержащим время отправления в минутах от начала недели ( например Вт 17:42 будет записан числом 1*24*60+17*60+42). Такая форма хранения времени сочетает с себе компактность и легкость пересчета (пересчет требуется только при вводе и выводе, а в программе в большинстве случаев пересчет не нужен. Динамический тип использован по причине большого разброса в частоте отправления рейсов (могут быть рейсы, отправляющиеся каждый день через час, а могут быть рейсы отправляющиеся раз в неделю)
Добавить в Одноклассники    

 

Rambler's Top100