Динамічне програмування алгоритми на графах

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

скачати

Міністерство освіти Республіки Білорусь
Установа освіти
«Гомельський державний університет ім. Ф. Скорини »
Математичний факультет
Кафедра МПМ
Реферат
Динамічне програмування, алгоритми на графах
Виконавець:
Студентка Старовойтова А.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент Лебедєва М.Т.
Гомель 2007

Зміст
Введення
1. Алгоритми, що використовують рішення додаткових підзадач
2. Основні визначення теорії графів
3. Пошук шляху між парою вершин невиваженого графа
4. Шляхи мінімальної довжини у зваженому графі
Висновок
Література

Введення

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

1. Алгоритми, що використовують рішення додаткових підзадач

Завдання 9. Потрібно підрахувати кількість різних розбиттів числа N на натуральні складові. Два розкладання вважаються різними, якщо одне не можна отримати з іншого шляхом перестановки доданків.

Рішення. Для того щоб підрахувати кількість різних розбиттів числа N на довільні натуральні складові, попередньо підрахуємо кількості розбиття на наступні групи доданків: 1) розбиття тільки на одиниці (очевидно, що для будь-якого числа таке розбиття єдино); 2) розбиття на одиниці і двійки такі, що хоча б одна двійка в розбитті присутній і т.д. Останню групу представляє саме число N. Очевидно, що кожне розбиття числа N можна приписати тільки до однієї з розглянутих груп, залежно від значення j - максимального доданка в тому чи іншому розбивці. Позначимо кількість розбиттів в кожній з груп t (N, j). Тоді шукану кількість розбиттів дорівнює сумі розбиття по всіх можливих груп. Введення таких підзадач призводить до нескладного способу підрахунку числа розбиття. А саме, тому що в будь-якому з розбиття j-ої групи присутній число j, то ми можемо відняти з N число j і скласти розбиття вже числа N - j на складові, не перевершують j. Тобто ми прийшли до наступного рекурентному співвідношенню:
Тепер очевидно, що якщо ми маємо можливість завести двовимірний масив розміром N 'N, і будемо заповнювати її в порядку зростання номерів рядків, то завдання буде легко вирішена. Проте легко помітити, що вирішення частини підзадач ніяк не беруть участь у формуванні рішення. Наприклад, при обчисленні кількості розбиття числа 10 на складові будуть отримані, але не використані значення t (9, j) для j = 2 .. 9 і т. д. Для того щоб не виробляти зайвих обчислень, застосуємо динамічне програмування "зверху вниз" (усі попередні завдання вирішувалися "знизу вгору"). Для цього завдання будемо вирішувати все ж рекурсивно, використовуючи формулу (*), але відповіді до вже вирішеним підзадач будемо запам'ятовувати в таблиці. Спочатку таблиця порожня (вірніше заповнимо елементи, значення яких за формулою (*) дорівнює 0 або 1, а інші значення, наприклад, числом -1). Коли в процесі обчислень підзадача зустрічається вперше, її рішення заноситься в таблицю. Надалі рішення цієї підзадачі береться з таблиці. Таким чином ми отримали прийом поліпшення рекурсивних алгоритмів, а "зайві" підзадачі тепер вирішуватися не будуть.
Наведемо програму для вирішення цього завдання.
var i, j, k, n: byte;
sum: longint;
table: array [1 .. 120,1 .. 120] of longint;
function t (n, k: byte): longint;
var i, s: byte;
begin
if table [n, k] <0 then
{Решта елементи не перераховуємо}
begin
table [n, k]: = 0;
for i: = 1 to k do
inc (table [n, k], t (nk, i))
end;
t: = table [n, k]
end;
begin
read (n);
fillchar (table, sizeof (table), 0);
for i: = 1 to n do
begin
table [i, i]: = 1;
table [i, 1]: = 1
end;
{Невизначені елементи мітимо -1}
for i: = 2 to n do
for j: = 2 to i-1 do
table [i, j]: =- 1;
sum: = 0;
for i: = 1 to n do
sum: = sum + t (n, i);
writeln ('sum =', sum)
end.
Завдання 10. Плитки (Чемпіонат школярів з програмування, Санкт-Петербург, 1999 р.).
У Петі є необмежений набір червоних, синіх і зелених плиток розміром 1'1. Він вибирає рівно N плиток і викладає їх у смужку. Наприклад, при N = 10 вона може виглядати наступним чином:
До
До
До
З
З
До
До
З
До
З
(Буквою До позначена червона плитка, С - синя, З - зелена)

