Алгоритми на графах Найкоротші відстані на графах

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Міністерство освіти Республіки Білорусь
Установа освіти
"Гомельський державний університет ім. Ф. Скорини"
Математичний факультет
Кафедра МПУ
Алгоритми на графах. Пошук в глибину
Курсова робота
Виконавець:
Студентка групи М-43 Полякова О.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент Звєрєва Т.Є.
Гомель 2006

Зміст
Введення
1 Пошук в глибину
2 Завдання "Дороги"
3 Задача "Перехрестя"
4 Завдання "Скрудж Мак-Дак"
Висновок
Література

Введення

Перш за все, кілька слів про те, як виникає поняття графа з природних умов завдань. Наведемо кілька прикладів.
Нехай ми маємо карту доріг, в якій для кожного міста вказано відстань до всіх сусідніх з ним. Тут два міста називаються сусідніми, якщо існує дорога, що сполучає безпосередньо ці два міста.
Аналогічно, можна розглянути вулиці і перехрестя всередині одного міста. Зауважимо, що можуть бути вулиці з одностороннім рухом.
Мережа комп'ютерів, з'єднаних провідними лініями зв'язку.
Набір слів, кожне з яких починається на певну букву і закінчується на цю ж або іншу літеру.
Безліч кісток доміно. Кожна кістка має 2 числа: ліву і праву половину кістки.
Пристрій, що складається з мікросхем, з'єднаних один з одним наборами провідників.
Генеалогічні дерева, що вказують родинні стосунки між людьми.
І, нарешті, власне графи, що вказують відносини між якими або абстрактними поняттями, наприклад, числами.
Отже, неформально, граф можна визначити як набір вершин (міста, перехрестя, комп'ютери, літери, цифри кістки доміно, мікросхеми, люди) і зв'язків між ними: дороги між містами; вулиці між перехрестями; провідні лінії зв'язку між комп'ютерами; слова, що починаються на одну букву і закачується на іншу або цю ж літеру; провідники, що з'єднують мікросхеми; родинні стосунки, наприклад, Олексій - син Петра. Двонапрямлені зв'язку, наприклад, дороги з двостороннім рухом, прийнято називати ребрами графа; а односпрямовані зв'язку, наприклад, дороги з одностороннім рухом, прийнято називати дугами графа. Граф, у якому вершини з'єднуються ребрами, прийнято називати неорієнтованим графом, а граф, в якому хоча б деякі вершини з'єднуються дугами, прийнято називати орієнтованим графом.

1. Пошук в глибину

Нижче наведено приклад неорієнтованого графа з шістьма вершинами.

При комп'ютерній обробці граф може задаватися списком ребер (дуг) для кожної вершини. Наприклад, для графа, наведеного на прикладі, цей список виглядає так

Для зберігання цієї інформації в пам'яті комп'ютера можна скористатися двовимірним масивом G [1 .. N, 1 .. M], де N - кількість вершин у графі, M - максимально можливе число ребер (дуг) в однієї вершини графа. Для зручності обробки цієї інформації можна також мати одновимірний масив kG [1 .. N] - кількості ребер (дуг) вершин графа.
Тоді для обробки списку зв'язків поточної вершини U можна написати
for i: = 1 to kG [U]
begin
V: = G [U, i];
end;

Тим самим, ми отримуємо обробку дуги, яка зв'язує вершини U і V для всіх вершин, безпосередньо пов'язаних з U.
Для обробки ВСІХ зв'язків усіх вершин можна використовувати пошук в глибину (DFS - Depth-First Search):
for U: = 1 to N do Color [U]: = WHITE;
for U: = 1 to N do
if color [U] = WHITE then DFS (U);
Procedure DFS (U: longint);
var
j: longint;
begin
color [U]: = GRAY;
for j: = 1 to kG [U] do DFS (G [U, j]);
end;
Тут
Color [U] = колір вершини
WHITE (константа = 1) - білий, якщо ми ще не відвідували цю вершину
GRAY (константа = 2) - сірий, якщо ми відвідували дану вершину
DFS (U) - рекурсивна процедура, яка викликає себе для всіх вершин, нащадків даної вершини.
Тобто, для забезпечення пошуку в глибину на заданому графі G [1 .. N, 1 .. M] з кількостями дуг з вершин G [1 .. N], спочатку ми встановлюємо всім вершин колір WHITE, а потім для всіх вершин, які ще не відвідувалися (Color [G [U, j]] = WHITE) викликаємо рекурсивну процедуру DFS.
Таким способом формуються всі можливі маршрути в графі. При цьому немає обмежень на кількість разів використання дуг і заходів у вершини.
Якщо ж за умовами завдання буде потрібно відвідувати кожну вершину не більше одного разу, щоб формувати маршрути з незбіжних вершин, то це може бути забезпечено в процедурі DFS умовним викликом:
Procedure DFS (U: longint);
var
j: longint;
begin
color [U]: = GRAY;
for j: = 1 to kG [U] do
if color [G [U, j]] = WHITE then DFS (G [U, j]);
end;
Якщо за умовами задачі потрібно кожну дугу використовувати не більше одного разу, то можна ввести забарвлення дуг:
Color [1 .. N, 1 .. M] - зі значеннями FREE або DONE де, як і раніше
N - кількість вершин у графі,
M - максимально можливе число ребер (дуг) в однієї вершини графа.
А процедура DFS формування маршрутів так, що б кожна дуга використовувалася в маршруті не більше одного разу, буде виглядати наступним чином:
procedure DFS (v: byte);
var j: byte;
begin
for j: = 1 to kG [v] do
if (color [v, j] = FREE)
then
begin
color [v, j]: = DONE;
DFS (G [v, j]);
color [v, j]: = FREE;
end;
end;
Тут вводяться позначки на дуги
Color [v, j] = FREE,
якщо дуга ще не оброблена, і DONE, якщо вона включена в поточний шлях.
Якщо в задачі потрібно вивести знайдений шлях, то для його зберігання заводиться спеціальний масив SLED [1 .. Q], де Q - максимальна кількість ребер у дорозі і вершини поточного шляху заносяться в цей масив і видаляються з нього в процесі обходу графа:
procedure DFS (v: byte);
var j: byte;
begin
for j: = 1 to kG [v] do
begin
inc (ks); sled [ks]: = G [v, j];
DFS (G [v, j]);
dec (ks);
end;
end;
Наведена теоретична інформація ілюструється далі прикладами рішення конкретних завдань.

2 Завдання "Дороги"

Республіканська олімпіада з інформатики 1997
Дана система односторонніх доріг, обумовлена ​​набором пар міст. Кожна така пара (i, j) вказує, що з міста i можна проїхати в місто j, але це не означає, що можна проїхати в зворотному напрямку.
Необхідно визначити, чи можна проїхати з заданого міста А в заданий місто У таким чином, щоб відвідати місто С і не проїжджати ні по якій дорозі більше одного разу.
Вхідні дані задаються у файлі з ім'ям PATH.IN наступним чином. У першому рядку знаходиться натуральне N (N <= 50) - кількість міст (міста нумеруються від 1 до N). У другому рядку знаходиться натуральне M (M <= 100) - кількість доріг. Далі в кожному рядку знаходиться пара номерів міст, які пов'язує дорога. В останній (M +3)-му рядку знаходяться номери міст А, В і С.
Відповіддю є послідовність міст, що починається містом А і закінчується містом В, що задовольняє умовам задачі, який повинен бути записаний у файл PATH.OUT у вигляді послідовності номерів міст по одному номеру в рядку. Перший рядок файлу повинна містити кількість міст в послідовності. При відсутності шляху записати в перший рядок файлу число -1.


Коротко ідея рішення може бути викладена наступним чином:
Пошук в глибину.
Якщо зустрічаємо вершину B, встановлюємо відповідний прапор.
Якщо зустрічаємо вершину C і прапор B встановлено - виводимо результат і завершуємо роботу.
Після завершення пошуку (потрібного маршрут не знайдено) виводимо -1.
Викладемо рішення більш докладно.
Введення вихідних даних здійснюється наступним чином:
read (N, M);
for i: = 1 to M do
begin
read (x, y); inc (kG [x]); G [x, kG [x]]: = y; color [x, kG [x]]: = FREE;
end;
read (A, B, C);
Тут, як і колись,
kG [i] - кількість дуг з вершини i
G [i, j] - (для j від 1 до kG [j]) - вершини, з якими вершина i пов'язана відповідної дугою
Крім того, введений колір дуги FREE - вільна (DONE - зайнята, FREE / DONE - константи)
Головна програма фактично включає тільки наступні оператори:
LabC: = 0; {Встановити мітку - вершину C ще не відвідували}
DFS (A); {Пошук в глибину від вершини A}
writeln (-1); {Висновок ознаки відсутності необхідного шляху}

Рекурсивна процедура пошуку в глибину від вершини V виглядає наступним чином:
procedure DFS (v: byte);
var j: byte;
begin
for j: = 1 to kG [v] do
if (color [v, j] = FREE)
then
begin
if (G [v, j] = B) and (LabC = 1)
then begin OutRes; halt; end;
if G [v, j] = C then LabC: = 1;
color [v, j]: = DONE; inc (ks); sled [ks]: = G [v, j];
DFS (G [v, j]);
color [v, j]: = FREE; sled [ks]: = 0; dec (ks);
if G [v, j] = C then LabC: = 0;
end;
end;
Тобто для всіх ще необроблених (color [v, j] = FREE) дуг від поточної вершини з'ясовуємо - якщо вона веде в кінцевий пункт, а місто C вже проходили - виклик процедури виведення результату і останов.
Якщо поточна дуга веде в місто С, встановлюємо відповідну позначку (LabC = 1).
Позначаємо дугу як оброблену, заносимо її в масив SLED, який містить поточний оброблюваний шлях, KS - кількість елементів у ньому.
Викликаємо процедуру DFS від вершини (G [v, j]), в яку ведуть поточна дуга.
Перед виходом із процедури DFS відновлюємо стан, "початкове" перед її викликом: знімаємо позначку обробки з дуги (color [v, j]: = FREE), видаляємо її з масиву SLED (dec (ks), оператор sled [ks]: = 0; робити необов'язково, але він надає зручності налагодження - що б у масcіве SLED ненульовими були тільки реально входять в дорогу елементи).
І, нарешті, процедура виведення результату:
procedure OutRes;
begin
writeln (ks +2);
writeln (A); for i: = 1 to ks do writeln (sled [i]); writeln (B);
end;
Оскільки за алгоритмом побудови початковий (A) і кінцевий (B) міста не заносилися в масив SLED, то вони виводяться окремо, а кількість міст в дорозі (KS) перед виведенням збільшується на 2.
Повний текст програми наводиться нижче.
program by97d2s3;
const
FREE = 1;
DONE = 2;
var
G, color: array [1 .. 50,1 .. 100] of byte;
D: array [1 .. 50] of longint;
kG, sled: array [1 .. 50] of byte;
path: array [1 .. 100] of byte;
MinD, is: longint;
i, j, x, y, A, B, C, N, M, ks, LabC: byte;
Yes: boolean;
procedure OutRes;
begin
writeln (ks +2);
writeln (A); for i: = 1 to ks do writeln (sled [i]); writeln (B);
end;
procedure DFS (v: byte);
var j: byte;
begin
for j: = 1 to kG [v] do
if (color [v, j] = FREE)
then
begin
if (G [v, j] = B) and (LabC = 1)
then begin OutRes; halt; end;
if G [v, j] = C then LabC: = 1;
color [v, j]: = DONE; inc (ks); sled [ks]: = G [v, j];
DFS (G [v, j]);
color [v, j]: = FREE; sled [ks]: = 0; dec (ks);
if G [v, j] = C then LabC: = 0;
end;
end;
begin
assign (input, 'path.in'); reset (input);
assign (output, 'path.out'); rewrite (output);
read (N, M);
for i: = 1 to M do
begin
read (x, y); inc (kG [x]); G [x, kG [x]]: = y; color [x, kG [x]]: = FREE;
end;
read (A, B, C);
LabC: = 0;
DFS (A);
writeln (-1);
close (input); close (output);
end.

3 Задача "Перехрестя"

(Автор - Котов В.М.)
Республіканська олімпіада з інформатики 1998
Дано декартові координати N перехресть міста, які пронумеровані від 1 до N. На кожному перехресті є світлофор. Деякі з перехресть з'єднані дорогами з двостороннім (правостороннім) рухом, які перетинаються тільки на перехрестях. Для кожної дороги відомо час, що потрібно для проїзду по ній від одного перехрестя до іншого.
Необхідно проїхати від перехрестя з номером А до перехрестя з номером В за мінімальний час.
Час проїзду залежить від набору проїжджаємо доріг і від часу очікування на перехрестях. Так, якщо ви під'їхали від перехрестя X до перехрестя C по дорозі Х-> C і хочете їхати далі по дорозі C-> У, то час очікування на перехресті C еавісіт від того, повертаєте ви наліво чи ні. Якщо ви повертаєте наліво, то час очікування одно D * К, де D дорівнює кількості доріг, що перетинаються на перехресті C, а К - деяка константа. Якщо ви не повертаєте наліво, то час очікування дорівнює нулю.
Написати програму, яка визначає найшвидший маршрут.
Специфікація вхідних даних.
Вхідні дані знаходяться у текстовому файлі з ім'ям PER.IN і мають наступну структуру:
- У першому рядку знаходиться число N (натуральне, <= 1000);
- У другому рядку - кількість доріг M (натуральне, <= 1000);
- В третьому рядку - константа K (натуральне число, <= 1000);
- В кожній з N наступних стpок знаходиться паpа чисел х і у, розділених пробілом, де x, y - кооpдінати перехрестя (цілі числа, не перевищувати за модулем 1000);
- В кожній з M наступних рядків знаходиться 3 числа p, r, t, розділені пробілом, де p і r - номери перехресть, які з'єднує дорога, а t (натуральне, <= 1000) - час проїзду по ній;
- В останньому рядку знаходяться номери початкового А і кінцевого У перехресть.
Специфікація вихідних даних.
Вихідні дані повинні бути записані в текстовий файл з ім'ям PER.OUT і мати наступний формат:
- У першому рядку знаходиться натуральне число T - час проїзду по найшвидшому маршруту;
- У кожній з наступних рядків знаходиться одне число - номер чергового перетину маршруті (починаючи з перехрещення з номером А і закінчуючи В).
Коротко ідея рішення може бути викладена наступним чином.
Алгоритм Дейкстри безпосередньо не застосуємо, оскільки:
а) оптимальне рішення в наступної вершини не є сумою оптимального рішення для попередньої вершини і ваги поточного ребра
б) вагу поточного ребра - непостійна величина, що залежить від того, яким поворотом ми вийшли з вершини.
Тому пропонується рішення пошуком в глибину. При цьому дозволяється використовувати кожну вершину стільки разів, скільки у неї є ребер. Відсікаються рішення гірше поточного оптимального.
Можна ще прискорити рішення, якщо забезпечувати перебір, починаючи з правих поворотів (відсікання працювали б більш ефективно).
Зауваження:
У тексті задачі явно не вказано, але автори оригінальних тестів до завдання вважали, що поворот на 180 градусів - це лівий поворот (як в армії: поворот на 180 градусів - "через ліве плече").
Розглянемо рішення більш докладно:
Введення вихідних даних здійснюється наступним чином:
read (N, M, K);
for i: = 1 to N do readln (x [i], y [i]);
for i: = 1 to N do begin kG [i]: = 0; D [i]: = 0; end;
for i: = 1 to M do
begin
readln (p, r, t); inc (kG [p]); inc (kG [r]);
G [p, kG [p], 1]: = r; G [p, kG [p], 2]: = t; inc (D [p]);
G [r, kG [r], 1]: = p; G [r, kG [r], 2]: = t; Inc (D [r]);
end;
readln (vA, vB);
Тут kG [i] - кількість дуг з вершини i
G [i, j, 1] - вершина, з якої сполучена вершина i дугою з номером j у списку всіх дуг із вершини i.
G [i, j, 2] - час проїзду від вершини i до вершини, з якою вона з'єднана дугою j у списку всіх дуг із вершини i.
D [i] - кількість доріг, що перетинаються на перехресті i (тобто сумарна кількість дуг, що виходять з вершини i та входящік в неї),
vA і vB вказують, звідки і куди потрібно добиратися.
Оскільки за умовами задачі дороги двосторонні, то, для кожної введеної дороги, ми додаємо в граф дві дуги.
Основний алгоритм виглядає наступним чином:

