Структуры даних, і алгоритми

Структуры даних, і алгоритмы

Курсовая робота студента Гридасова А. Ю.

Новосибирский державний технічний университет

Кафедра прикладної математики

Новосибирск

1998

Условие задачи.

Имеется деяке кінцеве число міст, пов’язані транспортної мережею, яка перебуває з авіа, залізничних, автомобільних і водяних рейсів довільного напряму, і які включають довільне число міст. Вартість проїзду різна за класами. Рейси вирушають по тижневої розкладу. При пересадки між рейсами має не меншим 2-х годин. По заданим початковому і кінцевому містам, дати бажаного відправлення, максимальному часу шляху й максимальної вартості і максимальної кількості пересадок видати всіх можливих маршрути, те щоб маршрути з не меншою датою і часом прибуття відображалися раніше, ніж із большим.

Анализ задачи.

Транспортная схема є спрямований зважений мультиграф. Кожна дуга характеризується приналежністю до рейсу, часом шляху, ціною кожного з класів, часом відправлення.

Входными даними является:

Транспортная система. (міст і всі рейсы).

Початковий, кінцевий місто, орієнтовна дата та палестинці час відправлення, максимальне час шляху максимальна ціна, якомога більше пересадок.

Причем дані першої групи змінюються дуже рідко і визначають розробником транспортної системи, а дані другої групи змінюються від завдання до завдання й задаються кожним пользователем.

Результатом роботи програми є кінцеве безліч маршрутів. Два маршруту ми вважати різними, якщо вони різняться хоча б містом прямування чи хоча б рейсом. Потому, як знайдено все маршрути вони сортуються по часу прибытия.

Метод рішення — метод послідовних випробувань. Пошук рішень здійснюватиметься рекурсивно, причому максимальна глибина рекурсії дорівнюватиме максимальному кількості пересадок. Оскільки маємо обмеження з деяким параметрами то ми можемо відсікти явно помилкову гілка пошуку рішень, зробивши перевірку на перевищення параметрів. Це дозволить виграти додаткового часу. (про реалізації докладніше п.4).

Выбор та обґрунтування форм уявлення данных..

Так як транспортна система включає у собі досить великий обсяг інформації, в цілях доступу більшого обсягу пам’яті, й у цілях раціональнішого використання пам’яті також тому неприпустимість використання статичних об'єктів деяких випадках, у програмі для внутрішнього уявлення широко використовуються динамічні объекты.

Для об'єднання великої кількості даних щодо одного об'єкті, і навіть для реалізації динамічних об'єктів використовується комбінований тип (запись).

Для внутрішнього зберігання інформації про рейсах використовується ланцюг (односпрямований список) PFlight з 7-му інформаційними полями різних типов:

Для зберігання назви компанії-перевізника використовується тип string[20] як за зрозумілим причинам.

Для зберігання номери рейсу використовується тип string[10] т.к. в номерах рейсу часто використовуються різні не цифрові шифри, індекси, коди.

Общее кількість міст — интервальный тип. Автоматична перевірка кордонів цього типу підвищує надійність программы.

Таблица відправлення представляється своїм динамічним типом. Цей динамічний тип представляє совою ланцюг з однією інформаційним полем, що містить час відправлення в хвилинах початку тижня (наприклад Вт 17:42 буде записано числом 1*24*60+17*60+42). Така форма зберігання часу поєднує з компактність і легкість перерахунку (перерахунок потрібно лише за введення і виведення, а програмі здебільшого перерахунок непотрібен. Динамічний тип використаний по причини великого розкиду в частоті відправлення рейсів (може бути рейси, які вирушають щодня за годину, а може бути рейси які вирушають разів у неделю).

Маршрут рейсу також представляється своїм динамічним типом — однонаправленим динамічним списком. Причина використання списку аналогічна полю відправленнярозкид. Так наприклад літаки звичайно мають більше чотирьох посадок, а поїзда навпаки роблять багато зупинок. Інформаційне полі містить інформацію не одну йдеться про 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.10 079; {Тип час у минутак з 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:=1 000 000 000;

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.