Після цього Петя заповнює таку таблицю, яка в даному прикладі виглядає так:
Червоний
Синій
Зелений
Червоний
Y
Y
Y
Синій
Y
N
Y
Зелений
Y
Y
N
У клітці на перетині рядка, що відповідає кольору А, і стовпця, що відповідає кольору Б, він записує "Y", якщо в його смужці знайдеться місце, де поруч лежать плитки квітів А і Б і "N" в іншому випадку. Вважається, що плитки лежать поруч, якщо у них є спільна сторона. (Очевидно, що таблиця симетрична щодо головної діагоналі - якщо плитки квітів А і Б лежали поруч, то поряд лежали і плитки квітів Б і А.) Назвемо таку таблицю діаграмою суміжності даної смужки.
Так, дана таблиця являє собою діаграму суміжності наведеної вище смужки.
Допоможіть Петі дізнатися, скільки різних смужок має певну діаграму суміжності (зауважте, що смужки, що є віддзеркаленням один одного, але не збігаються, вважаються різними. Так, смужка
З
До
З
До
До
З
З
До
До
До
не збігається з смужкою, наведеної на початку умови.)
Перший рядок вхідного файлу містить число N. ( ). Наступні три рядки вхідного файлу, що містять по три символи з набору {"Y", "N"}, відповідають трьом рядкам діаграми суміжності. Інших символів, включаючи пробіли, у вхідному файлі не міститься. Вхідні дані коректні, тобто діаграма суміжності симетрична.
Виведіть у вихідний файл кількість смужок довжини N, що мають наведену у вхідному файлі діаграму суміжності. Нижче дан приклад вхідного і вихідного файлів.
Input.txt
Output.txt
10
YYY
YNY
YYN
4596
Рішення. Очевидно, що перебір всіх можливих смужок у даній задачі неможливий, оскільки їх кількість може скласти 2 100, тому слід спробувати знайти динамічну схему вирішення. Зрозуміло, що для того щоб підрахувати кількість смужок довжини N, що задовольняють заданій діаграмі суміжності, необхідно знати кількість допустимих смужок довжини N - 1, а також кількість смужок, в діаграмі суміжності яких один діагональний елемент або два симетричних недіагональні елемента рівні "N" замість " Y "у вихідній діаграмі. Далі, при розгляді смужок довжини N - 2, буде потрібно знати кількість смужок, що задовольняють ще більшій кількості діаграм суміжності і т. д. У результаті на якомусь кроці нам може знадобитися інформація про кількість смужок практично з усіма можливими діаграмами. Загальна кількість останніх становить 2 6 = 64 (унікальними, тобто не повторюються, а, значить, визначальними кількість різних діаграм, є тільки 6 елементів). Оскільки при збільшенні довжини смужки діаграма може змінитися в залежності від поєднання квітів в останньому (новому) і передостанньому елементах, підраховувати смужки слід окремо для трьох різних кінцевих елементів. Таким чином кількість інформації, що зберігається зростає до 64'3 = 192 значень. Стільки ж значень буде отримано в результаті перерахунку. Але завдяки тому, що кількість смужок довжини i виражається тільки через кількість смужок довжини i - 1, зберігати треба лише ці 2'192 = 384 значення. Незважаючи на малий розмір таблиці (масив total в програмі) слід зазначити, що її розмір експоненціально залежить від одного з вхідних параметрів - кількості квітів k, а саме: 2 'k '2 k (k +1) / 2. Наприклад, для 8 квітів необхідно було б зберігати 2 40 елементів, що нереально. Цим дана задача відрізняється від розглянутих раніше.
Залишилося обговорити деякі технічні прийоми, що дозволяють написати досить просту програму, що реалізовує описаний алгоритм. Якщо ми поставимо у відповідність кожному з унікальних місць у діаграмі суміжності свій ступінь двійки від 2 0 до 2 5 (див. масив констант magic в програмі), то кожній діаграмі може бути поставлений у відповідність номер від 0 до 63, який дорівнює сумі тих ступенів двійок , які відповідають значенням "Y" (див. процедуру findcode). Якщо ми підраховуємо кількість смужок для діаграми з номером j, то сумісність додається кольору k стояв раніше останнім кольором l згідно діаграмі j можна перевірити так: magic [k, l] and j <> 0. Дана умова, побудоване за допомогою бітової операції над цілими числами and, означає наявність в j-ої діаграмі суміжності елемента "Y" на перетині k-го рядка і l-го стовпця (відповідна ступінь двійки масиву magic міститься в двійковому представленні числа j). Вираз j - magic [k, l] відповідає заміні у діаграмі з номером j згаданого елемента "Y" на "N" (по іншому це вираз можна було б записати як j xor magic [k, l]). Детальніше про бітових операціях над цілими числами можна прочитати в [1]. Останній прийом полягає в тому, що ми не будемо на кожному кроці перепрісваівать отримані значення елементам масиву, призначеного для зберігання результатів попереднього кроку. Для цього результати для смужок парному довжини i будемо розміщувати в половину масиву total з першим індексом 0, а непарні - з індексом 1. У будь-якому з цих випадків значення попереднього кроку доступні за індексом [1 - i mod 2]. Крім того, відповідь на рішення цієї задачі при всіх N, що задовольняють умові, вимагає самостійної організації обчислень за допомогою так званої "довгої арифметики" (див., наприклад, [1, 3]).
Наведемо програму для вирішення цього завдання, але використовує замість "довгої арифметики" тип даних extended, зберігає максимально можливу кількість значущих цифр (спробуйте модернізувати програму самостійно). Тобто не для всіх значень N відповідь буде вирахувано точно. Але, так як для отримання результату використовується тільки додавання цілих чисел, втрати точності при проміжних обчисленнях не буде, принаймні поки відповідь не стане перевищувати 2 63.
{$ N +}
const magic: array [1 .. 3, 1 .. 3] of byte =
((1, 2, 4),
(2, 8, 16),
(4, 16, 32));
var n, i, j, k, l, code: longint;
can: array [1 .. 3, 1 .. 3] of boolean;
total: array [0 .. 1, 1 .. 3, 0 .. 63] of extended;
answer: extended;
procedure readdata;
var s: string;
i, j: byte;
begin
readln (n);
fillchar (can, sizeof (can), false);
for i: = 1 to 3 do
begin
readln (s);
for j: = 1 to 3 do
if upcase (s [j]) = 'Y' then
begin
can [i, j]: = true;
can [i, j]: = true
end
end
end;
procedure findcode;
var i, j: byte;
begin
{Переводимо діаграму суміжності в число}
code: = 0;
for i: = 1 to 3 do
for j: = i to 3 do
if can [i, j] then
code: = code + magic [i, j]
end;
begin
assign (input, 'input.txt');
reset (input);
assign (output, 'output.txt');
rewrite (output);
readdata;
findcode;
fillchar (total, sizeof (total), 0);
{Кількість смужок довжини 1}
for i: = 1 to 3 do
total [1, i, 0]: = 1;
for i: = 2 to n do
for j: = 0 to 63 do
for k: = 1 to 3 do
{Вважаю смужки довжини i,
c діаграмою суміжності j
і закінчуються кольором k}
begin
total [i mod 2, k, j]: = 0;
for l: = 1 to 3 do
{Цикл за кінцевим кольором
смужок довжини i - 1}
if magic [k, l] and j <> 0 then
{Кольору l і ​​k можуть бути сусідами
згідно діаграмі суміжності j}
begin
total [i mod 2, k, j]: =
total [i mod 2, k, j] +
total [1 - i mod 2, l, j];
total [i mod 2, k, j]: =
total [i mod 2, k, j] +
total [1 - i mod 2, l, j - magic [k, l]]
end
end;
answer: = 0;
{Підсумовуємо кількість смужок з діаграмою
суміжності code і різними закінченнями}
for i: = 1 to 3 do
answer: = answer + total [n mod 2, i, code];
writeln (answer: 0:0)
end.