for i: = 1 to N do
begin
for j: = 1 to kG [i] do Color [i, j]: = WHITE; {всі дуги вільні}
Time [i]: = maxlongint; {час маршруту до I - максимально}
end;
OptT: = Maxlongint; {Оптимальний час - максимально}
Sled [1]: = vA; {Заносимо в маршрут вершину vA}
kv: = 1; {Кількість вершин у маршруті = 1}
Time [vA]: = 0; {Оптимальний час до вершини vA = 0}
DFS (vA); {Пошук в глибину від вершини vA}
висновок відповіді
Рекурсивна процедура DFS (i) забезпечує виконання наступної роботи:
Procedure DFS (i)
begin
for j: = 1 to kG [i] do
if G [i, j, 1] <> vB
then
begin
if color [i, j] = FREE
then
begin
продовження шляху з викликом DFS
end
end
else
begin
порівняння шляху з поточним оптимальним
end;
end;
Якщо поточна вершина - кінцева (vB), то робимо "... порівняння шляху з оптимальним"
Інакше перевіряємо, якщо поточна дуга ще не використання (color [i, j] = FREE) щось робимо "... продовження шляху з викликом DFS".
При цьому, перед входом в DFS позначаємо дугу як використану (color [i, j]: = DONE), а після виходу - як знову вільну (color [i, j]: = FREE);
"... Вони йшли з викликом DFS" включає в себе наступні оператори:
inc (kv); sled [kv]: = G [i, j, 1]; {поміщаємо в дорогу нову вершину}
NewTime: = Time [i] + G [i, j, 2] + CountTime; {обчислюємо новий час}
if NewTime <OptT {якщо новий час менше оптимального}
then {то продовжуємо, інакше - відсікаємо}
begin
color [i, j]: = DONE; {Позначаємо - ребро використано}
RetTime: = Time [G [i, j, 1]]; {Зберігаємо старе час}
Time [G [i, j, 1]]: = NewTime; {Встановлюємо новий час}
DFS (G [i, j, 1]); {Викликаємо пошук від G [i, j, 1]}
Time [G [i, j, 1]]: = RetTime; {Відновлюємо старе час}
color [i, j]: = FREE; {Позначаємо - ребро вільно}
end;
Sled [kv]: = 0; dec (kv); {Видаляємо вершину з шляху}

