Кратко и по делу — сравнение по ключевым параметрам, примеры и приёмы уменьшения памяти.

1) Что делает каждый алгоритм (интуитивно)

BFS — ищет кратчайший путь по числу рёбер (единые/неважные веса). Исследует граф слоями.Dijkstra — ищет минимальную суммарную стоимость в графе с неотрицательными весами рёбер.A* — Dijkstra с эвристикой h(n), направляющей поиск; изучает вершины по f(n)=g(n)+h(n).

2) Применимость и требования

BFS
Когда применять: граф/решётка с равными (единичными) или отсутствующими весами, нужна минимальная длина по числу шагов.Требования: нет эвристики; работает и на неориентированных/ориентированных графах.Противопоказано: когда веса различны и важна общая стоимость.Dijkstra
Когда применять: веса рёбер ≥ 0, нужно найти кратчайший путь по сумме весов.Требования: веса неотрицательны (иначе Bellman–Ford).Эвристика не требуется (всё равно оптимален).A*
Когда применять: тот же класс задач, что Dijkstra, но есть информативная эвристика h(n) приближающая оставшийся путь — ускоряет поиск.Требования к эвристике: чтобы алгоритм гарантировал оптимальность, h должна быть admissible (не переоценивает истинную минимальную оставшуюся стоимость). Лучше — также consistent (монoтонная): h(u) ≤ w(u,v) + h(v); тогда нет необходимости повторно открывать вершины.Противопоказано: если хорошей эвристики нет — A* деградирует до Dijkstra.

3) Сложности (временная и по памяти)
(пусть V — число вершин, E — число рёбер, b — branching factor, d — глубина решения)

BFS
Время: O(V + E) (при реализации через очередь и отметки посещённых).Память: O(V) (хранит фронт и массив visited; в неявно заданных ветвящихся пространствах — O(b^d)).Dijkstra (с бинарной кучей)
Время: O(E + V log V) или O(E log V) (в зависимости от реализации).Память: O(V) (таблицы расстояний, parent, очередь).A*
Время: в худшем случае экспоненциально по d (или O(E) в графовом представлении); практическое время зависит от качества эвристики — чем ближе h к истинному расстоянию, тем меньше исследуется вершин. В формализованном виде часто O(b^{εd}), где ε отражает качество эвристики.Память: O(V) (хранит Open и Closed; в пространственных задачах — обычно O(b^d)). A* сильно завязан на памяти — часто основное ограничение.

4) Требования к эвристике (A*)

Admissible (не переоценивает): обеспечивает оптимальность.Consistent (монoтонная): упрощает реализацию — не приходится повторно обрабатывать закрытые вершины; большинство практических эвристик (Манхэттен, Евклид) — консистентны.Чем информативнее (ближе к истинной стоимости), тем меньше узлов будет исследовано.Пример плохой эвристики: переоценивающая — может дать неверный (неоптимальный) путь.

5) Примеры задач, где каждый алгоритм оптимален

BFS: лабиринт/решётка без весов, задача "минимум ходов" (например, найти минимальное число ходов конём на шахматной доске между двумя клетками при одинаковой стоимости хода).Dijkstra: дорожная карта с разными положительными длинами/временами — найти маршрут с минимальным суммарным временем/расстоянием (например, навигация по города с разными скоростями/расстояниями).A*: путь на регулярной сетке/карте, где есть естественная и легко вычислимая эвристика (Манхэттен для 4-направленных сеток, Евклид для движения в непрерывной плоскости) — оптимален по времени/исследованию узлов при сохранении оптимальности пути.

6) Модификации и приёмы для экономии памяти (с указанием компромиссов)

Итеративное углубление
IDDFS (для не взвешенных графов): O(b^d) время, O(d) память. Хорошо, когда глубина невелика.IDA (Iterative Deepening A)
Итеративное углубление по порогу f; использует рекурсивный обход, память O(d), но время возрастает (повторное исследование ветвей).Применимо при ограниченной памяти, широко используется в задачах типа 15‑пазла.RBFS (Recursive Best-First Search)
Рекурсивный, использует O(d) памяти, похож по идее на A*, может расходовать больше времени.SMA (Simplified Memory-bounded A)
Настаивает на лимите памяти; удаляет наименее перспективные узлы, но сохраняет информацию для восстановления; при переполнении памяти может выбросить узлы и тем самым увеличить время.Beam search
Хранит только k лучших узлов на каждом уровне; экономия памяти и времени, но не гарантирует оптимальность (жёсткий компромисс).Bidirectional search / Bidirectional A*
Два односторонних поиска (от старта и от цели) встречаются посередине; уменьшает время и память примерно до O(b^{d/2}). Требует возможности теста встречного расширения и часто согласования эвристик.Компрессия хранилища
Хранить parent-указатели в компактной форме; хранить только хэши состояний; использовать диск/внешнюю память (external-memory algorithms).Использование Bloom-фильтров для closed set
Экономит память, но допускает ложные позитивы => возможна потеря оптимального пути (или его повторное исследование при ошибке).Хеш‑таблицы с вытеснением / partial transposition tables
Аналогично шахматным движкам — хранят только часть состояния.Иерархические/преобработанные структуры
Contraction Hierarchies, Landmark‑based (ALT) — уменьшают размер поискового пространства и время, часто используют дополнительную компактную предобработку (полезно для больших дорожных графов).Специальные оптимизации для сеточных карт
Jump Point Search (для лишённой препятствий прямоугольной сетки) — сокращает количество узлов; сохраняет оптимальность (при соответствующей эвристике).Хранение только frontier и релевантных backpointers
Не хранить полный closed set, а при реконструкции пути восстанавливать некоторые промежуточные контрольные точки.

7) Практические рекомендации по выбору

Если веса равны/важен минимум шагов → BFS.Если веса положительны и эвристики нет/никто не знает → Dijkstra.Если веса положительны и есть хорошая адекватная эвристика → A* (обычно быстрее в практических задачах).Если память критична → рассмотреть IDA, RBFS, SMA или bidirectional search; если можно пожертвовать оптимальностью — beam search.Для больших карт/сетьей маршрутов — применять предобработку (contraction hierarchies, ALT), чтобы снизить память/время при многократных запросах.

Если хотите, могу:

показать псевдокод IDA/SMA или сравнить на конкретном примере (сеточная карта 1000×1000),подобрать эвристику для вашей задачи и оценить экономию поиска.