Схожа завдання ("Симпатичні візерунки") пропонувалася і на I-ої Всеросійської командній олімпіаді з програмування. Її умова і рішення можна прочитати в [2].
Задача 11. Паркет (Завдання VI Всеросійської олімпіади з інформатики, 1994 р.)
Кімнату розміром N 'M одиниць потрібно покрити однаковими паркетними плитками розміром 2'1 одиницю без пропусків і накладень (1 £ N £ 20, 1 £ M £ 8). Потрібно визначити кількість усіх можливих способів укладання паркету для конкретних значень N і M.
Рішення. Нехай M - ширина кімнати, яку ми зафіксуємо. Спробуємо висловити шукану кількість укладок паркету для кімнати довжини N, через кількість укладок для кімнати довжиною N - 1. Однак очевидно, що зробити це не вдасться, так як існує ще безліч укладок, в яких частина плиток перетинає кордон між такими кімнатами. Отже нам знову доведеться вирішувати додаткове число підзадач. А саме, введемо узагальнене поняття укладання кімнати довжиною N - 1: перша частина кімнати довжиною N - 2 покладена щільно, а в (N - 1)-й одиниці вимірювання довжини кімнати можуть перебувати порожнечі (в N-й одиниці виміру паркету немає). Якщо наявність плитки в (N - 1)-й одиниці виміру позначити 1, а її відсутність - 0, то кількість різних закінчень подібних укладок можна пронумерувати двійковими числами від 0 до 2 M - 1. Якщо кількість укладок для кожного з закінчень нам відомо (частина з них можуть виявитися нереалізованим, то є відповідна кількість укладок буде дорівнює 0), то ми зможемо підрахувати кількість різних укладок кімнати довжини N. При цьому доведеться перевіряти сумісність закінчень. Закінчення будемо вважати сумісними, якщо шляхом додавання цілого числа плиток до укладі довжиною N - 1 із закінченням j, таких що кожна з них збільшує довжину укладання до N, ми можемо отримати закінчення i укладання довжиною N. Якщо спосіб поєднання укладок існує, то з побудови він єдиний. Тоді для визначення кількості укладок із закінченням i довжиною N необхідно підсумувати кількості укладок довжиною N - 1 з сумісними закінченнями. Для кімнати нульової довжини будемо рахувати кількість укладок рівним 1. Формування динамічної схеми закінчено. Кількість збережених в програмі значень при цьому одно 2'2 M = 2 M +1, тобто воно експоненціально залежить від одного з параметрів задачі й істотно його збільшити не представляється можливим. У нашому випадку воно дорівнює 512, тобто застосування табличного методу розв'язання виявляється реальним. Відповідь на питання завдання буде отриманий на N-му кроці алгоритму в елементі таблиці з номером 2 M - 1. При максимальному за умовою завдання розмірі кімнати для отримання відповіді знову буде потрібно "довга арифметика".
Схему програми для вирішення цього завдання, яка простіше попередньої, можна знайти, наприклад, в [3].
Після розгляду завдань 9-11 може скластися враження, що до даного класу відносяться лише завдання підрахунку кількостей тих чи інших конфігурацій, у тому числі комбінаторних. Звичайно ж це не так. Прикладом оптимізаційної задачі, рішення якої грунтується на аналогічних ідеях, служить завдання "Бізнес-класики", запропонований на XIII Всеросійської олімпіади з програмування (див. [4]).
Багато прикладні та олімпіадні завдання легко сформулювати у термінах такої структури даних як граф. Для ряду подібних завдань добре вивчені ефективні (поліноміальні) алгоритми їх вирішення. Розглянемо в даній лекції ті з них, які використовують ідеї динамічного програмування. Але спочатку необхідно ознайомитися з деякими термінами, що зустрічаються при описі цієї структури.

