Підбірка візуалізації по алгоритмах пошуку


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Візуалізація – відмінний спосіб показати, як наочно працює той або інший алгоритм. Пропонуємо вашій увазі алгоритми пошуку і їх візуалізації з посиланнями на початковий код.

Список даних алгоритмів :

Алгоритм пошуку A*

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

A* покроково переглядає всі шляхи, що ведуть від початкової вершини в кінцеву, поки не знайде мінімальний. Як й всі поінформовані алгоритми пошуку, він переглядає спочатку ті маршрути, які “здаються” ведуть до мети. З вихідним кодом алгоритму ви зможете ознайомитися на додатковому ресурсі.

Алгоритм пошуку Jump Point Search (JPS)

JPS виконує пошук шляху швидше, ніби “перескакуючи” деякі місця, які мають бути проглянуті. Характерною відмінністю JPS від інших алгоритмів є відсутність вимог для попередньої обробки і додаткових витрат пам’яті.

Детальніше ознайомитися з роботою цього алгоритму ви зможете в розгорнутій статті, присвяченої йому. З кодом цього алгоритму пропонуємо ознайомитися на додатковому ресурсі.

Алгоритм виявлення циклічних схем в спрямованому графові

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

З початковим кодом алгоритму і його інтерактивною презентацією ви зможете ознайомитися в джерелі.

Алгоритм пошуку в глибину

Стратегія алгоритму полягає в тому, щоб йти ” углиб” графа, наскільки це можливо. Алгоритм пошуку в глибину описується рекурсивно: перебираються усі ребра, що виходять з даної вершини. Якщо ребро веде у вершину, яка не була розглянута раніше, то алгоритм треба запустити від неї, а після повернутися і продовжити перебирати ребра. Повернення відбувається у тому випадку, якщо в даній вершині не залишилося ребер, які ведуть в нерозглянуту вершину. Якщо після завершення алгоритму не усі вершини були розглянуті, то необхідно запустити алгоритм від однієї з нерозглянутих вершин.

Давайте розглянемо роботу алгоритму на анімації нижче. Як бачите, шлях “углиб” графа розпочинається з вершини A, потім перевіряється вершина B, далі за вершину D і E. Таким чином алгоритм перевіряє усі вершини цієї гілки і “повертається” для дослідження іншій гілці. Алгоритм закінчує роботу на вершині A, тому що вершина D вже була перевірена раніше. З кодом алгоритму ви зможете ознайомитися в статті, присвяченоі йому.

Алгоритм пошуку завширшки

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

Примітка Ви можете експериментувати з цим алгоритмом в спеціальній візуалізації.

Примітка граф – це, кажучи простими словами, безліч точок, що називаються вершинами, сполучених якимись лініями, що називаються ребрами (необов’язково усі вершини сполучені). Можна уявляти собі як міста, сполучені дорогами.

Ви зможете ознайомитися з початковим кодом і інтерактивною презентацією алгоритму в джерелі.

Алгоритм Дейкстри

В процесі виконання алгоритм перевірить кожну з вершин графа і знайде найкоротший шлях до початкової вершини. Він широко застосовується в програмуванні, наприклад, при роботі з протоколами маршрутизації OSPF та IS – IS.

Примітка Ви можете експериментувати з цим алгоритмом в спеціальній візуалізації.

Ви зможете ознайомитися з кодом і інтерактивною презентацією алгоритму на спеціальному ресурсі.

Додаткові матеріали для практики

Також пропонуємо вам звернути увагу на інтерактивні реалізації різних алгоритмів разом з ігровими механізмами. Усі зразки представлені з початковим кодом під ліцензією MIT. Цей ресурс буде корисний для програмістів, які також зацікавлені в розробці ігор, але не знають, як реалізувати або побудувати правильно той або інший алгоритм.

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *