Найкоротші шляхи
Алгоритм Едсгера Дейкстри 1956 року відвідує вузли в порядку накопиченої вартості від джерела, гарантуючи оптимальність на графах із невід'ємними вагами ребер. На сітці з 1000 вузлів він обробляється за мілісекунди; на розріджених реальних дорожніх мережах він обробляє мільйони вузлів при відповідному налаштуванні черги з пріоритетами.
Пошук шляху — Дейкстра й A*
Малюйте перешкоди на сітці й порівнюйте Дейкстру (досліджує рівномірно в усіх напрямках) з A* (керується евристикою h(v)=‖v−ціль‖ за евклідовою відстанню). Спостерігайте фронт і закриту множину в реальному часі.
Генерація та розв'язання лабіринтів
Генеруйте лабіринти за допомогою рекурсивного повернення, рандомізованого MST Прима або порядкового алгоритму Еллера. Розв'язуйте за допомогою BFS (найкоротший шлях), DFS (швидко, не оптимально) або A*.
Складність Дейкстри проти A*
Дейкстра: O((V + E) log V) із черга з пріоритетами на бінарній купі
A*: O(b^d) у найгіршому випадку; майже O(E log V) з гарною евристикою h(v)
Гарантія A*: якщо h(v) допустима (h(v) ≤ істинна вартість), результат оптимальний
f(v) = g(v) + h(v), де g — вартість від старту, h — евристика до цілі
Остовні дерева та зв'язність
Мінімальне остовне дерево (MST) з'єднує всі вузли з мінімальною сумарною вагою ребер і без циклів. Алгоритм Крускала сортує всі ребра за вагою й використовує структуру «система непересічних множин»; алгоритм Прима вирощує одне дерево з початкового вузла. Обидва дають однакове MST, але відрізняються продуктивністю на щільних і розріджених графах.
Мінімальне остовне дерево
Додавайте випадкові вузли й спостерігайте, як алгоритми Крускала і Прима будують MST ребро за ребром. Показане стиснення шляхів у системі непересічних множин; порівняйте кількість ребер із повним кліком.
Силова розкладка графа
Алгоритм розкладки Фрухтермана-Рейнгольда — ребра діють як пружини (закон Гука), вузли відштовхуються через кулонівську силу. Самоорганізована розкладка виявляє кластери й периферійні вузли.
Комбінаторна оптимізація
Деякі графові задачі не мають відомого поліноміального алгоритму. Задача комівояжера (TSP) — знайти найкоротший маршрут, що відвідує кожен вузол рівно раз — NP-складна. Проте наближення й евристики на практиці працюють на диво добре.
Задача комівояжера
Евристики 2-opt і найближчого сусіда для TSP на 20–80 містах. Порівняйте жадібну вставку (швидко, ~25% вище оптимуму) з імітацією відпалу (повільніше, майже оптимально на 40 містах).
Візуалізатор алгоритмів сортування
Бульбашкове, злиттям, швидке, пірамідальне сортування у вигляді кольорових стовпчиків. Кількість інверсій у реальному часі; порівняйте час виконання O(n²) проти O(n log n) на n від 50 до 300 елементів.
Чому A* перевершує Дейкстру на практиці? Дейкстра розширює вузли рівномірно в усіх напрямках. A* використовує евристику h(v), щоб зміщувати розширення в бік цілі, досліджуючи набагато менше вузлів. На дорожніх мережах Дейкстра зазвичай досліджує >50% графа; A* з евклідовою відстанню — <5% — без втрати оптимальності.
Навчальні маршрути
Класичні алгоритми
- Візуалізатор алгоритмів сортування
- Пошук шляху — Дейкстра й A*
- Генерація та розв'язання лабіринтів
- Мінімальне остовне дерево
Просунуті графи
- Силова розкладка графа
- Задача комівояжера
- Навчання дерева рішень