Структуры
данных и алгоритмы
Курсовая
работа студента Гридасова А. Ю.
Новосибирский государственный технический университет
Кафедра прикладной математики
Новосибирск
1998
Условие задачи
Имеется
некоторое конечное число городов, которые связаны транспортной сетью, состоящей
из авиа, железнодорожных, автомобильных и водных рейсов произвольного
направления и включающих произвольное число городов. Стоимость проезда различна
по классам. Рейсы отправляются по недельному расписанию. При пересадки между
рейсами должно быть не менее 2-х часов.
По заданным начальному и конечному городам, дате желаемого отправления,
максимальному времени пути и максимальной стоимости и максимальному числу
пересадок выдать все возможные маршруты, так, чтобы маршруты с меньшей датой и
временем прибытия отображались раньше, чем с большим.
Анализ задачи
Транспортная
схема представляет собой направленный взвешенный мультиграф. Каждая дуга характеризуется
принадлежностью к рейсу, временем пути, ценой каждого из классов, временем
отправления.
Входными
данными является:
Транспортная система. (города и все рейсы)
Начальный, конечный город, ориентировочная
дата и время отправления, максимальное время пути максимальная цена,
максимальное количество пересадок.
Причем данные
первой группы изменяются крайне редко и задаются разработчиком транспортной
системы, а данные второй группы изменяются от задачи к задачи и задаются каждым
пользователем.
Результатом
работы программы является конечное множество маршрутов. Два маршрута мы будем
считать различными, если они отличаются хотя бы одним городом следования или
хотя бы одним рейсом. После того, как найдены все маршруты они сортируются по
времени прибытия.
Метод решения –
метод последовательных испытаний. Поиск решений будет осуществляться
рекурсивно, причем максимальная глубина рекурсии будет равна максимальному
количеству пересадок. Так как мы имеем ограничения по некоторым параметрам то
мы можем отсечь заведомо ошибочную ветвь поиска решений, сделав проверку на
превышение параметров. Это позволит выиграть дополнительное время. (о
реализации более подробно п.4)
Выбор и обоснование форм представления данных.
Так как
транспортная система включает в себя достаточно большой объем информации, в
целях доступа к большему объему памяти, также в целях более рационального
использования памяти и по причине недопустимости использования статических
объектов в некоторых случаях, в программе для внутреннего представления широко
используются динамические объекты.
Для объединения
большого количества данных в одном объекте, а также для реализации динамических
объектов используется комбинированный тип (запись).
Для внутреннего
хранения информации о рейсах
используется цепь (однонаправленный список) PFlight с 7-ю информационными полями различных
типов:
Для хранения
названия компании-перевозчика используется тип string[20] так по понятным причинам.
Для хранения
номера рейса используется тип string[10] т.к. в номерах рейса часто используются различные не цифровые
шифры, индексы, коды.
Общее
количество городов – интервальный тип. Автоматическая проверка границ этого
типа повышает надежность программы.
Таблица
отправления представляется своим динамическим типом. Этот динамический тип
представляет совой цепь с одним информационным полем , содержащим время
отправления в минутах от начала недели ( например Вт 17:42 будет записан числом
1*24*60+17*60+42). Такая форма хранения времени сочетает с себе компактность и
легкость пересчета (пересчет требуется только при вводе и выводе, а в программе
в большинстве случаев пересчет не нужен. Динамический тип использован по
причине большого разброса в частоте отправления рейсов (могут быть рейсы,
отправляющиеся каждый день через час, а могут быть рейсы отправляющиеся раз в
неделю).
Маршрут рейса
также представляется своим динамическим типом – однонаправленным динамическим
списком. Причина использования списка аналогична полю отправления -разброс. Так
например самолеты обычно не имеют более 4 посадок, а поезда наоборот делают
много остановок. Информационное поле содержит информацию не об одной а о 4-х станциях, т.е. представляет собой массив
из 4 элементов. Это сделано для экономии памяти на избыточных указателях. При
этом усложнение кода программы незначительно.
Тип транспорта
кодируется числом 1..4. По понятным причинам. Перечислимый тип не был
использован для упрощения ввода данных из внешнего файла.
Классы, которые
предоставляет рейс, представляется в
виде массива индексом является класс, а типом элемента – булевский.
Внутренне
каждый город обозначается своим номером (элемент интервального типа), что
уменьшает расходы памяти и упрощает вычисление. А для хранения названий городов
и их координат для отображения на экране используется свой тип – массив,
элементами которого являются записи с полями для названия города и координат.
Статический массив используется для простого и быстрого доступа к этим данным.
Для хранения
времени пути используется тип Integer. Отрицательные числа нужны для контроля за превышением времени
пути.
Для хранения
цены используется тип LongInt. Причины выбора этого типа очевидны.
Тип Pattern для хранения исходных параметров поиска
представляет собой запись с полями: время отправления относительно понедельника
в минутах, начальный и конечный город, допустимые типы транспорта, допустимые
классы, максимальное количество пересадок, максимальное время пути,
максимальная цена, допустимые классы. Выбор типов для всех полей кроме
«допустимые типы транспорта» обсуждался выше. Для поля «допустимые типы транспорта» выбран массив
где тип индекс – это тип транспорта, а тип элемента – булевский. Это сделано по
причине того что маршрут может включать. Поездки на разных видах транспорта
(тех где в значение true).
Запись использована чтоб передавать все данные единым объектом в процедуру
поиска маршрута.
Тип Link предназначен для хранения информации о
части маршрута между двумя городами, соединенными одним рейсом. Кроме ссылки на
предыдущую такую часть он содержит ссылку на рейс, коды начального и конечного
города, общую цену участка , время отправления, относительно заданного
пользователем время отправления, общее время пути по участку. Типы полей и
обоснования их выбора обсуждались выше. В совокупности цепочка таких элементов
задает один маршрут.
Тип AnswerList предназначен для ответа - множества всех
допустимых маршрутов. Представляет из себя однонаправленный список, в каждом
элементе которого кроме ссылки на следующий имеется поле типа маршрут (Link),
общее время пути, общая максимальная и минимальная цена, количество
пересадок. Типы полей и обоснование
обсуждались выше.
Внешнее
представление:
Транспортная
система хранится во внешнем текстовом файле. Файл может быть создан любым
текстовым редактором. В файле указывается следующее:
Количество
городов. Со следующей строки начинается информация о городах: название города,
на следующей строчке координаты. После всех городов начинается информация о
рейсах: компания, номер, тип, классы, количество станций; номер города, время
пути, время стоянки цена по классам, для каждого города; время отправления от
начальной станции.
Так как эта
информация редактируется крайне редко, причем разработчиком сети, то такой
способ является наиболее приемлемым.
Название
городов вводятся как строки, дата – в
любом формате (дд-мм-гг, дд-мм-гггг,
дд-мес-гг и т.п.) время чч:мм. По умолчанию полагается дата – текущий день,
время 0:00.
Максимальное
время пути, максимальное число пересадок, максимальная цена – вводятся как
числа.
Алгоритм
Begin
{Загрузка транспортной схемы};
{Ввод исходных данных и заполнение шаблона};
{Вызов процедуры поиска с введенным
шаблоном, построенная часть маршрута - пустая};
{Вывод полученного множества маршрутов}
End
{Процедура
поиска маршрута с данным шаблоном и уже построенной частью маршрута}
Begin
While {просмотрены не все рейсы} do begin
If {соответствует тип транспорта} and {Текущий рейс не равен предыдущему}then
Begin
If {город отправления присутствует в рейсе,
причем раньше конечной станции} then begin
{Рассчитать время отправления
ближайшего следующего рейса}
Repeat
{Перейти
к следующему городу};
{Рассчитать время дороги с учетом нового
участка}
If {текущий город еще не проезжали} and {время пути не превышает максимального}
and {количество пересадок не превышает
максимального} and
{не приехали[1]
}
then {Добавить к маршруту проеханный
участок. Вызвать процедуру поиска маршрута
от текущего города до конечного с новыми
значениями времени}
Until {текущий город проезжали} or {время исчерпано} or
{приехали} or
{конец рейса};
If
{приехали} and
{время не превышено} and {минимальная цена рейса не выше
допустимой} then {Добавить построенный маршрут в мно-во
ответов на нужное место}
end;
end;
{Перейти к следующему рейсу}
end;
end
Текст программы на языке
Pascal
uses Crt, Date, Graph;
Const MaxCity=100; MClass=6;
Type
CityCode=1..maxcity; {Внутрений код города}
Week=0..10079; {Тип время в минутак с 0:00 понедельника}
DayTable=^IDayTable; {Таблица отправлений от
начальной станции}
IDayTable=record
Time:Week;
Next:DayTable;
end;
WayKind=1..4; {Тип пути (аэро, море, ж.д, авто)}
WayClass=1..MClass; {Класс или тип перевозки}
Cities=array[CityCode] of {Названия и координаты городов}
record
name:string[20];
x,y:word;
end;
mcost=array[wayclass] of longint;
{Таблица стоимости по классам}
Way=record
City:Citycode;
Delay,Reboard:Word;
Cost:mcost;
end;
WayP=^way;
PWay=^Way1; {Информация о городах следования рейса}
Way1=record
Way:array
[1..4] of way;
next:PWay;
end;
wclass=array
[WayClass] of boolean;
PFlight=^Flight;
Flight=record {Информация о рейсе}
company:string[20];
number:string[10];
totalstation:CityCode;
table:DayTable;
path:PWay;
kind:WayKind;
class:WClass;
next:PFlight;
end;
Blank=record {Шаблон для поиска пути}
delay:Week;
BCity,ECity:CityCode;
Kind:array
[WayKind] of boolean;
ReBoading:CityCode;
WayTime:Integer;
Cost:Longint;
Class:WClass;
end;
Link=^CityList; {Цепочка рейсов для проезда от начала до конца}
CityList=record {Информация о проезде между двумя пунктами одним рейсом}
DDelay:Word;
waytime:word;
cost:mcost;
Bcity,Target:CityCode;
Flight:PFlight;
Last:Link;
end;
AnswerList=^IAnswer; {Список всех возможных
маршрутов следования}
IAnswer=record
path:link;
reboard:citycode;
mincost,maxcost:longint;
waytime:word;
next:AnswerList;
end;
var
Lanswer:AnswerList; {глобальная переменная - начало списка маршрутов }
{Добавления
нового найденного маршрута}
Procedure Answer(A:Link;cost:longint);
var P,Q:Link; d,s1,s2:word; W,PAnswer:answerlist;
r:citycode;
function min(a:mcost):longint;
{Минимальная стоимость по классам}
var i:integer; m:longint;
begin
m:=1000000000;
for i:=1 to
Mclass do if (m>a[i]) and (a[i]>0) then m:=a[i];
min:=m
end;
function max(a:mcost):longint; {Максимальная стоимость по классам}
var i:integer; m:longint;
begin
m:=a[1];
for i:=2 to Mclass do if m=P^.totalStation); {Выходим, если есть нарушения или рейс закончился или
прехали}
If B2 and B1 then
Answer(Npath,pattern.cost); {Если приехали, добавить маршрут в список}
end {найден начальный город}
end; {маршрут подходит по типу}
P:=P^.next; {переход к следущему циклу}
end;
Dispose(NPath)
end;
{Загрузка
исходных данных из файла}
Function Load (A:PFlight; FName:String;var
City:cities):PFlight;
Var
Source:Text;
P:Pflight; I:WayClass; J,MC:CityCode; K:byte;
C:char;
Q:Pway; G,L:DayTable; D:string[8];
Begin
Assign(Source,FName);
Reset(Source);
readln(Source,MC); {Количество городов}
{Считывание название городов и координат
на карте }
For J:=1 to MC do begin
ReadLn(source,City[j].name); readln(source,city[j].x,city[j].y) end;
While Not
EOF(Source) do begin
New(P);
P^.Next:=A;
A:=P;
{Общая информация о рейсе}
ReadLn(Source, P^.company);
ReadLn(Source, P^.number);
ReadLn(Source, P^.kind);
{Стоимость каждого из классов}
For I:=1 to MClass do begin
Read(Source,C); P^.class[i]:=C='X' end;
ReadLn(Source, P^.TotalStation);
New(P^.path);
Q:=P^.path;
{информация о городах следования времени
пути, стоянках}
For J:=1 to P^.TotalSTation do
begin
K:=((J-1)
mod 4)+1;
Read(Source,Q^.Way[K].City,Q^.Way[K].Delay,Q^.Way[K].Reboard);
For I:=1
to MClass do If P^.class[I] then Read(Source,Q^.Way[K].cost[I])
else
Q^.Way[K].cost[I]:=0;
If (J mod
4)=0 then begin
If
(JP^.TotalStation) then begin New(Q^.Next); Q:=Q^.next end
else
Q^.next:=nil;
end;
ReadLn(Source);
end;
New(P^.Table);
G:=P^.Table;
L:=G;
{Информация о отправлении из начального
пункта}
While Not EOLn(Source) do begin
Read(Source,D);
G^.Time:=(ord(D[1])-ord('0')-1)*1440+((ord(D[3])-ord('0'))*10+ord(D[4])-ord('0'))*60
+(ord(D[6])-ord('0'))*10+ord(D[7])-ord('0');
if
L^.time>G^.time then write('Wrong data');
If not
EOLn(Source) then begin New(G^.next); G:=G^.next end else G^.next:=nil;
end;
ReadLn(Source);
end;
Load:=A;
end;
const
line='--------------------------------------------------------------------------------';
procedure graphout(const city:cities);
var
grDriver:
Integer;
grMode:
Integer;
p:citycode;
begin
grDriver :=
Detect;
InitGraph(grDriver, grMode,'');
setcolor(12);
outtextxy(200,0,'Карта транспортной схемы');
p:=1;
while
(p