Для обчислення нового часу тут використовується функція CounTime з параметром kv - номер останньої вершини в стеке.Ета функція робить наступне: Відновлює номери вершин, проходу через перехрестя "з i1 через i2 в i3":
if kv = 2 then begin CountTime: = 0; exit; end;
i1: = sled [kv-2];
i2: = sled [kv-1];
i3: = sled [kv];
if i3 = i1 then begin CountTime: = K * D [i2]; exit; end;
Попутно, з'ясовується
а) якщо вершин в дорозі всього 2, тобто не було ніякого повороту - це крок з початкової вершини і CountTime = 0.
б) якщо i1 = i3 то це поворот на 180 градусів і автори завдання вважають, що це теж лівий поворот, CountTime = K * D [i2]; де, K - коефіцієнт який вводиться, i2 - перехрестя, D [i2] - кількість доріг, що входять до цього перехрестя.
Потім з масивів координат перехресть вибираються координати поточних перехресть: (x1, y1) (звідки); (x2, y2) (через який); (x3, y3) (куди).
x1: = x [i1]; x2: = x [i2]; x3: = x [i3];
y1: = y [i1]; y2: = y [i2]; y3: = y [i3];
Обчислюється рівняння прямої по точках (x1, y1) та (x2, y2)
A: = y2-y1;
B: = x1-x2;
C: = y1 * (x2-x1)-x1 * (y2-y1);

