Базові алгоритми, що будуть використані при розробці програми пошуку оптимальної туристичної путівки

Базові алгоритми та структури даних — важлива складова, при створенні будь-якого проекту. Вони є потужним інструментом у вирішенні багатьох поставлених задач у розробці програмного забезпечення. Вони дозволяють спростити код програми, оптимізувати його, та зробити більш лаконічним. Існують такі базові алгоритми та структури даних:

Масимв — впорядкований набір фіксованої кількості однотипних елементів, що зберігаються в послідовно розташованих комірках оперативної пам’яті, мають порядковий номер і спільне ім'я, що надає користувач, сукупність елементів одного типу даних, впорядкованих за індексами, які зазвичай репрезентовані натуральними числами, що визначають положення елемента в масиві. Масив може бути одновимірним (вектором), та багатовимірним (наприклад, двовимірною таблицею), тобто таким, де індексом є не одне число, а кортеж (сукупність) з декількох чисел, кількість яких збігається з розмірністю масиву [1]. В даній курсовій роботі, динамічний масив використовується для виведення туристичних путівок, які задовольняють вимоги та потреби користувача.

Зв’язаний список — одна з найважливіших структур даних, в якій елементи лінійно впорядковані, але порядок визначається не номерами елементів, а вказівниками, які входять в склад елементів списку та вказують на наступний за даним елемент (в однозв’язних або однобічно зв’язаних списках) або на наступний та попередній елементи (в двозв’язних або двобічно зв’язаних списках). Список має «голову» — перший елемент та «хвіст» — останній елемент. Зв’язані списки мають серію переваг порівняно з масивами. Зокрема, в них набагато ефективніше (за час О (1), тобто незалежно від кількості елементів) виконуються процедури додавання та вилучення елементів. Натомість, масиви набагато кращі в операціях, які потребують безпосереднього доступу до кожного елементу, що у випадку зі зв’язаними списками неможливо та потребує послідовного перебору усіх елементів, які передують даному [2].

Стек — різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) «останнім прийшов — першим пішов» (LIFO, англ. last in, first out). Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стеку та був введений в стек останнім. Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку (інша назва стеку — «магазин», за аналогією з принципом роботи магазину в автоматичній зброї) [3].

Черга — динамічна структура даних, що працює за принципом «перший прийшов — перший пішов» (англ. FIFO — first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові. Така черга повністю аналогічна звичній «базарній» черзі, в якій хто перший встав в неї, той першим буде обслуженим [4].

Двійкове дерево — структура даних у вигляді дерева, в якому кожна вершина має не більше двох дітей. Зазвичай такі діти називаються правим та лівим. На базі двійкових дерев будуються такі структури, як двійкові дерева пошуку та двійкові купи. Часто виникає необхідність обійти усі вершини дерева для аналізу інформації, що в них знаходиться. Існують декілька порядків такого обходу, кожний з яких має певні властивості, важливі в тих чи інших алгоритмах: прямий (preorder), центрований (inorder) та зворотний (postorder) [5].

АВЛ-дерево — збалансоване по висоті двійкове дерево пошуку: для кожної його вершини висота її двох піддерев відрізняється не більше ніж на 1. АВЛ — абревіатура, утворена першими літерами творців (радянських учених) Адельсон-Вельського Георгія Максимовича і Ландіс Євгена Михайловича [6].

Генетичний алгоритм — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію. Особливістю генетичного алгоритму є акцент на використання оператора «схрещення», який виконує операцію рекомбінацію рішень-кандидатів, роль якої аналогічна ролі схрещення в живій природі [7].

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

Головне завдання БД — гарантоване збереження значних обсягів інформації (так звані записи даних) та надання доступу до неї користувачеві або ж прикладній програмі. Таким чином, БД складається з двох частин: збереженої інформації та системи керування нею.

З метою забезпечення ефективності доступу записи даних організовують як множину фактів (елемент даних) [8].

Сортування — це алгоритм, що розв’язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів. Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основними характеристиками є: час необхідний на впорядкування n-елементного масиву і додаткова пам’ять необхідна для впорядкування. Крім цих двох характеристик, сортування буває стабільним чи нестабільним, з використанням додаткової інформації про елементи, чи без використання.

Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є, це пов’язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів. Інший клас алгоритмів здійснює впорядкування за час. В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного [9]. Серед найвідоміших алгоритмів сортування: сортування бульбашкою, сортування вставками, швидке сортування, сортування Шелла.

Жадібний алгоритм — простий і прямолінійний евристичний алгоритм, який приймає найкраще рішення, виходячи з наявних на поточному етапі даних, не турбуючись про можливі наслідки, сподіваючись врешті-решт отримати оптимальне рішення. Легкий в реалізації і часто дуже ефективний за часом виконаннях [10]. Багато комбінаторно-оптимізаційних задач не можуть бути розв’язані з його допомогою. В даній курсовій роботі, даний алгоритм використовується для виведення оптимальної кількості путівок, які можна придбати на суму, на яку розраховує користувач.

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