BFS, Дейкстра и A*: один взвешенный лабиринт

Начальный пример

Это результаты исходной карты без изменений. После редактирования карты результаты могут измениться у всех трёх алгоритмов.

Одна карта, разные правила выбора

BFS извлекает клетки из очереди FIFO и запоминает первый путь к каждой. Он минимизирует число переходов, не учитывая местность. Его цена в таблице — сумма по выбранному маршруту, без гарантии минимальной стоимости.

Дейкстра выбирает минимальную известную стоимость g из всей границы. A* выбирает минимум g + h. Оба обновляют расстояние и предка, если нашли более дешёвый путь. Соседей смотрим через открытые проходы в порядке север/восток/юг/запад. При равных приоритетах раньше обрабатываем клетку, которая раньше получила текущую оценку; улучшение оценки даёт новый порядок в очереди. Цель проверяем при извлечении, а не при первом обнаружении.

Вход в клетку стоит 1, 3 или 7. Оплачиваем следующую клетку, включая G; старт S бесплатный. Проход работает в обе стороны, но вход в разную местность может стоить по-разному. Редактор меняет цены и точки сразу для трёх поисков; стены остаются прежними.

Почему A* сохраняет минимальную стоимость

Здесь h — манхэттенское расстояние до G, умноженное на минимальную цену клетки на карте. Оценка игнорирует стены и считает все оставшиеся переходы самыми дешёвыми. Поэтому она не завышает оставшуюся стоимость.

За один переход h уменьшается максимум на одну минимальную цену — не больше реальной стоимости входа. Такая эвристика согласованна: извлечённую клетку не требуется открывать заново. Дейкстра и A* находят минимальную стоимость; при нескольких одинаково дешёвых маршрутах пути могут отличаться. Оценка не обещает сокращение работы на любой карте.

При единичных весах цена пути равна числу переходов. Все три поиска тогда минимизируют одну величину, хотя A* может раскрывать клетки в другом порядке.

Что измеряет общий такт

Когда в исследованной ветви не осталось ожидающих клеток, она становится тонкой и серой, а её движущаяся точка гаснет после завершения отрезка. Общий ствол остаётся цветным, пока в другой ветви есть работа. Статус определяется очередью и связями с предками на текущем шаге.

Один визуальный шаг объединяет уже ожидающие к его началу клетки с минимальным приоритетом: BFS по глубине, Дейкстра по g, A* по g + h. Все их отрезки растут одновременно. Новые клетки и клетки с улучшенной оценкой ждут последующих волн по своему приоритету, даже если A* даёт им приоритет текущей волны. Поэтому предок уже обработан до начала волны: линии растут из связанных ветвей, а не от другой движущейся точки. Внутри алгоритмы по-прежнему извлекают клетки последовательно и останавливаются сразу при извлечении G, в том числе посреди последней волны.

Тонкие линии показывают исследованные ветви, яркие точки — текущую волну, более яркая и толстая линия — найденный маршрут. Завершившийся поиск сохраняет результат, пока остальные продолжают. Местность нейтральная, клетка без числа стоит 1; цвета обозначают только алгоритмы. У трёх поисков разные шкалы волн, поэтому время окончания анимации и число волн не сравнивают скорость процессора.

«Раскрыто» считает извлечённые клетки, включая G. Цена пути и число переходов появляются после извлечения цели. «Граница» — ожидающие клетки, без извлечённой. Скорость тактов — темп воспроизведения, а не замер времени процессора. Число раскрытий зависит от порядка соседей, правил равенства и эвристики.

Флажки над картой показывают один или несколько следов, не меняя расчёт сравнения. Линии поиска можно скрыть, а точки ожидающих клеток — включить для продолжающихся поисков. Над каждым следом видны текущая глубина или приоритет и число клеток в волне. Можно остановить поиск, шагать в обе стороны, выбрать шаг на шкале или сразу перейти к результату. Шаги и перемотка показывают полные волны; режим уменьшенного движения отключает анимацию отрезков. Координаты в редакторе позволяют менять карту без нажатий на canvas. Ошибка координат сохраняет текущий лабиринт и историю поиска.

Стоимость этой реализации

BFS использует очередь с движущимся началом: O(V+E) времени. Дейкстра и A* ищут минимум проходом по массиву: O(V²+E), а не оценка для кучи. Рабочая память каждого алгоритма без входного графа — O(V). Для воспроизведения сохраняется O(V) данных после каждого из не более V извлечений: дополнительно O(V²) памяти на алгоритм. Неизменяемая карта общая для трёх историй; модель ограничивает сравнение 256 клетками.

Компактный код ниже вычисляет результат без истории визуализации. adjacency — упорядоченные списки {to, weight}; в сетке вес ребра равен цене входа в следующую клетку. Для A* передайте описанную выше согласованную манхэттенскую оценку (нулевая оценка по умолчанию превращает A* в Дейкстру).

Реализация на JavaScript

function search(adjacency, start, goal, method, heuristic = () => 0) {
  const n = adjacency.length;
  const valid = v => Number.isInteger(v) && v >= 0 && v < n;
  if (!["bfs", "dijkstra", "astar"].includes(method) || !valid(start) || !valid(goal))
    throw Error("Invalid search parameters");
  for (const neighbors of adjacency) for (const {to, weight} of neighbors)
    if (!valid(to) || !Number.isInteger(weight) || weight < 1 || weight > 9)
      throw Error("Expected entry costs from 1 to 9");
  const g = Array(n).fill(Infinity), parent = Array(n).fill(null);
  const priorityOrder = Array(n).fill(Infinity);
  const closed = Array(n).fill(false), open = [start];
  let head = 0, expanded = 0, order = 1;
  g[start] = 0;
  priorityOrder[start] = 0;
  const priority = v => g[v] + (method === "astar" ? heuristic(v) : 0);
  while (head < open.length) {
    let current;
    if (method === "bfs") current = open[head++];
    else {
      let best = 0;
      for (let i = 1; i < open.length; i++)
        if (priority(open[i]) < priority(open[best]) ||
            (priority(open[i]) === priority(open[best]) && priorityOrder[open[i]] < priorityOrder[open[best]])) best = i;
      current = open.splice(best, 1)[0];
    }
    expanded++; closed[current] = true;
    if (current === goal) {
      const path = [];
      for (let v = goal; v !== null; v = parent[v]) path.push(v);
      return { path: path.reverse(), cost: g[goal], expanded };
    }
    for (const {to, weight} of adjacency[current]) {
      if (closed[to]) continue;
      const unseen = !Number.isFinite(g[to]), candidate = g[current] + weight;
      if (method === "bfs" ? !unseen : candidate >= g[to]) continue;
      g[to] = candidate; parent[to] = current;
      priorityOrder[to] = order++;
      if (unseen) open.push(to);
    }
  }
  return null;
}