Підстановкою координат (x3, y3) в рівняння прямої Ax + By + C = 0, побудованої за першими двох точках (x1, y1) та (x2, y2) і з урахуванням крайніх випадків, коли пряма паралельна осях координат, обчислюємо, чи був поворот лівим чи правим і відповідно встановлюємо значення функції CountTime.
Left: = (((x2> x1) and ((A * x3 + B * y3 + C) <0))) or
(((X2 <x1) and ((A * x3 + B * y3 + C) <0))) or
(((Y2 = y1) and (x1> x2) and (y3 <y1))) or
(((Y2 = y1) and (x1 <x2) and (y3> y1))) or
(((X2 = x1) and (y1> y2) and (x3> x1))) or
(((X2 = x1) and (y1 <y2) and (x3 <x1)));
if Left then CountTime: = K * D [i2]
else CountTime: = 0;
"Порівняння шляху з оптимальним" виконується наступним чином:
inc (kv); sled [kv]: = G [i, j, 1];
T: = Time [i] + G [i, j, 2] + CountTime;
if T <OptT
then begin
OptT: = T;
OptKv: = kv; OptSled: = Sled;
end;
Sled [kv]: = 0; dec (kv);
Таким чином, оптимальний час зберігається у змінній OptT а оптимальний шлях зберігатися в масиві OptSled з кількістю елементів OptKv. І тому, виведення результатів виглядає так:

