Категорія «Алгоритми та ШІ» існує вже деякий час, але тепер у неї є власна виділена сторінка з фірмовими акцентними кольорами, обраними симуляціями та посиланнями на статті. Ось що в ній є.
Що входить до категорії
Чому алгоритми?
Алгоритми часто викладають за допомогою статичних діаграм або псевдокоду. Але вони — це процеси: у них є динаміка, вони ухвалюють рішення, вони досліджують простори. Анімація в реальному часі показує те, чого блок-схема ніколи не покаже: чому A* знаходить найкоротший шлях, не досліджуючи всю сітку, чому генетичні алгоритми сходяться до локальних оптимумів, чому швидке сортування деградує на вже відсортованих вхідних даних.
Кожна симуляція в цій категорії дозволяє взаємодіяти з алгоритмом безпосередньо під час його роботи. Змінюйте стіни лабіринту, порушуйте рух рою, налаштовуйте частоту мутацій — і бачте ефект миттєво.
Детальніше про пошук шляху
Пошук шляху A* — ймовірно, найкраща відправна точка, якщо ви ніколи не спостерігали за роботою алгоритму пошуку. Розставте стіни в будь-якому місці сітки, перетягніть маркери початку та мети — і натисніть play. Ви побачите, як фронт дослідження розширюється віялом відвіданих клітинок, що розходяться від старту, зі зміщенням у бік мети завдяки евристиці — зазвичай це відстань по прямій або манхеттенська відстань. Порівняйте це зі звичайним алгоритмом Дейкстри (який досліджує рівномірно в усіх напрямках, не маючи жодного уявлення про те, де мета), і різниця в кількості досліджених клітинок виявиться разючою, особливо на відкритих сітках з невеликою кількістю перешкод.
Сортування та лабіринти пліч-о-пліч
Візуалізатор сортування запускає кілька класичних алгоритмів — швидке сортування, сортування злиттям, пірамідальне сортування та пару квадратичних для порівняння — на одному й тому самому перемішаному масиві, тож ви можете дивитися, як вони змагаються. Швидке сортування зазвичай найшвидше на випадкових даних, але має неприємний найгірший випадок на вже відсортованих або зворотно відсортованих вхідних даних, що візуалізатор одразу демонструє, щойно ви подаєте йому відсортований масив і бачите, як воно деградує до квадратичної поведінки. Сортування злиттям, навпаки, повільно, але передбачувано просувається незалежно від того, як виглядають вхідні дані — плата за гарантовану оцінку O(n log n) полягає в тому, що йому потрібна додаткова пам'ять для етапу злиття.
Генератори лабіринтів розташовані поруч з пошуком шляху не випадково: генерація та пошук — це дві сторони однієї медалі теорії графів. Пошук углиб вирізає довгі, звивисті коридори з небагатьма розгалуженнями, тому що завжди рухається до найновішого невідвіданого сусіда. Алгоритм Прима, застосований як генератор лабіринту замість побудовника мінімального остовного дерева, створює коротші, більш однорідні проходи з більшою кількістю тупиків. Алгоритм Вілсона використовує випадкові блукання зі стиранням циклів і, на відміну від двох інших, генерує абсолютно неупереджений лабіринт — усі можливі остовні дерева сітки є однаково ймовірними.
Що далі
У планах: повноцінний дослідник графових алгоритмів (BFS, DFS, Дейкстра, Беллман–Форд), щоб ви могли порівняти всі чотири стратегії обходу на одному й тому ж графі; розв'язувач задачі комівояжера на основі мурашиного алгоритму (ACO), що прокладає та випаровує сліди феромонів так само, як справжні мурахи; та демонстрація навчання з підкріпленням, де агент вчиться орієнтуватися у сітковому світі виключно методом спроб і помилок за сигналами винагороди, з видимою Q-таблицею, що оновлюється в реальному часі. Слідкуйте за оновленнями.