Crowdly

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

ля

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

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

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

Наведіть приклад real world-задачі, яка є NP-складною.

Single Source Shortest

Path

Vehicle Routing Problem

8-Queens

Problem

Minimum

Spanning Tree

Що таке алгоритм

beam search?

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

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

е метод

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

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

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

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

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

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

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

Вкажіть правильний алгоритм Крускала для

формування мінімального зв'язного дерева.

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

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

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

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

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

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

азується на

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

MST

, доки не

будуть з'єднані всі вершини графа.

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

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

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

Що таке NP-повна задача?

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

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

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

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

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

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

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

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

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

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

Наведіть приклад benchmark-задачі, яка не є NP-складною.

Vehicle

Routing Problem

Minimum Spanning Tree

Very

Large Scale Integration

Traveling

Salesman Problem

Що таке кросовер і мутація?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

розробили генетичний алгоритм. Яким чином буде здійснюватись кросовер?

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

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

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

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

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

Кросовер у

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

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

нащадків.

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

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

. Який метод оптимізації тут підійде?

Вам необхідно розв'язати задачу Political Districting

Problem

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

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

k-NN), який поділяє території на основі найближчих сусідів.

k-середніх (k-means), для поділу територій на політичні округи.

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

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

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

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

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

В чому полягає

суть методу оптимізації contraction hierarchies для задач на графах?

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

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

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

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

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

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

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

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

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

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