writeln (OptT);
for i: = 1 to OptKv do writeln (OptSled [i]);
Повний текст програми наводиться нижче
program by98d2s2;
Const
FREE = 1;
DONE = 2;
Type
int1000 = 0 .. 1000;
int3 = 1 .. 3;
var
G: array [1 .. 1000,1 .. 10,1 .. 2] of int1000;
Time, D: array [1 .. 1000] of longint;
x, y, kG, Sled, OptSled, divd: array [1 .. 1000] of int1000;
Color: array [1 .. 100,1 .. 10] of int3;
N, M, K, i, p, r, t, vA, vB, v, kv, OptKv, j: int1000;
OptT: longint;
function CountTime (i: int1000): longint;
var
Left: boolean;
i1, i2, i3: int1000;
x1, x2, x3, y1, y2, y3, A, B, C: longint;
begin
if kv = 2 then begin CountTime: = 0; exit; end;
i1: = sled [kv-2];
i2: = sled [kv-1];
i3: = sled [kv];
if i3 = i1 then begin CountTime: = K * D [i2]; exit; end;
x1: = x [i1]; x2: = x [i2]; x3: = x [i3];
y1: = y [i1]; y2: = y [i2]; y3: = y [i3];
A: = y2-y1;
B: = x1-x2;
C: = y1 * (x2-x1)-x1 * (y2-y1);
Left: = (((x2> x1) and ((A * x3 + B * y3 + C) <0))) or
(((X2 <x1) and ((A * x3 + B * y3 + C) <0))) or
(((Y2 = y1) and (x1> x2) and (y3 <y1))) or
(((Y2 = y1) and (x1 <x2) and (y3> y1))) or
(((X2 = x1) and (y1> y2) and (x3> x1))) or
(((X2 = x1) and (y1 <y2) and (x3 <x1)));
if Left
then CountTime: = K * D [i2]
else CountTime: = 0;
end;
Procedure DFS (i: int1000);
var
j: byte;
T: longint;
RetSled, RetPred, RetTime: longint;
begin
for j: = 1 to kG [i] do
if G [i, j, 1] <> vB
then
begin
if color [i, j] = FREE
then
begin
inc (kv); sled [kv]: = G [i, j, 1];
NewTime: = Time [i] + G [i, j, 2] + CountTime;
if NewTime <OptT
then
begin
color [i, j]: = DONE;
RetTime: = Time [G [i, j, 1]];
Time [G [i, j, 1]]: = NewTime;
DFS (G [i, j, 1]);
Time [G [i, j, 1]]: = RetTime;
color [i, j]: = FREE;
end;
Sled [kv]: = 0; dec (kv);
end
end
else
begin
inc (kv); sled [kv]: = G [i, j, 1];
T: = Time [i] + G [i, j, 2] + CountTime;
if T <OptT
then begin
OptT: = T;
OptKv: = kv; OptSled: = Sled;
end;
Sled [kv]: = 0; dec (kv);
end;
end;
begin
assign (input, 'PER.in'); reset (input);
assign (output, 'PER.out'); rewrite (output);
read (N, M, K);
for i: = 1 to N do readln (x [i], y [i]);
for i: = 1 to N do begin kG [i]: = 0; D [i]: = 0; end;
for i: = 1 to M do
begin
readln (p, r, t); inc (kG [p]); inc (kG [r]);
G [p, kG [p], 1]: = r; G [p, kG [p], 2]: = t; inc (D [p]);
G [r, kG [r], 1]: = p; G [r, kG [r], 2]: = t; Inc (D [r]);
end;
readln (vA, vB);
for i: = 1 to N do
begin
for j: = 1 to kG [i] do Color [i, j]: = FREE;
Time [i]: = maxlongint;
end;
Time [vA]: = 0; kv: = 1; Sled [1]: = vA; OptT: = Maxlongint;
DFS (vA);
writeln (OptT);
for i: = 1 to OptKv do writeln (OptSled [i]);
close (input); close (output);
end.

