Міністерство освіти Республіки Білорусь
Установа освіти
В«Гомельський державний університет ім. Ф. Скорини В»
Математичний факультет
Кафедра МПМ
Реферат
Динамічне програмування, алгоритми на графах
Виконавець:
Студентка Старовойтова А.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент Лебедєва М.Т.
Гомель 2007
Зміст
Введення
1. Алгоритми, використовують рішення додаткових підзадач
2. Основні визначення теорії графів
3. Пошук шляху між парою вершин незваженого графа
4. Шляхи мінімальної довжини у зваженому графі
Висновок
Література
Введення
Існує цілий клас задач з програмування, які простіше вирішуються, якщо учень володіє певним набором знань, умінь і навичок у сфері алгоритмів на графах. Це відбувається тому, що такі завдання можуть бути переформуліровани в термінах теорії графів.
Теорія графів містить величезну кількість визначень, теорем і алгоритмів. І тому даний матеріал не може претендувати, і не претендує, на повноту охоплення матеріалу. Однак, на думку автора, пропоновані відомості є хорошим компромісом між обсягом матеріалу і його "коефіцієнтом корисної дії" в практичному програмуванні та вирішенні олімпіадних завдань. p> Іноді вирішення основного завдання доводиться формулювати в термінах кілька модифікованих підзадач. Саме такі проблеми розглядаються в даній роботі. b>
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 (n-k, 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;
<...
