Алгоритми та обчислювальна складність — сортування, пошук шляху та NP-складні задачі

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

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

Нотація Big-O дає саме це. O(n²) означає: якщо подвоїти розмір вхідних даних, час виконання приблизно зросте вчетверо. O(n log n) означає, що подвоєння вхідних даних лише трохи більш ніж подвоює обсяг роботи. O(2ⁿ) означає, що кожен додатковий елемент подвоює час виконання — смертний вирок для великих вхідних даних. Ці швидкості зростання розділяють алгоритми на практичні рівні, і різниця між алгоритмом першого й третього рівня може означати різницю між чуйним застосунком і таким, що заморожує ваш браузер.

Шість симуляцій нижче роблять складність видимою: ви спостерігаєте, як алгоритми O(n²) борються зі зростанням n, і бачите, як розумні структури даних зводять обхід графа O(n²) до O((V + E) log V), не змінюючи саму відповідь.

Частина 1: алгоритми сортування

Симуляція сортування — O(n²) проти O(n log n) наживо

Сортування — перший алгоритм, який вивчає більшість програмістів, і найретельніше проаналізований у комп'ютерних науках. Його простота робить його ідеальною лабораторією для порівняння класів складності: бульбашкове й сортування вставками — O(n²) у найгіршому випадку; сортування злиттям і пірамідальне сортування — завжди O(n log n); швидке сортування — O(n log n) у середньому, але O(n²) у найгіршому без рандомізованого вибору опорного елемента.

Алгоритм      Найкращий  Середній   Найгірший  Пам'ять   Стабільний?
──────────────────────────────────────────────────────────────────
Бульбашкове   Ω(n)       Θ(n²)      O(n²)      O(1)      Так
Вставками     Ω(n)       Θ(n²)      O(n²)      O(1)      Так
Вибором       Ω(n²)      Θ(n²)      O(n²)      O(1)      Ні
Злиттям       Ω(n log n) Θ(n log n) O(n log n) O(n)      Так
Швидке        Ω(n log n) Θ(n log n) O(n²)*     O(log n)  Ні
Пірамідальне  Ω(n log n) Θ(n log n) O(n log n) O(1)      Ні
Порозрядне    Ω(nk)      Θ(nk)      O(nk)      O(n+k)    Так
Tim Sort      Ω(n)       Θ(n log n) O(n log n) O(n)      Так

* Найгіршого випадку швидкого сортування уникають рандомізованим опорним елементом

Інверсії та сортування вставками:
  Вартість ∝ кількість інверсій у масиві
  Вже відсортований масив: O(n) порівнянь (найкращий випадок)
  Відсортований у зворотному порядку: n(n-1)/2 інверсій → O(n²)

Нижня межа для сортування на основі порівнянь:
  Будь-яке сортування на основі порівнянь потребує Ω(n log n) порівнянь
  Доказ: дерево рішень має n! листків → висота ≥ log₂(n!)

Симуляція сортування візуалізує всі основні алгоритми поряд, на одному й тому самому масиві. Оберіть розмір масиву (від 8 до 1000 елементів), розподіл (випадковий, майже відсортований, зворотно відсортований, багато дублікатів) і спостерігайте за анімацією стовпчикової діаграми. Лічильник порівнянь підтверджує прогноз Big-O: лічильник сортування злиттям зростає як n log n; лічильник бульбашкового сортування зростає як n². Майже відсортовані масиви розкривають приховану силу сортування вставками — його найкращий випадок Ω(n).

Частина 2: пошук шляху в графах

Симуляція пошуку шляху — Дейкстра та A*

Навігація, маршрутизація в мережах, ігровий ШІ — усе зводиться до однієї задачі: знайти найкоротший шлях між двома вузлами у зваженому графі. Алгоритм Дейкстри розв'язує це оптимально за O((V + E) log V), використовуючи чергу з пріоритетом. A* розширює Дейкстру евристичною функцією, що оцінює залишкову відстань, разюче зменшуючи кількість досліджуваних вузлів на структурованих графах на кшталт сіток.