2. Основні визначення теорії графів

Графом називається пара , Де V - деяке безліч, яку називають множиною вершин графа, а E - відношення на V ( ) - Безліч ребер графа. Тобто усі ребра з множини E з'єднують деякі пари точок з V.
Якщо відношення E симетричне (тобто ), То граф називають неорієнтованим, у противному випадку граф називають орієнтованим. Фактично для кожного з ребер орієнтованого графа вказані початок і кінець, тобто пари (u, v) впорядкована, а в неорієнтованому графі (u, v) = (v, u).
Якщо в графі існує ребро (u, v), то говорять, що вершина v суміжна з вершиною u (в орієнтованому графі ставлення суміжності несиметрично).
Шляхом з вершини u у вершину v довжиною k ребер називають послідовність ребер графа . Часто той же шлях позначають послідовністю вершин . Якщо для даних вершин u, v існує шлях з u в v, то говорять, що вершина v досяжна з u. Шлях називається простим, якщо всі вершини в ньому різні. Циклом називається шлях, у якому початкова вершина збігається з кінцевою. При цьому цикли, що відрізняються лише номером початкової точки, ототожнюються.
Граф називається зв'язаним, якщо для будь-якої пари його вершин існує шлях з однієї вершини в іншу.
Якщо кожному ребру графа приписано якесь число (вага), то граф називають зваженим.
При програмуванні вершини графа зазвичай зіставляють числах від 1 до N, де - Кількість вершин графа, і розглядають . Ребра нумерують числами від 1 до M, де . Для зберігання графа в програмі можна застосувати різні методи. Найпростішим є зберігання матриці суміжності, тобто двовимірного масиву, скажімо A, де для невиваженого графа (Або 1), якщо і (Або 0) в іншому випадку. Для зваженого графа A [i] [j] дорівнює вазі відповідного ребра, а відсутність ребра в ряді завдань зручно позначати нескінченністю. Для неорієнтованих графів матриця суміжності завжди симетрична щодо головної діагоналі (i = j). C допомогою матриці суміжності легко перевірити, чи існує в графі ребро, що з'єднує вершину i з вершиною j. Основний же її недолік полягає в тому, що матриця суміжності вимагає, щоб обсяг пам'яті пам'яті був достатній для зберігання N 2 значень, навіть якщо ребер у графі істотно менше, ніж N 2. Це не дозволяє побудувати алгоритм з часом порядку O (N) для графів, що мають O (N) ребер.
Цього недоліку позбавлені такі способи зберігання графа, як одновимірний масив довжини N списків або множин вершин. У такому масиві кожен елемент відповідає одній з вершин і містить список або безліч вершин, суміжних їй.
Для реалізації деяких алгоритмів більш зручним є опис графа шляхом перерахування його ребер. У цьому випадку зберігати його можна в одновимірному масиві довжиною M, кожен елемент якого містить запис про номери початкової і кінцевої вершин ребра, а також його вагу в разі зваженого графа.
Нарешті, при вирішенні задач на графах, у тому числі і з допомогою комп'ютера, часто використовується його графічне представлення. Вершини графа зображують на площині у вигляді крапок або маленьких кружків, а ребра - у вигляді ліній (не обов'язково прямих), що з'єднують відповідні пари вершин, для неорієнтованого графа і стрілок - для орієнтованого (якщо ребро спрямовано з u в v, то з точки, зображує вершину u, проводять стрілку у вершину v).
Графи широко використовуються в різних галузях науки (в тому числі в історії!) І техніки для моделювання відносин між об'єктами. Об'єкти відповідають вершин графа, а ребра - відносинам між об'єктами). Детальніше про цю структуру даних можна прочитати в [5 - 7].

