Д

ля

шифрування даних у криптографії

В алгоритмах сортування для підвищення їх ефективності.

Д

ля

побудови дерев рішень у машинному навчанні.

В

генетичних алгоритмах та інших евристичних методах для ефективного кодування

розв'язків і забезпечення плавного переходу між ними.

Single Source Shortest

Path

Vehicle Routing Problem

8-Queens

Problem

Minimum

Spanning Tree

Ц

е алгоритм, який

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

Ц

е метод

кластеризації даних, який використовує багатовимірний простір для групування

схожих об'єктів.

Ц

е алгоритм, який

використовується для знаходження найкращого можливого рішення в просторі

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

Ц

е алгоритм, який

шукає найкоротший шлях у графі, використовуючи жадібний підхід.

С

ортує всі ребра

за зростанням ваги; перебирає відсортовані ребра і додає кожне ребро до MST,

якщо це не утворює циклу.

Використовує метод

найближчих сусідів для побудови дерева, де кожна вершина з'єднується з

найближчою сусідньою вершиною за допомогою ребра.

Б

азується на

випадковому виборі ребер і додаванні їх до

Включає побудову

графа з усіма можливими ребрами та подальше видалення ребер з найбільшою вагою,

поки не залишиться мінімальний набір ребер.

Ц

е задача, яку можна

розв'язати за поліноміальний час і яка має лише один можливий розв'язок.

Це клас задач у

теорії обчислювальної складності, для яких виконуються два основних критерії:

а) NP (Nondeterministic Polynomial time): Задача належить до класу NP, тобто її

розв'язок може бути перевірений за поліноміальний час. Б) NP-повнота: Задача є

NP-повною, якщо вона є однією з найскладніших задач у класі NP.

Ц

е задача, яку можна

розв'язати тільки за допомогою жадібних алгоритмів і яка не має жодних обмежень

на час виконання.

Vehicle

Routing Problem

Minimum Spanning Tree

Very

Large Scale Integration

Traveling

Salesman Problem

Кросовер — це процес, який виконується після завершення основного циклу

алгоритму для збереження найкращих рішень.

Мутація — це процес, який використовує тільки найгірші рішення для

створення нових рішень у популяції.

Кросовер — це генетичний оператор у еволюційних

алгоритмах, який поєднує двох батьківських індивідів (розв'язків) для створення

одного або кількох нащадків. Мета кросоверу полягає у змішуванні генетичної

інформації двох батьків з надією отримати нові, кращі рішення.

Мутація — це генетичний оператор, який випадковим

чином змінює частину індивіда для введення нових генетичних варіацій у

популяцію. Мутація допомагає уникнути передчасної конвергенції на локальних

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

Кросовер — це процес випадкового вибору нових параметрів для батьківських

рішень, який виконується кожного разу перед оцінкою функції придатності.

Мутація — це процес заміни одного з батьківських рішень на нове випадкове

рішення з популяції.

Кросовер — це процес, у якому один батько передає своє рішення іншому

батькові для обчислення середнього значення обох рішень.

Мутація — це процес, при якому генетичний алгоритм перестає шукати нові

рішення після певної кількості ітерацій.

Шляхом випадкового обміну будь-яких елементів між двома батьківськими

рішеннями без урахування специфіки задачі оптимізації на графах.

Одним з поширених

методів є одноточковий або двоточковий кросовер, де відбувається обмін

частинами маршрутів між двома батьківськими розв'язками.

Кросовер у

генетичному алгоритмі для задачі оптимізації на графах полягає у зміні ваг

ребер між вершинами у батьківських рішеннях, щоб створити нові ваги для

нащадків.

Шляхом об'єднання всіх вершин і ребер двох батьківських рішень у один великий

граф, після чого алгоритм випадковим чином обирає маршрут з цього графа.

Метод класифікації,

такий як метод найближчого сусіда (

Методи кластеризації,

такі як алгоритм

Генетичний алгоритм.

М

етоди регресії, такі

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

Застосовується для кластеризації вершин графа на

основі їхньої центральності.

Метод contraction hierarchies включає динамічне

перепланування ребер графа в реальному часі для оптимізації обчислень.

Полягає у попередній обробці графа шляхом

поступового "стискання" його вершин. Вершини графа видаляються в

певному порядку, а нові з'єднання (shortcuts) додаються між сусідніми

вершинами, щоб зберегти короткі шляхи. Це дозволяє значно зменшити розмір графа.

Використовує зменшення розміру ребер графа для

зниження складності обчислень.