Дейкстра (найкоротший шлях з одного джерела):
  Вхід:  зважений граф G=(V,E), джерело s
  Вихід: dist[v] = найкоротша відстань від s до v

  Черга з пріоритетом (min-heap):
    dist[s] = 0; dist[v] = ∞ для v ≠ s
    поки Q не порожня:
      u = extract_min(Q)
      для кожного сусіда v вузла u:
        якщо dist[u] + w(u,v) < dist[v]:
          dist[v] = dist[u] + w(u,v)
          decrease_key(Q, v, dist[v])

  Складність: O((V + E) log V) з бінарною купою
              O(E + V log V) з купою Фібоначчі

Пошук A*:
  f(n) = g(n) + h(n)
  g(n) = фактична вартість від джерела до n
  h(n) = допустима евристика (ніколи не переоцінює)

  Допустимі евристики для сіток:
    h = евклідова відстань  (8-напрямковий рух)
    h = мангеттенська відстань  (4-напрямковий рух)
    h = відстань Чебишева  (8-напр., однакова діагональна вартість)

  A* оптимальний, якщо h допустима.
  A* відвідує менше вузлів, ніж Дейкстра, коли h інформативна.

Пошук у ширину (незважений найкоротший шлях):
  Складність: O(V + E)   знаходить найкоротший шлях за кількістю ребер

У симуляції пошуку шляху малюйте стіни, встановлюйте початкову й кінцеву точки, потім порівнюйте Дейкстру, A*, пошук у ширину й пошук у глибину на одному й тому самому лабіринті. Лічильник відвіданих вузлів робить різницю разючою: A* з мангеттенською евристикою часто досліджує в 5–10 разів менше вузлів, ніж Дейкстра, на сітці, досягаючи цілі, не скануючи неважливі ділянки. Пошук у глибину знаходить якийсь шлях швидко, але рідко найкоротший.

Симуляція генерації лабіринту

