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

🔬 Неінформативні алгоритми

DFS (Depth-First Search)

Пошук у глибину: йде наскільки можна глибше перед поверненням. Використовує стек (LIFO). Може бути неефективним для великих просторів. Переваги: мала пам'ять, знаходить будь-який шлях.

BFS (Breadth-First Search)

Пошук у ширину: спочатку всі вузли на рівні, потім наступний рівень. Використовує чергу (FIFO). Знаходить найкоротший шлях (за кількістю кроків). Недолік: велика пам'ять.

Uniform Cost Search

Узагальнення BFS для зважених графів. Знаходить найдешевший шлях (за вагами ребер). Використовує пріоритетну чергу. Базовий для Dijkstra.

🎯 Евристичні алгоритми

A*

Евристичний пошук: f(n) = g(n) + h(n), де g(n) — реальна відстань від старту, h(n) — евристична оцінка до мети. Оптимальний за допустимої евристики (h не переоцінює). Ефективний, широко використовується.

Greedy Best-First Search

Жадібний пошук: використовує тільки h(n), обирає найближчий до мети вузол. Швидкий, але може бути неоптимальним. Не гарантує найкоротший шлях.

Dijkstra

Алгоритм для знаходження найкоротших шляхів у зважених графах. Без евристики (h=0), еквівалентний UCS. Гарантує оптимальність. Використовується у мережах, навігації.

Bidirectional Search

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

💻 Оптимізації

Iterative Deepening

IDDFS: поєднання DFS та BFS. Повторює DFS зі збільшенням глибини. Переваги BFS (оптимальність) з малою пам'яттю DFS. Використовується коли пам'ять обмежена.

Beam Search

Обмежений BFS: зберігає тільки k найкращих вузлів на кожному рівні. Зменшує пам'ять, але може пропустити оптимальний шлях. Використовується у NLP (generation).

Pruning

Відсікання неперспективних гілок. Alpha-beta pruning для мінімакс, constraint propagation. Зменшує простір пошуку, прискорює.

🏭 Застосування

Навігація

GPS, маршрутизація: знаходження найкоротших/швидших шляхів. A*, Dijkstra для карт. Реальний час, великі графи.

Game Playing

Minimax з alpha-beta pruning для ігор (шахи, го). Пошук у дереві можливих ходів. Оптимізація рішень.

Планування

Автоматичне планування: пошук у просторі станів для знаходження послідовності дій. A*, heuristic search у планувальниках.

AI агенти

Пошук рішень для AI агентів: navigation, task planning. Критично для автономних систем.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Hash Function Avalanche Visualizer і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.