4 Завдання "Скрудж Мак-Дак"

(Автор - Котов В.М.)
Республіканська олімпіада з інформатики 1995
Скрудж Мак-Дак вирішив зробити прилад для керування літаком. Як відомо, положення штурвала залежить від стану вхідних датчиків, але ця функція досить складна.
Його механік Гвинт Р. зробив пристрій, обчислює цю функцію в кілька етапів з використання проміжної пам'яті і допоміжних функцій. Для обчислення кожної з функцій потрібно, щоб у комірках пам'яті вже перебували обчислені параметри (які є значеннями обчислених функцій), необхідні для її обчислення. Обчислення функції без параметрів може проводиться в будь-який час. Після обчислення функції осередки можуть бути використані повторно (хоча б для запису результату обчисленої функції). Структура виклику функцій така, що кожна функція обчислюється не більше одного разу і будь-який параметр використовується не більше одного разу. Будь-який параметр є ім'я функції. Так як Скрудж не хоче витрачати зайвих грошей на мікросхеми, він поставив завдання мінімізувати пам'ять приладу. По заданной структуре вызовов функций необходимо определить минимальный возможный размер памяти прибора и указать последовательность вычисления функций.
Входной файл INPUT.TXT
Формат ввода:
1 строка> <общее количество функций N>
2 строка> <имя функции, которую необходимо вычислить>
3 строка> <имя функции> <кол-во параметров>[<список имен параметров>]
...N+2 строка> <имя функции> <кол-во параметров>[<список имен параметров>]
Выходной файл OUTPUT.TXT
Формат вывода:
Размер памяти (в ячейках)
имя 1-й вычисляемой функции
имя 2-й вычисляемой функции
....имя функции, которую необходимо вычислить
Примечание: имя функции есть натуральное число от 1 до N.
Приклад.