Симуляція лабіринту природно поєднується з пошуком шляху. Вона генерує ідеальні лабіринти (без петель, з одним розв'язком) за допомогою пошуку в глибину з поверненням, алгоритму Прима або алгоритму Крускала зі структурою даних Union-Find. Оскільки ідеальні лабіринти є остовними деревами, вони — мінімальний зв'язний підграф сітки: прекрасне перетинання теорії графів і комбінаторики.

Пошук у глибину (рекурсивний backtracker):
  Ідеальні випадкові лабіринти — неупереджені, але з довгими коридорами
  O(V) часу, O(V) простору стека

Рандомізований Прим (зростаюче дерево):
  Додає випадкове ребро з множини межі
  Більше розгалужень, коротший середній шлях
  O(E log E) з чергою пріоритету

Крускал + Union-Find:
  Призначаємо випадкові ваги всім ребрам, сортуємо, додаємо, якщо немає циклу
  Union-Find зі стисненням шляхів:
    find: O(α(n)) ≈ O(1) в амортизованому сенсі
    union: O(α(n)) амортизовано
  Загалом: O(E α(E)) ≈ O(E)

Алгоритм Вілсона (випадкове блукання зі стиранням циклів):
  Генерує лабіринти рівномірно випадково (справді неупереджено)
  Очікуваний час O(V log V)
  Кожне остовне дерево однаково ймовірне

Частина 3: backtracking і задачі з обмеженнями

Симуляція N-Queens — обрізання простору пошуку

Розставте N ферзів на дошці N×N так, щоб жодні два ферзі не атакували один одного. Це канонічна задача задоволення обмежень. Наївний повний перебір пробує всі N^N розстановок: для N=8 це 16 мільйонів спроб. Базовий backtracking скорочує це до 15 720 спроб, відмовляючись від часткових розв'язків у ту мить, коли порушується обмеження. З прямою перевіркою (forward checking) число падає ще далі — приблизно до 2000.

Задача:
  Розставити N ферзів на дошці N×N так, щоб жоден рядок/стовпець/діагональ не повторювались.

Розв'язки:
  N=1: 1    N=4: 2    N=8: 92    N=12: 14 200
  N=13: 73 712    N=14: 365 596    N=15: 2 279 184

Наївний повний перебір:      O(N^N)
Backtracking (по рядках):    O(N!) — один ферзь на рядок
Із відстеженням стовпців:    уникнення O(N) перевірок стовпця на розстановку
Із відстеженням діагоналей:  два булеві масиви розміром 2N-1 кожен

Схема backtracking:
  placeQueens(row, colsUsed, diag1, diag2):
    якщо row == N: розв'язок знайдено
    для col у 0..N-1:
      якщо col ∉ colsUsed ТА (row-col) ∉ diag1 ТА (row+col) ∉ diag2:
        recurse(row+1, ...)

Пряма перевірка (AC-3):
  Після розстановки ферзя видаляємо атаковані клітинки з доменів
  Обрізаємо піддерева, де будь-яка змінна має порожній домен
  Значно скорочує кількість повернень для великих N

Симуляція N-Queens анімує backtracking-пошук. Спостерігайте, як алгоритм розставляє ферзів рядок за рядком, повертається назад у тупику, пробує наступний стовпець і зрештою знаходить розв'язок. Лічильник показує загальну кількість рекурсивних викликів, розкриваючи, наскільки разюче поширення обмежень перевершує голий backtracking. Увімкніть режим «показати всі розв'язки», щоб порахувати весь простір розв'язків.

Частина 4: задача комівояжера

Симуляція TSP — NP-складність на практиці

Комівояжер має відвідати N міст рівно по одному разу й повернутися до початкового міста, мінімізуючи загальну відстань. Розв'язок повним перебором пробує всі (N-1)!/2 маршрутів — для N=20 це 60 квадрильйонів маршрутів. TSP є NP-складною задачею: жоден поліноміальний алгоритм не відомий, і більшість дослідників вважають, що жодного й не існує. Проте для практичних розмірів розумні евристики та точні розв'язувачі методом гілок і меж швидко знаходять розв'язки, близькі до оптимальних.

Точні методи:
  Повний перебір:        O((n-1)!/2)    непридатний для n > 15
  Динамічне програмування: O(2ⁿ · n²)    алгоритм Гелда-Карпа
  Гілки й межі:           експоненційний найгірший випадок, добре на практиці

Конструктивні евристики (швидкі, субоптимальні):
  Найближчий сусід:      O(n²)  — жадібно будує маршрут
    відношення до оптимуму:  в середньому 1.25, може бути й удвічі гірше

  Жадібне додавання ребра: O(n² log n)
    сортуємо ребра за довжиною, додаємо, якщо валідно (без перетину, ступінь < 2)

Локальний пошук (покращення наявного маршруту):
  2-opt:  видалити 2 ребра, перез'єднати — O(n²) за прохід
    ітеруємо, поки є покращення: O(n² · ітерацій)
    зазвичай у межах 5% від оптимуму

  3-opt:  видалити 3 ребра — O(n³) за прохід — краще, але повільніше
  Лін-Керніган (LK): витончений пошук зі змінною глибиною
    сучасна евристика, < 1% від оптимуму на більшості прикладів

NP-складність:
  TSP є NP-складною: жоден поліноміальний алгоритм не відомий
  P ≠ NP (припущення): ефективного точного алгоритму не існує
  TSP з нерівністю трикутника: 1.5-наближення (Крістофідес, 1976)

Симуляція TSP дозволяє розмістити міста на полотні, а потім обрати алгоритм: найближчий сусід, жадібне ребро або 2-opt. Лічильник довжини маршруту оновлюється наживо, поки обміни 2-opt покращують маршрут. Для 30 міст кілька секунд уточнення 2-opt зазвичай досягають 3–5% від оптимуму. Збільште до 100+ міст і подивіться, як найближчий сусід створює потворне сплетіння перетинів, яке 2-opt швидко розплутує — інтуїтивне розуміння того, чому локальний пошук важливий.

Частина 5: генетичні алгоритми

Симуляція генетичного алгоритму — еволюція як оптимізація

Коли простір пошуку надто величезний для точних методів, а локальний пошук потрапляє в пастку локальних оптимумів, генетичні алгоритми використовують механіку біологічної еволюції — відбір, схрещування, мутацію — для широкого дослідження. ГА не гарантують знаходження глобального оптимуму, але на багатьох практичних задачах вони знаходять чудові розв'язки за помірних обчислень.

Популяція:  P = {x₁, x₂, …, xₙ}  (кандидати-розв'язки, закодовані як хромосоми)
Пристосованість: f(x) → ℝ         (ціль, яку максимізуємо)

Оператори відбору:
  Турнірний:    обираємо k кандидатів, повертаємо найпристосованішого
  Рулетковий:   P(обрати xᵢ) = f(xᵢ) / Σf(xⱼ)
  Ранговий:     ймовірність ∝ ранг, а не сира пристосованість (різноманіття)

Оператори схрещування:
  Одноточкове:    розрізати у випадковій позиції, обміняти хвости
  Рівномірне:     кожен ген успадковується від батька 1 з імовірністю p
  Порядкове схрещування (OX): для задач перестановок (TSP)
    копіюємо сегмент від батька 1, решту заповнюємо від батька 2 по порядку

Оператори мутації:
  Інверсія біта:  перевернути кожен біт з імовірністю p_m
  Обмін:          обміняти дві випадкові позиції
  Інверсія:       обернути випадкову підпослідовність

Теорема схем (Холланд):
  Короткі, низького порядку, вищі за середнє схеми зростають експоненційно
  Внутрішній паралелізм: n хромосом неявно оцінюють O(n³) схем

Параметри на практиці:
  Популяція: 50–500;  Частота схрещування: 0.6–0.9;  Мутація: 0.001–0.05
  Занадто низька мутація → передчасна збіжність
  Занадто висока мутація → випадковий пошук

Симуляція генетичного алгоритму використовує TSP як ціль оптимізації. Спостерігайте, як популяція сходиться: ранні покоління показують шалено розкидані довжини маршрутів, потім тиск відбору тягне розподіл до коротших маршрутів, тоді як ін'єкції мутацій запобігають колапсу популяції до одного розв'язку. Побудуйте криві найкращої/середньої пристосованості, щоб побачити класичний ступінчастий патерн збіжності — стрибки, що виникають, коли схрещування виявляє нове структурне покращення.

Колекція алгоритмів

Зв'язки між колекціями

Алгоритми з цієї колекції з'являються по всій платформі під іншими масками. Пошук шляху A* — основа уникнення перешкод у симуляції зграйної поведінки Boids — агенти знаходять шляхи без зіткнень, використовуючи те саме розширення черги з пріоритетом. Union-Find із генерації лабіринту знову з'являється в симуляції перколяції для відстеження зв'язних кластерів через ґратку. Генетичні алгоритми напряму живлять симуляцію генетичного алгоритму. Навіть сортування присутнє в симуляції аеропрофілю, де значення тиску вздовж поверхні сортуються для знаходження точок застою й відриву потоку. Теорія складності пов'язує все: причина, чому ми використовуємо жадібні алгоритми для пошуку шляху й евристики для TSP, полягає саме в тому, що точні методи не масштабуються — факт, який стає болісно очевидним, коли спостерігаєш, як N-Queens вибухає складністю після N=15.

Алгоритми та методи в цій колекції