Алгоритми і структури даних
Побудова і аналіз алгоритмів, їх покрокове проектування, визначення ефективності. Ряд алгоритмів пошуку даних, які виконуються на статичних структурах, алгоритми сортування. Програмна ілюстрація різних видів пошуку. Методи швидкого доступу до даних.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курс лекций |
| Язык | украинский |
| Дата добавления | 03.11.2011 |
| Размер файла | 372,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Порядок алгоритму якісно лінійний - O(N), для сортування потрібно D*N операцій аналізу цифри. Проте, в такій оцінці порядку не враховується ряд обставин.
По-перше, операція виділення значущої цифри буде простою і швидкою тільки при P=2, для інших систем числення ця операція може вимагати значно більше часу, ніж операція порівняння.
По-друге, при оцінці алгоритму не враховуються затрати часу і пам'яті на створення і ведення груп. Розміщення груп в статичній робочій пам'яті вимагає пам'яті для P*N елементів, оскільки в граничному випадку всі елементи можуть потрапити в якусь одну групу. Якщо ж формувати групи усередині тієї ж послідовності за принципом обмінних алгоритмів, то виникає необхідність перерозподілу послідовності між групами і всі проблеми і недоліки, властиві алгоритмам включення. Найбільш раціональним є формування груп у вигляді зв'язних списків з динамічним виділенням пам'яті.
У наступному прикладі застосовуємо порозрядне сортування до статичної структури даних і формуємо групи на тому ж місці, де розташована початкова послідовність. Приклад вимагає деяких пояснень.
Ділянка пам'яті, займана масивом перерозподіляється між вхідною і вихідною множинами, як це робилося і у ряді попередніх прикладів. Вихідна множина (вона розміщується на початку масиву) розбивається на групи. Розбиття відстежується в масиві b. Елемент масиву b[і] містить індекс в масиві a, з якого починається і+1-а група. Номер групи визначається значенням аналізованої цифри числа. Коли чергове число вибирається з вхідної множини і повинне бути занесене в і-ту групу вихідної множини, воно буде записано в позицію, яка визначається значенням b[і]. Але заздалегідь ця позиція повинна бути звільнена: ділянка масиву від b[і] до кінця вихідної множини включно зсовується в право. Після запису числа в і-ту групу і-те і всі подальші значення в масиві b коректуються - збільшуються на 1.
// Цифрове сортування (розподіл)
int const D=4; // максимальна кількість цифр в числі
int const P=10; // основа системи счислення
// повертає значення n-ої цифри в числі v
int Digit(int v, int n)
{
for ( int i=n; i>0;i-- )
v = v / P;
return v % P;
}
void Sort(int *a)
{
int b[P]; // індекс елемента наступного за останнім в і-ій групі
int i, j, k, m, x;
for ( m=0; m<D; m++ ) // перебір цифр, починаючи з молодшої
{
for ( i=0; i<P; i++ )
b[i] = 0; // початокове значення індексів
for ( i=0; i<N; i++ ) // перебір масиву
{
k = Digit(a[i],m); // визначення m-ої цифри
x = a[i];
// зсув - звільнення місця в кінці k-ої групи
for ( j=i; j>b[k]; j-- )
a[j] = a[j-1];
// запис в кінець k-ої групи
a[b[k]] = x;
// модифікація k-го індексу і всіх більших
for ( j=k; j<P; j++ )
b[j] = b[j]+1;
}
}
}
2.4.2 Швидке сортування Хоара
Даний алгоритм відноситься до розподільних і забезпечує показники ефективності O(N*log2(N)) навіть при якнайгіршому початковому розподілі.
Використовується два індекси - і і j - з початковими значеннями 0 і N-1 відповідно. Ключ K[і] порівнюється з ключем K[j]. Якщо ключі задовольняють критерію впорядкованості, то індекс j зменшується на 1 і проводиться наступне порівняння. Якщо ключі не задовольняють критерію, то записи R[і] і R[j] міняються місцями. При цьому індекс j фіксується і починає мінятися індекс і (збільшуватися на 1 після кожного порівняння). Після наступної перестановки фіксується і і починає змінюватися j і т.д. Прохід закінчується, коли індекси і і j стають рівними. Запис, що знаходиться на позиції зустрічі індексів, стоїть на своєму місці в послідовності. Цей запис ділить послідовність на дві підмножини. Всі записи, розташовані ліворуч від неї мають ключі, менші ніж ключ цього запису, всі записи праворуч - більші. Той же самий алгоритм застосовується до лівої підмножини, а потім до правої. Записи підмножини розподіляються на дві менші підмножини і так далі. Розподіл закінчується, коли отримана підмножина буде складатися з єдиного елемента - така підмножина вже є впорядкованою.
Процедура сортування в наступному прикладі рекурсивна. При її виклику повинні бути задані значення меж сортованої ділянки від 0 до N-1.
// Швидке сортування Хоара
void Sort(int *a, int i0, int j0)
// і0, j0 - межі сортованої ділянки
{
int i, j; // поточні індекси в масиві
bool flag; // ознака змінного індексу:
// якщо flag=true - зменшується j, інакше - збільшується і
if ( j0 <= i0 )
return; // підмножина порожня або з 1 eл-та
i = i0;
j = j0;
flag = true; // спочатку буде змінюватися j
while ( i < j )
{
if ( a[i] > a[j] )
{
Swap(a[i], a[j]); // перестановка
// після перестановки міняється змінний індекс
flag = !flag;
}
// реально змінюється тільки один індекс
if (flag)
j--;
else
i++;
}
Sort(a, i0, i-1); // сортування лівого підмасиву
Sort(a, i+1, j0); // сортування правого підмасиву
}
2.5 Сортування злиттям
Алгоритми сортування злиттям, як правило, мають порядок O(N*log2(N)), але відрізняються від інших алгоритмів більшою складністю і вимагають великої кількості пересилок. Алгоритми злиття застосовуються в основному, як складова частина зовнішнього сортування. Тут же для розуміння принципу злиття приведемо найпростіший алгоритм злиття в оперативній пам'яті.
2.5.1 Сортування попарним злиттям
Вхідна множина розглядається, як послідовність підмножин, кожна з яких складається з єдиного елемента і, отже, є вже впорядкованим. На першому проході кожні дві сусідні одноелементних множини зливаються в одну двоелементну впорядковану множину. На другому проході двоелементні множини зливаються в 4-елементні впорядковані множини і т.д. Врешті-решт отримують одну велику впорядковану множину.
Самою найважливішою частиною алгоритму є злиття двох впорядкованих множин. Цю частину алгоритму опишемо більш детально.
1. Початкові установки. Визначити довжини першої і другої початкових множин - l1 і l2 відповідно. Встановити індекси поточних елементів в початковій множині і1 і і2 в 0. Встановити індекс в вихідній множині j=1.
2. Цикл злиття. Виконувати крок 3 до тих пір, поки і1<=l1 і і2<=l2.
3. Порівняння. Порівняти ключ і1-го елемента з першої початкової множини з ключем і2-го елемента з другої початкової множини. Якщо ключ елемента з 1-ої множини менший, то записати і1-тий елемент з 1-ої множини на j-те місце в вихідній множині і збільшити і1 на 1. Інакше - записати і2-тий елемент з 2-ої множини на j-те місце в вихідній множині і збільшити і2 на 1. Збільшити j на 1.
4. Виведення залишків. Якщо і1<=l1, то переписати частину 1-ої початкової множини від і1 до l1 включно в вихідну множину. Інакше - переписати частину 2-ої початкової множини від і2 до l2 включно в вихідну множину.
2.6 Рандомізація
В деяких програмах потрібно виконання операцій, протилежних сортуванню. Отримавши множину елементів, програма повинна розмістити їх у випадковому порядку. Рандомізацію нескладно виконати, використовуючи алгоритм, подібний на сортування вибіркою.
Для кожного розміщення в множині, алгоритм випадковим чином вибирає елемент, який повинен його зайняти з тих, які ще не були розміщені на своєму місці. Потім цей елемент міняється місцями з елементом, який, знаходиться на цій позиції. Так як алгоритм заповнює кожну позицію лише один раз, його складність - O(N).
Нескладно показати, що імовірність того, що елемент виявиться на якій-небудь позиції, рівна 1/N. Оскільки елемент може виявитися на будь-якій позиції з однаковою імовірністю, цей алгоритм дійсно приводить до випадкового розміщення елементів.
Результат рандомізації залежить від того, наскільки ефективним є генератор випадкових чисел. Для даного алгоритми не важливий початковий порядок розміщення елементів. Якщо необхідно неодноразово рандомізувати множину елементів, немає необхідності її попередньо сортувати.
Приведемо простий приклад функції рандомізації вектору цілих чисел.
void UnSort(int *a)
{
int i, pos;
for (i=0; i<N; i++)
{
pos = i + rand() %(N - i);
Swap(a[pos], a[i]);
}
}
Зауважимо, що перед використанням функції отримання випадкового числа - rand(), доцільно викликати функцію ініціалізації генератора випадкових чисел - randomize().
3. АЛГОРИТМИ пошуку
Одна з тих дій, які найбільш часто зустрічаються в програмуванні - пошук. Існує декілька основних варіантів пошуку, і для них створено багато різноманітних алгоритмів.
Задача пошуку - відшукати елемент, ключ якого рівний заданому „аргументу пошуку”. Отриманий в результаті цього індекс забезпечує доступ до усіх полів виявленого елемента.
3.1 Послідовний (лінійний) пошук
Найпростішим методом пошуку елемента, який знаходиться в неврегульованому наборі даних, за значенням його ключа є послідовний перегляд кожного елемента набору, який продовжується до тих пір, поки не буде знайдений потрібний елемент. Якщо переглянуто весь набір, і елемент не знайдений - значить, шуканий ключ відсутній в наборі. Цей метод ще називають методом повного перебору.
Для послідовного пошуку в середньому потрібно N/2 порівнянь. Таким чином, порядок алгоритму - лінійний - O(N).
Програмна ілюстрація лінійного пошуку в неврегульованому масиві приведена в наступному прикладі, де a - початковий масив, key - ключ, який шукається; функція повертає індекс знайденого елемента.
int LinSearch(int *a, int key)
{
int i = 0;
while ( (i<N) && (a[i] != key) )
i++;
return i;
}
Якщо елемент знайдено, то він знайдений разом з мінімально можливим індексом, тобто це перший з таких елементів. Рівність i=N засвідчує, що елемент відсутній.
Єдина модифікація цього алгоритму, яку можна зробити, - позбавитися перевірки номера елементу масиву в заголовку циклу (i<N) за рахунок збільшення масиву на один елемент у кінці, значення якого перед пошуком встановлюють рівним шуканому ключу - key - так званий „бар'єр”.
int LinSearch(int *a, int key)
{
a[N] = key;
i = 0;
while (a[i] != key)
i++;
return i; // i<N - повернення номера елемента
}
3.2 Бінарний пошук
Очевидно, що інших способів пришвидшення пошуку не існує, якщо, звичайно, немає ще якої-небудь інформації про дані, серед яких ведеться пошук. Алгоритм пошук може бути значно ефективнішим, якщо дані будуть впорядковані.
Іншим, відносно простим, методом доступу до елемента є метод бінарного (дихотомічного) пошуку, який виконується в явно впорядкованій послідовності елементів. Записи в таблицю заносяться в лексикографічному (символьні ключі) або чисельно (числові ключі) зростаючому порядку. Для досягнення впорядкованості може бути використаний котрийсь з методів сортування, які розглянемо пізніше.
Оскільки шуканий елемент швидше за все знаходиться „десь в середині”, перевіримо саме середній елемент: a[N / 2] == key? Якщо це так, то знайдено те, що потрібно. Якщо a[N / 2] < key , то значення i = N / 2 є замалим і шуканий елемент знаходиться „праворуч”, а якщо a[N / 2] > key, то „ліворуч”, тобто на позиціях 0 … i.
Для того, щоб знайти потрібний запис в таблиці, у гіршому випадку потрібно log2(N) порівнянь. Це значно краще, ніж при послідовному пошуку.
Приведемо ілюстрація бінарного пошуку на прикладі.
int BinSearch(int *a, int key)
{
int b, e, i;
b = 0; e = N-1; // початкові значення меж
bool Found = false; // прапорець
while ( (b < e) && !Found) // цикл, поки інтервал пошуку не звузиться до 0
{
i = ( b + e ) / 2; // середина інтервалу
if ( a[i] == key )
Found = true; // ключ знайдений
else
if ( a[i] < key )
b = i + 1; // пошук в правому підінтервалі
else
e = i - 1; // пошук в лівому підінтервалі
}
return i;
}
Максимальна кількість порівнянь для цього алгоритму рівна log2(N). Таким чином, приведений алгоритм суттєво виграє у порівнянні з лінійним пошуком.
Ефективність дещо покращиться, якщо поміняти місцями заголовки умовних операторів. Перевірку на рівність можна виконувати в другу чергу, так як вона зустрічається лише одноразово і приводить до завершення роботи. Але більш суттєвий виграш дасть відмова від завершення пошуку при фіксації знаходження елемента.
int BinSearch(int *a, int key)
{
int b, e, i;
b = 0; e = N-1;
while (b<e)
{
i = (b + e) / 2;
if (а[m] < x)
b = i + 1;
else
e = i - 1;
}
return i
}
Завершення циклу гарантовано. Це пояснюється наступним. На початку кожного кроку b<e. Для середнього арифметичного i справедлива умова b<=i<e. Значить, різниця e-b дійсно спадає, тому що або b збільшується при присвоєнні йому значення i+1, або e зменшується при присвоєнні йому значення i-1. При b<=i повторення циклу закінчується.
Виконання умови b=e ще не засвідчує знаходження потрібного елемента. Тут потрібна додаткова перевірка. Також, необхідно враховувати, що елемент a[e] у порівняннях ніколи не бере участі. Значить, і тут необхідна додаткова перевірка на рівність a[e]=key. Але ці перевірки виконуються однократно.
Алгоритм бінарного пошуку можна представити і трохи інакше, використовуючи рекурсивний опис. В цьому випадку граничні індекси інтервалу b і e є параметрами алгоритму. Рекурсивна процедура бінарного пошуку представлена в наступній програмі. Для виконання пошуку необхідно при виклику процедури задати значення її формальних параметрів b і е - 0 і N-1 відповідно, де b, e - граничні індекси області пошуку.
int BinSearch(int *a, int key, int & b, int & e)
{
int i;
if ( b > e )
return -1; // перевірка ширини інтервалу
else
{
i = ( b + e ) / 2; // середина інтервалу
if ( a[i] == key )
return i; // ключ знайдений, повернення індексу
else
if ( a[i] < key ) // пошук в правому підінтервалі
return BinSearch(a, key, i+1, e);
else // пошук в лівому підінтервалі
return BinSearch(a, key, b, i-1);
}
}
Відомо, також, декілька модифікацій алгоритму бінарного пошуку, які виконуються на деревах.
3.3 Метод інтерполяції
Якщо немає ніякої додаткової інформації про значення ключів, крім факту їхнього впорядкування, то можна припустити, що значення key збільшуються від a[0] до a[N-1] більш-менш „рівномірно”. Це означає, що значення середнього елементу a[N / 2] буде близьким до середнього арифметичного між найбільшим та найменшим значенням. Але, якщо шукане значення key відрізняється від вказаного, то є деякий сенс для перевірки брати не середній елемент, а „середньо-пропорційний”, тобто такий, номер якого пропорційний значенню key:
Програмна реалізація такого варіанту пошуку матиме вигляд:
int BinSearch(int *a, int key)
{
int b, e, i;
b = 0; e = N-1; // початкові значення меж
while ( b < e ) // цикл, поки інтервал пошуку не звузиться до 0
{
i = b + (key - a[b])*(e-b) / (a[e] - a[b]);
if ( a[i] == key )
return i; // ключ знайдений - повернення індексу
else
if ( a[i] < key )
b = i + 1; // пошук в правому підінтервалі
else
e = i - 1; // пошук в лівому підінтервалі
}
return -1; // ключ не знайдений
}
Вираз для поточного значення i одержано з пропорційності відрізків на рисунку:
В середньому цей алгоритм має працювати швидше за бінарний пошук, але у найгіршому випадку буде працювати набагато довше.
3.4 Метод „золотого перерізу”
Деякий ефект дає використання так званого „золотого перерізу”. Це число , що має властивість:
Доданій корінь і є золотим перерізом.
Згідно цього алгоритму відрізок b … e слід ділити не навпіл, як у бінарному алгоритмі, а на відрізки, пропорційні та 1, в залежності від того, до якого краю ближче key. Замість оператора
i = …;
у програму бінарного пошуку слід внести наступний фрагмент, попередньо визначивши константу Phi:
if a[e] - key < key - a[b]
i = b + (e - b) * (Phi - 1);
else
i = e - (e - b) * (Phi - 1) + 1;
3.5 Алгоритми пошуку послідовностей
Даний клас задача відноситься до задачі пошуку слів у тексті. Нехай масив a[N] вважається масивом символів останній елемент якого - 0:
char a[N];
у якому слід знайти заданий рядок символів: довжиною m.
3.5.1 Прямий алгоритм пошуку
Одним з найпростіших методів пошуку є послідовне порівняння першого символу s з символами масиву a. Якщо наявний збіг, тоді порівнюються другі, треті,... символи аж до повного збігу рядка s з частиною вектору такої ж довжини, або до незбігу у деякому символі. Тоді пошук продовжується з наступного символу масиву a та першого символу рядку s. Це визначається елементарною програмою:
i = 0; // номер символу масиву a
while (i < N - lenghts)
{
j = 0; // номер символу рядка s
while ((s[j] == a[i+j]) && (j<lenghts)
j++;
if (j==lenghts)
return i; // успіх
}
Якщо збіги відбуватимуться досить часто, то час роботи програми може бути досить значним.
Існує варіант удосконалення цього алгоритму - це починати пошук після часткового збігу не з наступного елементу масиву, а з символу, наступного після тих, що переглядалися, якщо у рядку s немає фрагментів, що повторюються.
j = 0; // j - номер символа у a
found = false;
while (!found)
{
i = 0; // i - номер символа у s
while ((s[i] == a[j]) && (s[i] != `/0')
{
i++;
j++;
};
if (s[i] == `/0'
found = true;
else
j -= i-1;
};
3.5.2 Алгоритм Кнута, Моріса, Пратта
Д. Кнут, Д. Моріс і В. Пратт винайшли алгоритм, який фактично потребує лише N порівнянь навіть в самому поганому випадку. Новий алгоритм базується на тому, що після часткового збігу початкової частини слова з відповідними символами тексту фактично відома пройдена частина тексту і можна „обчислити” деякі відомості (на основі самого слова), за допомогою яких потім можна швидко пересунутися текстом. Приведений приклад пошуку слова ABCABD показує принцип роботи такого алгоритму. Символи, які пройшли порівняння, - підкреслені. Зверніть увагу: при кожному незбігу пари символів слово зсовується на всю пройдену відстань, оскільки менші зсуви не можуть привести до повного збігу.
ABCABCABAABCABD
ABCABD
ABCABD
ABCABD
ABCABD
ABCABD
Основною відмінністю КМП-алгоритму від алгоритму прямого пошуку є здійснення зсуву слова не на один символ на кожному кроці алгоритму, а на деяку змінну кількість символів. Таким чином, перед тим як виконувати черговий зсув, потрібно визначити величину зсуву. Для підвищення ефективності алгоритму необхідно, щоб зсув на кожному кроці був би якомога більшим.
Якщо j визначає позицію в слові, в якій міститься перший символ, який не збігається (як в алгоритмі прямого пошуку), то величина зсуву визначається як j-D. Значення D визначається як розмір самої довшої послідовності символів слова, які безпосередньо передують позиції j, яка повністю збігається з початком слова. D залежить тільки від слова і не залежить від тексту. Для кожного j буде своя величина D, яку позначимо dj.
Так як величини dj залежать лише від слова, то перед початком фактичного пошуку можна обчислити допоміжну таблицю d; ці обчислення зводяться до деякої попередньої трансляції слова. Відповідні зусилля будуть оправдані, якщо розмір тексту значно перевищує розмір слова (M<<N). Якщо потрібно шукати багатократні входження одного й того ж слова, то можна користуватися одними й тими ж d. Наведені приклади пояснюють функцію d.
|
Текст |
A |
A |
A |
A |
С |
j=5; d[5]=4; max_shift=j-d[5]=1 |
||||||
|
Слово |
А |
А |
А |
А |
В |
|||||||
|
Зсунуте слово |
А |
А |
А |
А |
В |
|||||||
|
Текст |
A |
B |
C |
A |
В |
D |
j=5; d[5]=2; max_shift=j-d[5]=3 |
|||||
|
Слово |
А |
B |
C |
A |
В |
С |
||||||
|
Зсунуте слово |
A |
B |
C |
A |
B |
С |
||||||
|
Текст |
A |
B |
C |
D |
E |
A |
j=5; d[5]=0; max_shift=j-d[5]=5 |
|||||
|
Слово |
А |
B |
C |
D |
E |
F |
||||||
|
Зсунуте слово |
A |
B |
C |
D |
Розглянемо програмну реалізацію цього методу.
int d[M];
j = 0;
k = -1;
d[0] = -1;
while (i < M-1) // попереднє заповнення масиву d зсувів
{
while ((k>=0) && (s[i] != s[k]))
k = d[k];
i++;
k++;
if (s[i] == s[k])
d[i] = d[k]
else
d[i] = k;
}
i = 0;
j = 0;
k = 0;
while ((i < M) && (j < N))
{
while (k <= j)
{
cout << a[k];
k++;
}
while ((i>=0) && (a[j] != s[i])
i = d[i];
j++;
i++;
}
if (i == M)
; // Успіх!
3.5.3 Алгоритм Боуєра та Мура
КМП-пошук дає справжній виграш тільки тоді, коли невдачі передувала деяка кількість збігів. Лише у цьому випадку слово зсовується більше ніж на одиницю. На жаль, це швидше виняток, ніж правило: збіги зустрічаються значно рідше, ніж незбіги. Тому виграш від практичного використання КМП-стратегії в більшості випадків пошуку в звичайних текстах досить незначний. Метод, який запропонували Р. Боуєр і Д. Мур в 1975 р., не тільки покращує обробку самого поганого випадку, але й дає виграш в проміжних ситуаціях.
БМ-пошук базується на незвичних міркуваннях - порівняння символів починається з кінця слова, а не з початку. Як і у випадку КМП-пошуку, слово перед фактичним пошуком трансформується в деяку таблицю. Нехай для кожного символу x із алфавіту величина dx - відстань від самого правого в слові входження x до правого кінця слова. Уявимо, що виявлена розбіжність між словом і текстом. У цьому випадку слово відразу ж можна зсунути праворуч на dpM-1 позицій, тобто на кількість позицій, швидше за все більше одиниці. Якщо символ, який не збігся, тексту в слові взагалі не зустрічається, то зсув стає навіть більшим, а саме зсовувати можна на довжину всього слова. Ось приклад, який ілюструє цей процес:
ABCABCABFABCABD
ABCABD
ABCABD
ABCABD
На початку роботи слід завести масив, який зберігав би для кожного символу, що може зустрітися у масиві a, значення зсуву. Для символів, що взагалі не зустрічаються у образі s, зсув дорівнює M - довжині образу. Для символів, що зустрічаються у s, зсув буде меншим, щоби не пропустити можливих попадань.
Програму можна записати таким чином.
for (ch=0; ch<256; ch++)
d[ch] = M; // замовчування
for (i=0; i<M-1; i++)
d[s[i]] = M-i-1; // уточнення
// Поиск слова p в тексте s
i = M;
do
{
j = M;
k = i;
do // Цикл порівняння символів
{
k--;
j---; // слова, начинаючи з правого
while ( (j<0) || (a[j]!=s[k]) ); //Вихід, при порівн. все слово або незбіг
i += d[s[i-1]]; // Зсув слова вправо
while ( (j<0) || (i>N));
У випадку постійних незбігів цей алгоритм робить одне порівняння на M символів.
Варто сказати, що запропоновані методи пошуку послідовностей можна модифікувати таким чином, щоб у кожному рядку пошук йшов не до кінця кожного рядка, а на кількість шуканих символів менше, бо слово s не може бути розташоване у кінці одного рядка та на початку наступного.
4. Методи швидкого доступу до даних
4.1 Хешування даних
Для прискорення доступу до даних можна використовувати попереднє їх впорядкування у відповідності зі значеннями ключів. При цьому можуть використовуватися методи пошуку в упорядкованих структурах даних, наприклад, метод дихотомічного пошуку, що суттєво скорочує час пошуку даних за значенням ключа. Проте при добавленні нового запису потрібно дані знову впорядкувати. Втрати часу на повторне впорядкування можуть значно перевищувати виграш від скорочення часу пошуку. Тому для скорочення часу доступу до даних використовується так зване випадкове впорядкування або хешування. При цьому дані організуються у вигляді таблиці за допомогою хеш-функції h, яка використовується для „обчислення” адреси за значенням ключа.
У попередній главі описувався алгоритм інтерполяційного пошуку, який використовує інтерполяцію для пришвидшення пошуку. Порівнюючи шукане значення зі значеннями елементів у відомих точках, цей алгоритм може визначити імовірне розміщення шуканого елемента. По суті, він створює функцію, яка встановлює відповідність між шуканим значенням і індексом позиції, в якій він повинен знаходитися. Якщо перше передбачення помилкове, то алгоритм знову використовує цю функцію, передбачаючи нове розміщення, і так далі, до тих пір, поки шуканий елемент не буде знайдено.
Хешування використовує аналогічний підхід, відображаючи елементи в хеш-таблиці. Алгоритм хешування використовує деяку функцію, яка визначає імовірне розміщення елемента в таблиці на основі значення шуканого елементу.
Ідеальною хеш-функцією є така хеш-функція, яка для будь-яких двох неоднакових ключів дає неоднакові адреси. Підібрати таку функцію можна у випадку, якщо всі можливі значення ключів відомі наперед. Така організація даних носить назву „досконале хешування”.
Наприклад, потрібно запам'ятати декілька записів, кожен з яких має унікальний ключ зі значенням від 1 до 100. Для цього можна створити масив з 100 комірками і присвоїти кожній комірці нульовий ключ. Щоб добавити в масив новий запис, дані з нього просто копіюються у відповідну комірку масиву. Щоб добавити запис з ключем 37, дані з нього копіюються в 37 позицію в масиві. Щоб знайти запис з певним ключем - вибирається відповідна комірка масиву. Для вилучення запису ключу відповідної комірки масиву просто присвоюється нульове значення. Використовуючи цю схему, можна добавити, знайти і вилучити елемент із масиву за один крок.
У випадку наперед невизначеної множини значень ключів і обмеженні розміру таблиці підбір досконалої функції складний. Тому часто використовують хеш-функції, які не гарантують виконанні умови.
Наприклад, база даних співробітників може використовувати в якості ключа ідентифікаційний номер. Теоретично можна було б створити масив, кожна комірка якого відповідала б одному з можливих чисел; але на практиці для цього не вистарчить пам'яті або дискового простору. Якщо для зберігання одного запису потрібно 1 КБ пам'яті, то такий масив зайняв би 1 ТБ (мільйон МБ) пам'яті. Навіть якщо можна було б виділити такий об'єм пам'яті, така схема була б дуже неекономною. Якщо штат фірми менше 10 мільйонів співробітників, то більше 99 процентів масиву буде пустою.
Щоб вирішити цю проблему, схеми хешування відображають потенційно велику кількість можливих ключів на достатньо компактну хеш-таблицю. Якщо на фірмі працює 700 співробітників, можна створити хеш-таблицю з 1000 комірок. Схема хешування встановлює відповідність між 700 записами про співробітників і 1000 позиціями в таблиці. Наприклад, можна розміщати записи в таблиці у відповідності з трьома першими цифрами ідентифікаційного номеру. При цьому запис про співробітника з номером 123456789 буде знаходитися в 123 комірці таблиці.
Очевидно, що оскільки існує більше можливих значень ключа, ніж комірок в таблиці, то деякі значення ключів можуть відповідати одним і тим коміркам таблиці. Даний випадок носить назву „колізія”, а такі ключі називаються „ключі-синоніми”.
Щоб уникнути цієї потенційної проблеми, схема хешування повинна включати в себе алгоритм вирішення конфліктів, який визначає послідовність дій у випадку, якщо ключ відповідає позиції в таблиці, яка вже зайнята іншим записом.
Усі методи використовують для вирішення конфліктів приблизно однаковий підхід. Вони спочатку встановлюють відповідність між ключем запису і розміщенням в хеш-таблиці. Якщо ця комірка вже зайнята, вони відображають ключ на іншу комірку таблиці. Якщо вона також вже зайнята, то процес повторюється знову до тих пір, поки нарешті алгоритм не знайде пусту комірку в таблиці. Послідовність позицій, які перевіряються при пошуку або вставці елемента в хеш-таблицю, називається тестовою послідовністю.
В результаті, для реалізації хешування необхідні три речі:
Структура даних (хеш-таблиця) для зберігання даних;
Функція хешування, яка встановлює відповідність між значеннями ключа і розміщенням в таблиці;
Алгоритм вирішення конфліктів, який визначає послідовність дій, якщо декілька ключів відповідають одній комірці таблиці.
4.1.1 Методи розв'язання колізій
Для розв'язання колізій використовуються різноманітні методи, які в основному зводяться до методів „ланцюжків” і „відкритої адресації”.
Методом ланцюжків називається метод, в якому для розв'язання колізій у всі записи вводяться покажчики, які використовуються для організації списків - „ланцюжків переповнення”. У випадку виникнення колізій при заповненні таблиці в список для потрібної адреси хеш-таблиці добавляється ще один елемент.
Пошук в хеш-таблиці з ланцюжками переповнення здійснюється наступним чином. Спочатку обчислюється адреса за значенням ключа. Потім здійснюється послідовний пошук в списку, який зв'язаний з обчисленим адресом. Процедура вилучення з таблиці зводиться до пошуку елемента в його вилучення з ланцюжка переповнення. Схематичне зображення хеш-таблиці при такому методі розв'язання колізій приведене на наступному рисунку.
Якщо сегменти приблизно однакові за розміром, то у цьому випадку списки усіх сегментів повинні бути найбільш короткими при даній кількості сегментів. Якщо вихідна множина складається з N елементів, тоді середня довжина списків буде рівна N/B елементів. Якщо можна оцінити N і вибрати B якомога ближчим до цієї величини, то в списку буде один-два елементи. Тоді час доступу до елемента множини буде малою постійною величиною, яка залежить від N.
Одна з переваг цього методу хешування полягає в тому, що при його використанні хеш-таблиці ніколи не переповнюються. При цьому вставка і пошук елементів завжди виконується дуже просто, навіть якщо елементів в таблиці дуже багато. Із хеш-таблиці, яка використовує зв'язування, також просто вилучати елементи, при цьому елемент просто вилучається з відповідного зв'язного списку.
Один із недоліків зв'язування полягає в тому, що якщо кількість зв'язних списків недостатньо велика, то розмір списків може стати великим, при цьому для вставки чи пошуку елемента необхідно буде перевірити велику кількість елементів списку.
Метод відкритої адресації полягає в тому, щоб, користуючись якимось алгоритмом, який забезпечує перебір елементів таблиці, переглядати їх в пошуках вільного місця для нового запису.
Лінійне випробування зводиться до послідовного перебору елементів таблиці з деяким фіксованим кроком
a=h(key) + c*i ,
де i - номер спроби розв'язати колізію. При кроці рівному одиниці відбувається послідовний перебір усіх елементів після поточного.
Квадратичне випробування відрізняється від лінійного тим, що крок перебору елементів нелінійно залежить від номеру спроби знайти вільний елемент
a = h(key2) + c*i + d*i2
Завдяки нелінійності такої адресації зменшується кількість спроб при великій кількості ключів-синонімів. Проте навіть відносно невелика кількість спроб може швидко привести до виходу за адресний простір невеликої таблиці внаслідок квадратичної залежності адреси від номеру спроби.
Ще один різновид методу відкритої адресації, яка називається подвійним хешуванням, базується на нелінійній адресації, яка досягається за рахунок сумування значень основної і додаткової хеш-функцій.
a=h1(key) + i*h2(key).
Розглянемо алгоритми вставки і пошуку для методу лінійного випробування.
Вставка:
1. i = 0
2. a = h(key) + i*c
3. Якщо t(a) = вільно, то t(a) = key, записати елемент і зупинитися
4. i = i + 1, перейти до кроку 2
Пошук:
1. i = 0
2. a = h(key) + i*c
3. Якщо t(a) = key, то зупинитися - елемент знайдено
4. Якщо t(a) = вільно, то зупинитися - елемент не знайдено
5. i = i + 1, перейти до кроку 2
Аналогічно можна було б сформулювати алгоритми добавлення і пошуку елементів для будь-якої схеми відкритої адресації. Відмінності будуть лише у виразі, який використовується для обчислення адреси (крок 2).
З процедурою вилучення справа складається не так просто, так як вона в даному випадку не буде оберненою до процедури вставки. Справа в тому, що елементи таблиці знаходяться в двох станах: вільно і зайнято. Якщо вилучити елемент, перевівши його в стан вільно, то після такого вилучення алгоритм пошуку буде працювати некоректно. Нехай ключ елемента, який вилучається, має в таблиці ключі синоніми. У цьому випадку, якщо за ним в результаті розв'язання колізій були розміщені елементи з іншими ключами, то пошук цих елементів після вилучення завжди буде давати негативний результат, так як алгоритм пошуку зупиняється на першому елементі, який знаходиться в стані вільно.
Скоректувати цю ситуацію можна різними способами. Самий простий із них полягає в тому, щоб проводити пошук елемента не до першого вільного місця, а до кінця таблиці. Проте така модифікація алгоритму зведе нанівець весь виграш в прискоренні доступу до даних, який досягається в результаті хешування.
Інший спосіб зводиться до того, щоб відслідкувати адреси всіх ключів-синонімів для ключа елемента, що вилучається, і при необхідності розмістити відповідні записи в таблиці. Швидкість пошуку після такої операції не зменшиться, але затрати часу на саме розміщення елементів можуть виявитися значними.
Існує підхід, який не має перерахованих недоліків. Його суть полягає в тому, що для елементів хеш-таблиці добавляється стан „вилучено”. Даний стан в процесі пошуку інтерпретується, як зайнято, а в процесі запису як вільно.
Тепер можна сформулювати алгоритми вставки, пошуку і вилучення для хеш-таблиці, яка має три стани елементів.
Вставка:
1. i = 0
2. a = h(key) + i*c
3. Якщо t(a) = вільно або t(a) = вилучено, то t(a) = key, записати елемент і стоп
4. i = i + 1, перейти до кроку 2
Вилучення:
1. i = 0
2. a = h(key) + i*c
3. Якщо t(a) = key, то t(a) = вилучено, стоп елемент вилучений
4. Якщо t(a) = вільно, то стоп елемент не знайдено
5. i = i + 1, перейти до кроку 2
Пошук:
1. i = 0
2. a = h(key) + i*c
3. Якщо t(a) = key, то стоп - елемент знайдено
4. Якщо t(a) = свободно, то стоп - елемент не знайдено
5. i = i + 1, перейти до кроку 2
Алгоритм пошуку для хеш-таблиці, яка має три стани, практично не відрізняється від алгоритму пошуку без врахування вилучення. Різниця полягає в тому, що при організації самої таблиці необхідно відмічати вільні і вилучені елементи. Це можна зробити, зарезервувавши два значення ключового поля. Інший варіант реалізації може передбачати введення додаткового поля, в якому фіксується стан елемента. Довжина такого поля може складати всього два біти, що достатньо для фіксації одного з трьох станів.
4.1.2 Переповнення таблиці і повторне хешування
Очевидно, що в міру заповнення хеш-таблиці будуть відбуватися колізії і в результаті їх розв'язання методами відкритої адресації чергова адреса може вийти за межі адресного простору таблиці. Щоб це явище відбувалося рідше, можна піти на збільшення розмірів таблиці у порівнянні з діапазоном адрес, які обчислюються хеш-функцією.
З однієї сторони це приведе до скорочення кількості колізій і прискоренню роботи з хеш-таблицею, а з іншої - до нераціональних витрат адресного простору. Навіть при збільшенні таблиці в два рази у порівнянні з областю значень хеш-функції нема гарантій того, що в результаті колізій адреса не перевищить розмір таблиці. При цьому в початковій частині таблиця може залишатися достатньо вільних елементів. Тому на практиці використовують циклічний перехід на початок таблиці.
Розглянемо даний спосіб на прикладі методу лінійного випробування. При обчисленні адреси чергового елементу можна обмежити адресу, взявши в якості такої остачу від цілочисельного ділення адреси на довжину таблиці N.
Вставка:
1. i = 0
2. a = (h(key) + c*i) % N
3. Якщо t(a) = вільно або t(a) = вилучено то t(a) = key, записати елемент і стоп
4. i = i + 1, перейти до кроку 2
В даному алгоритмі не враховується можливість багатократного перевищення адресного простору. Більш коректним буде алгоритм, який використовує зсув адреси на 1 елемент у випадку кожного повторного перевищення адресного простору. Це підвищує імовірність знаходження вільного елемента у випадку повторних циклічних переходів до початку таблиці.
Вставка:
1. i = 0
2. a = ((h(key) + c*i) / n + (h(key) + c*i) % n) % n
3. Якщо t(a) = вільно або t(a) = вилучено, то t(a) = key, записати елемент і стоп
4. i = i + 1, перейти до кроку 2
Розглядаючи можливість виходу за межі адресного простору таблиці, ми не враховували фактори наповненості таблиці й вдалого вибору хеш-функції. При великій наповненості таблиці виникають часті колізії і циклічні переходи на початок таблиці. При невдалому виборі хеш-функції відбуваються аналогічні явища. В найгіршому випадку при повному заповнені таблиці алгоритми циклічного пошуку вільного місця приведуть до зациклювання. Тому при використанні хеш-таблиць необхідно старатися уникати дуже густого заповнення таблиць. Звичайно довжину таблиці вибирають із розрахунку дворазового перевищення передбачуваної максимальної кількості записів. Не завжди при організації хешування можна правильно оцінити потрібну довжину таблиці, тому у випадку великої наповненості таблиці може знадобитися рехешування. У цьому випадку збільшують довжину таблиці, змінюють хеш-функцію і впорядковують дані.
Проводити окрему оцінку густини заповнення таблиці після кожної операції вставки недоцільно, тому можна проводити таку оцінку непрямим способом - за кількістю колізій під час однієї вставки. Достатньо визначити деякий поріг кількості колізій, при перевищенні якого потрібно провести рехешування. Крім того, така перевірка гарантує неможливість зациклювання алгоритму у випадку повторного перегляду елементів таблиці. Розглянемо алгоритм вставки, який реалізує описаний підхід.
Вставка:
1. i = 0
2. a = ((h(key) + c*i) / n + (h(key) + c*i) % n) % n
3. Якщо t(a) = вільно або t(a) = вилучено, то t(a) = key, записати елемент і стоп
4. Якщо i > m , то стоп - потрібно рехешування
5. i = i + 1, перейти до кроку 2
В даному алгоритмі номер ітерації порівнюється з пороговим числом m. Варто зауважити, що алгоритми вставки, пошуку і вилучення повинні використовувати ідентичне утворення адреси чергового запису.
Вилучення:
1. i = 0
2. a = ((h(key) + c*i) / n + (h(key) + c*i) % n) % n
3. Якщо t(a) = key, то t(a) = вилучено і стоп елемент вилучено
4. Якщо t(a) = вільно або i>m, то стоп - елемент не знайдено
5. i = i + 1, перейти до кроку 2
Пошук:
1. i = 0
2. a = ((h(key) + c*i) / n + (h(key) + c*i) % n) % n
3. Якщо t(a) = key, то стоп - елемент знайдено
4. Якщо t(a) = вільно або i>m, то стоп - елемент не знайдено
5. i = i + 1, перейти до кроку 2
4.1.3 Оцінка якості хеш-функції
Як вже було відмічено, дуже важливий правильний вибір хеш-функції. При вдалій побудові хеш-функції таблиця заповнюється більш рівномірно, зменшується кількість колізій і зменшується час виконання операцій пошуку, вставки і вилучення. Для того щоб попередньо оцінити якість хеш-функції можна провести імітаційне моделювання.
Моделювання проводиться наступним чином. Формується вектор цілих чисел, довжина якого співпадає з довжиною хеш-таблиці. Випадково генерується достатньо велика кількість ключів, для кожного ключа обчислюється хеш-функція. В елементах вектора підраховується кількість генерацій даної адреси. За результатами такого моделювання можна побудувати графік розподілу значень хеш-функції. Для отримання коректних оцінок кількість генерованих ключів повинна в декілька разів перевищувати довжину таблиці.
Якщо кількість елементів таблиці достатньо велика, то графік будується не для окремих адрес, а для груп адрес. Великі нерівномірності засвідчують високу імовірність колізій в окремих місцях таблиці. Зрозуміло, така оцінка є наближеною, але вона дозволяє попередньо оцінити якість хеш-функції і уникнути грубих помилок при її побудові.
Оцінка буде більше точною, якщо генеровані ключі будуть більш близькими до реальних ключів, які використовуються при заповненні хеш-таблиці. Для символьних ключів дуже важливо добитися відповідності генерованих кодів символів тим кодам символів, які є в реальному ключі. Для цього потрібно проаналізувати, які символи можуть бути використані в ключі.
Наприклад, якщо ключ представляє собою прізвище українською мовою, то будуть використані українські букви. Причому перший символ може бути великою буквою, а інші - малими. Якщо ключ представляє собою номерний знак автомобіля, то також нескладно визначити допустимі коди символів в певних позиціях ключа.
Розглянемо більш загальний випадок. Нехай необхідно генерувати ключ із m символів з кодами в неперервному діапазоні від n1 до n2.
for (i=0; i<m; i++)
str[i]:=(char)(rand()%(n2-n1)+n1);
На практиці можливі варіанти, коли символи в одних позиціях ключа можуть належати до різних діапазонів кодів, причому між цими діапазонами може існувати розрив. Наприклад генерація ключа з m символів з кодами в діапазоні від n1 до n4 (діапазон має розрив від n2 до n3).
for (int i=0; i<m; i++)
{
x = rand() % ((n4-n3)+(n2-n1));
if ( x<=(n2-n1) )
str[i] = (char)(x+n1);
else
str[i] = (char)(x+n1+n3-n2);
}
Розглянемо ще один конкретний приклад. Нехай відомо, що ключ складається з 7 символів. Із них три перші символи - великі латинські букви, далі йдуть дві цифри, інші - малі латинські.
Приклад: довжина ключа 7 символів;
3 великі латинські (коди 65-90);
2 цифри (коди 48-57);
2 малі латинські (коди 97-122).
char key[7];
for (i=0; i<3; i++) key[i] = (char)(rand()%(90-65)+65);
for (i=3; i<5; i++) key[i] = (char)(rand()%(57-48)+57);
for (i=5; i<7; i++) key[i] = (char)(rand{}%(122-97)+97);
4.2 Організація даних для прискорення пошуку за вторинними ключами
До тепер розглядалися способи пошуку в таблиці за ключами, які дозволяють однозначно ідентифікувати запис. Такі ключі називають первинними ключами. Можливий варіант організації таблиці, при якому окремий ключ не дозволяє однозначно ідентифікувати запис. Така ситуація часто зустрічається в базах даних. Ідентифікація запису здійснюється за деякою сукупністю ключів. Ключі, які не дозволяють однозначно ідентифікувати запис в таблиці, називаються вторинними ключами.
Навіть при наявності первинного ключа, для пошуку запису можуть використовуватися вторинні. Наприклад, пошукові системи Internet часто організовані як набори записів, які відповідають Web-сторінкам. В якості вторинних ключів для пошуку виступають ключові слова, а сама задача пошуку зводиться до вибірки з таблиці деякої множини записів, які містять потрібні вторинні ключі.
4.2.1 Інвертовані індекси
Розглянемо метод організації таблиці з інвертованими індексами. Для таблиці будується окремий набір даних, який містить так звані інвертовані індекси. Допоміжний набір містить для кожного значення вторинного ключа відсортований список адрес записів таблиці, які містять даний ключ.
Пошук здійснюється у допоміжній структурі достатньо швидко, так як фактично відсутня необхідність звернення до основної структури даних. Ділянка пам'яті, яка використовується для індексів, є відносно невеликою у порівнянні з іншими методами організації таблиць.
Недоліками даної системи є великі затрати часу на складання допоміжної структури даних і її поновлення. Причому ці затрати зростають зі збільшенням об'єму бази даних.
Система інвертованих індексів є досить зручною й ефективною при організації пошуку в великих таблицях.
4.2.2 Бітові карти
Для таблиць невеликого об'єму використовують організацію допоміжної структури даних у вигляді бітових карт. Для кожного значення вторинного ключа записів основного набору даних записується послідовність бітів. Довжина послідовності бітів рівна кількості записів. Кожен біт в бітовій карті відповідає одному значенню вторинного ключа і одному запису. Одиниця означає наявність ключа в запису, а нуль - відсутність.
Основною перевагою такої організації є дуже проста й ефективна організація обробки складних запитів, які можуть об'єднувати значення ключів різними логічними предикатами. У цьому випадку пошук зводиться до виконання логічних операцій запиту безпосередньо над бітовими стрічками й інтерпретації результуючої бітової стрічки. Іншою перевагою є простота поновлення карти при добавленні записів.
До недоліків бітових карт варто віднести збільшення довжини стрічки пропорційно довжині файлу. При цьому наповненість карти одиницями зменшується зі збільшенням довжини файлу. Для великої довжини таблиці і ключів, які рідко зустрічаються, бітова карта перетворюється в велику розріджену матрицю, яка складається, в основному, з одних нулів.
5. Мережеві алгоритми
Мережі відіграють важливу роль у багатьох програмах. Їх можна використовувати для моделювання таких об'єктів, як мережа вулиць, телефонна або електрична мережа, водопровід, каналізація, водостік, мережа авіаперевезень або залізниць. Менш очевидна можливість використовування мереж для вирішення таких задач, як розбиття на райони, складання розкладу методом критичного шляху, планування колективної роботи або розподіли роботи.
5.1 Представлення мереж
Мережею або графом називається набір вузлів, сполучених ребрами або зв'язками. Для графа, на відміну від дерева, не було визначено поняття батьківського або синівського вузла. З ребрами мережі може бути зв'язаний відповідний напрям, тоді в цьому випадку мережа називається орієнтованою мережею. Для кожного зв'язку можна також визначити її ціну. Для мережі доріг, наприклад, ціна може бути рівна часу, який займе проїзд відрізком дороги, представленому ребром мережі. В телефонній мережі ціна може бути рівна коефіцієнту електричних втрат в кабелі, представленому зв'язком.
Шляхом між вузлами А і B називається послідовність ребер, яка зв'язує два ці вузли між собою. Якщо між будь-якими двома вузлами мережі є не більше одного ребра, то шлях можна однозначно описати, перерахувавши вузли, які входять в нього.
Циклом називається шлях який зв'язує вузол з ним самим. Шлях називається простим, якщо він не містить циклів.
Якщо існує який-небудь шлях між двома вузлами, то повинен існувати і простий шлях між ними. Цей шлях можна знайти, якщо видалити всі цикли з початкового шляху.
Мережа називається зв'язною, якщо між будь-якими двома вузлами існує хоча б один шлях. В орієнтованій мережі не завжди очевидно, чи є мережа зв'язною.
Більшість з методів представлень дерев можна застосувати і для роботи з мережами. Наприклад, представлення повними вузлами, списком нащадків (списком сусідів для мереж) або нумерацією зв'язків також можуть використовуватися для зберігання мереж.
Для різних програм можуть краще підходити різні представлення мережі. Представлення повними вузлами забезпечує хороші результати, якщо кожний вузол в мережі був зв'язаний з невеликою кількістю ребер. Представлення списком сусідніх вузлів забезпечує більшу гнучкість, ніж представлення повними вузлами, а представлення нумерацією зв'язків, хоча його складніше модифікувати, забезпечує більш високу продуктивність.
Окрім цього, деякі варіанти представлення ребер можуть спростити роботу з певними типами мереж. Ці представлення використовують один тип для вузлів і інший - для представлення зв'язків. Використання визначення типів для зв'язків полегшує роботу з властивостями зв'язків, такими, як ціна зв'язку.
Наприклад, орієнтована мережа з ціною зв'язків може використовувати для типу вузла структуру з номером вузла і списком сусідніх вузлів, а для представлення типу зв'язок - номер кінцевого вузла і ціна зв'язку.
Для представлення неорієнтованих мереж, можна використати інше представлення. Тип для представлення вузлів залишається таким же, що й раніше, але тип для представлення зв'язку включає посилання на обидва вузли на кінцях зв'язку. Для неорієнтованої мережі, попереднє представлення використовувало б два об'єкти для представлення кожного зв'язку - по одному для кожного з напрямків зв'язку.
5.2 Операції з вузлами і зв'язками
Мережі не завжди містять вузол, який займає таке особливе положення, як корінь в дереві. В незв'язній мережі може не існувати способу обійти всі вузли через зв'язки, почавши з одного конкретного вузла.
Тому алгоритми, які працюють з мережами, звичайно містять повний список усіх вузлів в мережі. Алгоритм також може зберігати повний список всіх зв'язків. За допомогою цих списків можна легко виконати будь-які дії над усіма вузлами або зв'язками в мережі.
5.2.1 Обхід мережі
Обхід мережі виконується аналогічно обходу дерева. Можна обходити мережу, використовуючи або обхід в глибину, або обхід в ширину. Обхід в ширину звичайно схожий на прямий обхід дерева, хоча для мереж можна визначити також зворотний і навіть симетричний обхід.
Алгоритм для виконання прямого обходу бінарного дерева формулюється так:
1. Звернутися до вузла.
2. Виконати рекурсивний прямий обхід лівого дерева.
3. Виконати рекурсивний прямий обхід правого дерева.
В дереві між зв'язаними між собою вузлами існує відношення батько - нащадок. Оскільки алгоритм починається з кореневого вузла і завжди виконується зверху вниз, він не звертається двічі ні до одного вузла.
У мережі вузли не обов'язково мають бути зв'язані в напрямку зверху вниз. Якщо спробувати застосувати до мережі алгоритм прямого обходу, може виникнути нескінченний цикл.
Щоб уникнути цього, алгоритм повинен позначати вузол після звернення до нього, при цьому при пошуку в сусідніх вузлах, перегляд відбувається тільки до вузлів, які ще не були помічені. Після того, як алгоритм завершить роботу, всі вузли в мережі будуть помічені (якщо мережа є зв'язною). Алгоритм прямого обходу мережі формулюється так:
1. Помітити вузол.
2. Звернутися до вузла.
3. Виконати рекурсивний обхід не помічених сусідніх вузлів.
Оскільки такий алгоритм обходу не допускає звернення до жодного вузла двічі, то список обходу зв'язків не містить циклів і утворює дерево.
Якщо мережа є зв'язною, то дерево обходу міститиме всі вузли мережі. Оскільки це дерево охоплює всі вузли мережі, то воно називається стовбурним деревом. Можна використовувати схожий підхід з поміткою вузлів для перетворення обходу дерева в ширину в мережний алгоритм. Алгоритм обходу дерева починається з поміщення кореневого вузла в чергу. Потім перший вузол вилучається з черги, відбувається звернення до нього, а в кінець черги поміщаються його дочірні вузли. Цей процес повторюється до тих пір, поки черга не стає пустою.
В алгоритмі обходу мережі потрібно спочатку переконатися, що вузол не перевірявся раніше або він вже не знаходиться в черзі. Для цього помічають кожний вузол, який поміщається в чергу. Мережна версія цього алгоритму має так вигляд:
1. Помітити перший вузол (який буде коренем стовбурного дерева) і додати його в кінець черги.
2. Повторювати наступні кроки до тих пір, поки черга не стає пустою:
3. Видалити з черги вузол і звернутися до нього.
4. Для кожного з непомічених сусідніх вузлів, помітити його і додати в кінець черги.
5.2.2 Найменші стовбурні дерева
Якщо була задана мережа з ціною зв'язків, то найменшим стовбурним деревом називається стовбурне дерево, в якому сумарна ціна всіх зв'язків в дереві буде найменшою. Найменше стовбурне дерево можна використовувати, щоб зв'язати всі вузли в мережі шляхом з якнайменшою ціною.
Наприклад, нехай потрібно розробити телефонну мережу, яка повинна з'єднати шість міст. Можна прокласти магістральний кабель між усіма парами міст, але це буде невиправдано дорого. Меншу вартість матиме рішення, при якому міста будуть сполучені зв'язками, які містяться в найменшому стовбурному дереві. Зауважимо, що мережа може мати декілька найменших стовбурних дерев.
Існує простий алгоритм пошуку найменшого стовбурного дерева для мережі:
1. Поміщають в стовбурне дерево будь-який вузол.
2. Знаходять зв'язок з найменшою ціною, який сполучає вузол в дереві з вузлом, який ще не був поміщений в дерево.
Подобные документы
Регулярний тип даних мови Pascal, що дозволяє в програмі задавати структуру даних, яка називається масивом. Поняття одновимірного та багатовимірного масиву. Прямі методи сортування масивів, типи даних. Таблиця результативності гравців футбольної команди.
лекция [411,2 K], добавлен 24.07.2014Історія створення мови С#. Аналіз алгоритмів кодування даних. Розробка системи в середовищі Visual Studio 2008 Express. Схема шифрування алгоритму DES. Дослідження алгоритму RC2. Приклади хешів RIPEMD-160. Програмна реалізація основних процедур системи.
дипломная работа [1,7 M], добавлен 25.10.2012Розробка інформаційної системи зберігання, обробки та моделювання алгоритмів обчислення статистичних даних для змагань з плавання і з інших видів спорту. Зміст бази даних, реалізація БД засобами MySQL, створення клієнтського додатка в середовищі PHP.
дипломная работа [4,5 M], добавлен 17.09.2011Перетворення вхідних даних великого розміру в дані фіксованого розміру. Алгоритми хешування з різними характеристиками. Криптографічні хеш-функції та їх використання. Застосування хешування для прискорення пошуку даних, перевірка парольної фрази.
презентация [80,7 K], добавлен 14.08.2013База даних як організована структура, призначена для зберігання інформації. Проектування та реалізація в СУБД MS Access інформаційної системи "База даних Internet-ресурсів тестів з психології". Розробка логічної системи даних, інструкції користувача.
курсовая работа [5,3 M], добавлен 22.10.2012Порівняння характеристик топології мережі передачі даних, таких як: діаметр, зв’язність, ширина бінарного поділу та вартість. Загальний опис механізмів передачі даних – алгоритмів маршрутизації, а також методів передачі даних між процесорами мережі.
курсовая работа [167,3 K], добавлен 20.06.2015Використання методів обробки сигналів, які базуються на використанні малохвильової теорії. Вимоги до алгоритмів компресії та критерії порівняння алгоритмів. Застосування вейвлет-перетворень. Критерії оцінювання оптимальності вибору малохвильових функцій.
реферат [1,1 M], добавлен 26.05.2019Вирішення задач сортування в програмуванні та розробка ефективних алгоритмів сортування. Знайомство з теоретичним положенням, що стосуються методів сортування файлів, реалізації їх на мові програмування Turbo Pascal. Методи злиття впорядкованих серій.
курсовая работа [46,9 K], добавлен 16.09.2010Характеристика швидкодії алгоритмів сортування масивів прямим і бінарним включенням, методами "бульбашки", "камінця", та шейкерного відбору, визначення їх переваг та недоліків. Огляд функцій сортування із стандартної бібліотеки мови програмування С++.
курсовая работа [452,1 K], добавлен 16.09.2010Аналіз предметної галузі, постановка задачі, проектування бази даних. UML-моделювання, побудова ER-діаграми, схеми реляційної бази даних у третій нормальній формі. Призначення і логічна структура. Опис фізичної моделі бази даних, програмної реалізації.
курсовая работа [3,5 M], добавлен 28.11.2011