В кратком изложении в данной задаче требуется сделать следующее:
- найти S - максимальную степень среди тех вершин, что подлежат обходу (поиск в глубину DFS1)
- необходимая память вычисляется по формуле
MaxS = S + k -1
где S - найдено на предыдущем шаге (DFS1),
а k - максимальное количество вершин одного уровня вложенности с такой же степенью S.
Для вычисления k совершается обход повторным поиском в глубину DFS2
- третьим поиском в глубину DFS3 находим и помещаем в очередь V все вершины, степень которых равна S.
- последним, четвертым поиском в глубину обходим данное дерево в порядке вершин в очереди V. То есть, в первую очередь вычисляем те функции, для которых требуется максимальная память.
Рассмотрим реализацию алгоритма более подробно.
Ввод исходных данных осуществляется следующим образом:
read(N,FC);
for i: = 1 to N do
begin
read(f,kG[f]);
for j:=1 to kG[f] do read(G[f,j]);
end;
Тут
N - исходное количество вершин,
FC - номер функции, которую нужно вычислить
kG[i] - количество параметров для вычисления функции i
G[i,j] - j-тый параметр, требуемый для вычисления функции i
Тело главной программы выглядит так :
for i:=1 to N do color[i]:=WHITE;
{пометить свободными все вершины}
DFS1(FC);
{находим S - максимальную степень вершин используемых для вычисления функции FC}
MaxS:=S;
DFS2(FC);
{Вычисляем K - количество вершин со степенью S в текущем слое и MaxS - максимальная из значений по слоям величина S+K-1}
kv:=0;
DFS3(FC);