3. Пошук шляху між парою вершин невиваженого графа

Нехай ми маємо довільний граф, орієнтований або неорієнтований. Якщо в незваженим графі існує шлях, то назвемо довжиною шляху кількість ребер у ньому. Якщо шляху немає взагалі, то відстань вважається нескінченним. Шлях мінімальної довжини при цьому називається найкоротшим шляхом в графі. Легко показати, що будь-які частини найкоротшого шляху також є найкоротшими шляхами між відповідними вершинами. Адже якщо це не так, тобто існує відрізок найкоротшого шляху, між кінцями якого можна побудувати більш короткий шлях, то ми можемо замінити цей відрізок найкоротшого шляху між вершинами u та v на більш короткий, тим самим зменшивши і довжину найкоротшого шляху між u і v , що неможливо. Це властивість найкоротших шляхів дозволяє вирішувати завдання їх знаходження методом динамічного програмування. Покажемо спочатку як можна записати "хвильовий алгоритм" так, що завдання пошуку найкоротшого шляху між двома вершинами графа буде вирішуватися за O (N 2) дій.
Задача 12. Для ліній метрополітену деякого міста відомо, між якими парами ліній є пересадочна станція. Необхідно визначити, за скільки пересадок можна дістатися з лінії на лінію m n або повідомити, що зробити це неможливо.
Рішення. Такий метрополітен зручно описувати за допомогою графа, вершини якого є лінії метрополітену (а не станції !!!), а наявність ребра між вершинами i та j графа відповідає наявності пересадковою станції між лініями з номерами i та j. Уявімо цей граф з допомогу масиву множин (змінна ss в програмі), в i-му елементі цього масиву міститься безліч всіх ліній, на які можна потрапити з лінії i за одну пересадку. Результат будемо отримувати за допомогою безлічі s, на кожному кроці алгоритму містить номери всіх ліній, на які можна потрапити з вихідної лінії m за k пересадок. Зауважимо, що якщо вершина n нашого графа досяжна з вершини m (кажуть, що вони знаходяться в одній компоненті зв'язності), то дані число пересадок менше загальної кількості ліній nn. Бо навіть якщо після кожної з перших nn - 1 пересадок ми потрапляли на нову лінію, то після наступної пересадки ми обов'язково опинимося на якийсь з ліній повторно, адже їх всього nn. Тому, якщо наш алгоритм не завершився за nn - 1 крок, то граф не пов'язаний і подальший пошук шляху марний (зауважимо, що наявність шляху між двома конкретними вершинами не доводить його зв'язність, а досліджувати всі пари вершин з допомогою запропонованого алгоритму для аналізу зв'язності неефективно ).
Програма для виконання завдання представленій нижче.
const nn = 200; {число ліній}
type myset = set of 0 .. nn; var i, m, n, k: byte; ss: array [1 .. nn] of myset; s, s1: myset; begin
... {Зчитуємо вхідні дані}
s: = [m]; k: = 0; while not (n in s) and (k <nn-1) do begin k: = k +1;
s1: = s; s :=[]; for i: = 1 to nn do if i in s1 then
{Додаємо до s вершини,
досяжні з i} s: = s + ss [i] end; if n in s then writeln (k) else
writeln ('it is impossible')
end.
Зауважимо, що запропонований при вирішенні завдання 12 алгоритм можна модифікувати так, щоб він знаходив довжину найкоротшого шляху від вихідної вершини до всіх інших вершин графа, причому асимптотичну час його роботи не зміниться. Незважаючи на гарні тимчасові характеристики, галузь застосування алгоритму обмежена розміром типу "безліч" в Паскалі. Уникнути цього обмеження можна, використовуючи такий спосіб представлення графа як масив списків вершин, суміжних з даною. Про способи реалізації динамічних структур даних, і зокрема списків, див., наприклад, [8].
Нехай тепер потрібно визначити наявність шляху відразу для всіх пар вершин графа. Таке завдання для невиваженого графа називається транзитивним замиканням. Розглянемо її рішення на прикладі наступної проблеми.
Задача 13. Нехай для деяких пар змінних відомо, що значення однієї з них не більше значення іншої. Виписати інші пари зі згаданих змінних, для яких, використовуючи транзитивність операції "£", можна також сказати, значення однієї з них не перевершує значення іншої.
Рішення. Позначимо даними змінними вершини графа, а знання про наявність між двома змінними відносини "£" - орієнтованими ребрами. Для деякої пари вершин справедливо, що значення однієї £ значення інше, якщо в побудованому орієнтованому графі існує шлях з першої зі згаданих вершин у другу. Тоді для вирішення задачі можна скористатися наступним алгоритмом Уоршолла [5, 6]. Нехай A - матриця, спочатку рівна матриці суміжності графа, записаної за допомогою логічних констант true і false. На k-му кроці алгоритму значення true в елементі матриці A [i, j] буде означати, що з вершини i у вершину j Існує шлях, який проходить через деякі вершини з номерами, не переважаючими k - 1. Якщо ж через згадані вершини шляху немає (A [i, j] = false), але існує шлях з вершини i у вершину k і шлях з вершини k у вершину j то значення даного елемента матриці стає true. Покажемо як написати фрагмент програми, що реалізує цей алгоритм без використання умовних операторів:
c: = a; {запам'ятовуємо матрицю суміжності}
for k: = 1 to nn do
for i: = 1 to nn do
for j: = 1 to nn do
a [i, j]: = a [i, j] or a [i, k] and a [k, j];
Стислість говорить тут сама за себе. В результаті виконання трьох вкладених циклів (тобто ми маємо алгоритм, що працює за N 3 операцій), порядок яких дуже важливий, в матриці a ми фактично отримаємо відповідь на питання завдання. Роздрукувати його можна так:
for i: = 1 to nn do
for j: = 1 to nn do
if a [i, j] xor c [i, j] then writeln (i, '', j);
Якщо ж потрібно знайти довжини найкоротших шляхів для всіх пар вершин, то, якщо кожному ребру графа приписати вага, що дорівнює одиниці, рішення задачі буде повністю співпадати з рішенням тієї ж задачі для зваженого графа (див. далі). Тому окремо ми розглядати його не будемо.

4. Шляхи мінімальної довжини у зваженому графі

Довжиною шляху між двома вершинами у зваженому графі називається сума ваг ребер, що складають цей шлях. На відміну від невиваженого графа наявність ребра між двома вершинами не гарантує, що найкоротший шлях між ними складається з цього ребра. Найчастіше сумарна вага шляху, що складається з двох, трьох і більше ребер може виявитися менше ваги одного ребра, тому навіть для повного графа (тобто графа, між кожною з пар вершин якого існує ребро, а у разі орієнтованого графа - два ребра, спрямованих в протилежні сторони) завдання пошуку найкоротших шляхів має сенс. Поняття найкоротшого шляху поки будемо розглядати тільки для графів, всі ребра яких мають невід'ємних вагу.
Найбільш просто знайти найкоротший шлях між кожною з пар вершин можна за допомогою алгоритму Флойда [5 - 7], заснованого на тій же ідеї, що і алгоритм Уоршолла. Нехай в елементі матриці A [i, j] зберігається довжина найкоротший шляху з вершини i у вершину j, який проходить через деякі вершини з номерами, не переважаючими k - 1. Якщо ж довжини шляху з вершини i у вершину k та шляхи з вершини k у вершину j то такі, що їх сума менше, ніж значення даного елемента матриці, то його слід перевизначити. Тобто в реалізації алгоритму Уоршолла слід замінити операцію and на "+", а or - на знаходження мінімуму з двох величин. Для реалізації алгоритму масив a спочатку слід заповнити елементами матриці суміжності, позначаючи відсутність ребра між двома вершинами "нескінченністю" - числом, свідомо переважаючим довжину будь-якого шляху в розглянутому графі, але меншим, ніж максимальне значення використовуваного типу даних, щоб було можливо виконувати з ним арифметичні операції. У цьому випадку можна уникнути додаткових перевірок.
Якщо ж нам треба знайти сам найкоротший шлях, а не його довжину, то при кожному поліпшенні шляху між двома вершинами ми у відповідному елементі допоміжного масиву (в програмі - w) будемо запам'ятовувати номер тієї вершини, через яку найкоротший шлях проходить, а потім за допомогою елегантної рекурсивної процедури будемо його друкувати. Ідея рекурсії полягає в тому, що якщо ми знаємо, що найкоротший шлях від вершини i до вершини j проходить через вершину k, то ми можемо звернутися до тієї ж самої процедури з частинами шляху від i до k і від k до j. Рекурсивний спуск закінчується, коли на найкоротшому шляху між двома вершинами не виявиться проміжних вершин.
Наведемо фрагмент програми, що реалізує алгоритм Флойда і друкує найкоротші шляхи між усіма парами вершин графа.

procedure way (i, j: integer);
{Друкує шлях між вершинами i та j}
begin
if w [i, j] = 0 then write ('', j)
{Друкуємо тільки вершину j,
щоб уникнути повторів}
else
begin
way (i, w [i, j]); way (w [i, j], j)
end
end;
begin
... {Заповнюємо матрицю суміжності}
for k: = 1 to nn do
for i: = 1 to nn do
for j: = 1 to nn do
if a [i, k] + a [k, j] <a [i, j] then
begin
a [i, j]: = a [i, k] + a [k, j];
w [i, j]: = k
end;
for i: = 1 to nn do
for j: = 1 to nn do
begin
write (i);
if i <> j then way (i, j);
writeln
end
end.

Алгоритм Флойда хороший всім, крім одного: він вимагає зберігати матрицю суміжності, а це не завжди можливо. Крім того, для визначення довжини найкоротшого шляху між двома конкретними вершинами, його спростити неможливо (тобто все одно доведеться рахувати шляху між усіма парами вершин). Якщо вага будь-якого ребра в графі обчислюється за деякою формулою (наприклад, як відстань між двома точками на площині, якщо такими є вершини нашого графа), то матрицю суміжності можна не створювати взагалі, а в процесі виконання програми звертатися до функції обчислення ваги ребра, що з'єднує вершини i та j: a (i, j).
У цьому випадку для визначення найкоротшого шляху між вершинами s і t використовують алгоритм Дейкстри [5 - 7]. Всі вершини в процесі роботи цього алгоритму розбиті на дві множини: ті, до яких найкоротший шлях з вершини s вже відомий (в програмі вони позначені значеннями true одновимірного булевского масиву b) і всі інші. Спочатку в першому безлічі знаходиться тільки вершина s. На кожному кроці до нього додається одна з вершин, поточне відоме відстань до якої мінімально серед усіх вершин з другого безлічі, позначимо її p. Спочатку поточні відстані (в програмі вони зберігаються в одновимірному масиві l) від s до інших вершин рівні ¥, а відстань до s дорівнює 0, p також дорівнює s. На черговому ж кроці ми намагаємося поліпшити довжину шляху до кожної з вершин другого безлічі, порівнюючи вирази l [p] + a (p, i) і l [i]. Потрібно показати, чому мінімальне з значень l, розглянутих на поточному кроці, є довжиною найкоротшого шляху до відповідної вершини, а, отже, цей шлях містить тільки вершини з першої множини. Якщо це не так, то є найкоротший шлях до цієї вершини містить і вершини з другого безлічі, то мінімальної виявилася б довжина шляху від s до однієї з цих вершин. Значить найкоротший шлях до вершини p проходить тільки через вершини першої множини і більше його перераховувати не потрібно.
Наведемо схему програми, що реалізує цей алгоритм (функцію a (i, j) і значення "нескінченності" визначати не будемо):
for i: = 1 to nn do
begin
l [i] = ¥;
b [i]: = false
end;
p: = s; l [s]: = 0;
b [s]: = true;
f: = true; {Чи варто шукати далі}
while (p <> t) and f do
begin
f: = false;
for i: = 1 to nn do
if not b [i] then
if l [p] + a (p, i) <l [i] then l [i]: = l [p] + a (p, i);
min: = t; {важливо, що b [t] = false}
for i: = 1 to n do
if (not b [i]) and (l [i] <l [min]) then min: = i;
if l [min] <¥ then
begin
p: = min; b [p]: = true; f: = true
end
end;
Нескладно підрахувати, що трудомісткість алгоритму становить O (N 2), що окупає деякі складнощі в його реалізації. Як і у випадку застосування "хвильового" алгоритму в незваженим графі, асимптотична оцінка не зміниться якщо нам буде потрібно підрахувати довжину шляху від s до кожної з вершин графа. Тому, як і в алгоритмі Флойда, довжини найкоротших шляхів між усіма парами вершин можуть бути розраховані за O (N 3) операцій.

Висновок

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

Література

1. Андреєва О., Фаліна І. Системи числення та комп'ютерна арифметика. М.: Лабораторія базових знань, 2000.
2. Станкевич А. С. Рішення задач I Всеросійської командної олімпіади з програмування. "Інформатика", № 12, 2001.
3. Окулов С.М. 100 завдань з інформатики. Кіров: вид-во ВДПУ, 2000.
4. Андреєва О. В. Рішення завдань XIII Всеросійської олімпіади з інформатики. "Інформатика", № 19, 2001.
5. Ахо А.А., Хопкрофта Д.Е., Ульман Д. Д. Структури даних і алгоритми. М.: "Вільямс", 2000.
6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритми. Побудова та аналіз. М. МЦНМО, 2000.
7. Липський В. Комбінаторика для програмістів. М.: "Мир", 1988.
8. Вірт Н. Алгоритми і структури даних. Санкт-Петербург: "Невський діалект", 2001.
Додати в блог або на сайт

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

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


Схожі роботи:
Алгоритми на графах Найкоротші відстані на графах
Алгоритми на графах Незалежні та домінуючі безлічі
Динамічне і лінійне програмування
Динамічне програмування та варіаційне числення
Алгоритми і структури даних Програмування у Cі
VB MS Access VC Delphi Builder C прінціпитехнологія алгоритми програмування
Операції на графах
Рішення задач на графах
Дослідження релейно контакторною схеми управління ЕП з АД і динамічне гальмування
© Усі права захищені
написати до нас