{Поместить в массив V все вершины, степень которых равна S, количество таких вершин - в переменной kv}
kr:=0;
for i:=1 to kv do DFS4(v[i]);
{Обход графа поиском в глубину начиная с вершин с максимальной степенью из массива V. Найденные вершины заносить в массив r}
writeln(MaxS); {вывод количества ячеек памяти}
for i:=1 to kr do writeln(r[i]);
{вывод порядка вычисления функций}
Полное решение задачи приводится ниже
program by95d2t1;
const
WHITE = 1;
GRAY = 2;
BLACK = 3;
var
G : array [1..100,1..100] of longint;
kG,v,color,r : array [1..100] of longint;
N,FC,i,j,s,f,kv,MaxS,kr : longint;
procedure DFS1(u:longint);
var
i,k : longint;
begin
if s<kG[u] then s:=kG[u];
for i:=1 to kG[u] do DFS1(G[u,i]);
end;
procedure DFS2(u:longint);
var
i,k : longint;
begin
k: = 0;
for i:=1 to kG[u] do
if kG[G[i,j]]=s then inc(k);
if MaxS<s+k-1 then MaxS:=s+k-1;
for i:=1 to kG[u] do DFS2(G[u,i]);
end;
procedure DFS3(u:longint);
var
i,k : longint;
begin
if kG[u]=s
then
begin
for i:=1 to kG[u] do DFS3(G[u,i]);
inc(kv); v[kv]:=u;
end;
end;
procedure DFS4(u:longint);
var
i : longint;
begin
color[u]:=GRAY;
if kG[u]<>0
then
for i:=1 to kG[u] do
if color[G[u,i]]<>GRAY
then DFS4(G[u,i]);
inc(kr); r[kr]:=u;
end;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(N,FC);
for i: = 1 to N do
begin
read(f,kG[f]);
for j:=1 to kG[f] do read(G[f,j]);
end;
for i:=1 to N do color[i]:=WHITE;
DFS1(FC);
MaxS:=s; DFS2(FC);
kv:=0; DFS3(FC);
kr:=0; for i:=1 to kv do DFS4(v[i]);
writeln(MaxS);
for i:=1 to kr do writeln(r[i]);
close(input); close(output);
end.

Висновок

Існує цілий клас задач з програмування, які простіше вирішуються, якщо учень володіє певним набором знань, умінь і навичок у галузі алгоритмів на графах. Це відбувається тому, що такі завдання можуть бути переформульовані в термінах теорії графів.
Теорія графів містить величезну кількість визначень, теорем і алгоритмів. І тому цей матеріал не може претендувати, і не претендує, на повноту охоплення матеріалу. Однак, на думку автора, пропоновані відомості є гарним компромісом між обсягом матеріалу і його "коефіцієнтом корисної дії" в практичному програмуванні та вирішенні олімпіадних завдань.
Необходимо отметить, что данный материал в существенной степени опирается на наличие у ученика определенных навыков в использовании рекурсивных функций и рекуррентных соотношений, которые, в частности, могут появиться при работе над предыдущими главами этой книги.

Література
1. Абдеев Р.Ф. Філософія інформаційної цивілізації. - М.: Владос, 1994.
2. Адамар Ж. Дослідження психології процесу винаходи в галузі математики. - М.: Сов. радіо, 1970.
3. Болтянский В.Г. Інформатика і математики / / Математика в школі. 1989. № 4.-С.86-90
4. Вейценбаум Дж. Можливості обчислювальних машин і людський розум. - М.: Радіо і зв'язок, 1982.
5. Вірт Н. Алгоритми + Структури даних = Програма. - М.: Світ, 1989
6. Вірт Н. Систематичне програмування: Введення. - М.: Світ, 1977.
7. Громов Г.Р. Нариси інформаційної технології. - М.: ІнфоАрт, 1993.
8. Дейкстра Е. Дисципліна програмування. - М.: Світ, 1978.
9. Ільєнко Е. В. Філософія і культура. - М.: Політ. лит., 1991.
10. Йодан Е. Структурне проектування і конструювання програм. - М.: Світ, 1979.
11. Майерс Г. Надійність програмного забезпечення. - М.: Світ, 1980.
12. Махмутов М.І. Організація проблемного навчання в школі. - М., 1986.
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
50.6кб. | скачати


Схожі роботи:
Динамічне програмування алгоритми на графах
Алгоритми на графах Незалежні та домінуючі безлічі
Операції на графах
Рішення задач на графах
Передача електроенергії на відстані та її використання
Трансформатор Передача електроенергії на великі відстані
Визначення фокусної відстані збиральної і розсіює лінз
Ознаки ушкодження при пострілах з різного відстані
Двовимірна кластеризуючих за граничним відстані Дискретна математика
© Усі права захищені
написати до нас