Grundy
Иконка канала Grundy

Grundy

29 подписчиков

4просмотра

Статья и интерактив: https://grundyjs.ru/r/closest-pair-short/ Какие две точки ближе всего друг к другу? Для 12 точек полный перебор требует 66 вычислений расстояния. Разбираем другой подход — «разделяй и властвуй»: сортируем точки слева направо и делим задачу пополам. Находим ответы половин и проверяем узкую полосу у границы. Если более близкая пара состоит из точек по разные стороны границы, обе точки лежат в этой полосе. Просматриваем их снизу вверх и пропускаем пары, которые не могут улучшить ответ. На этом наборе оба метода находят пару E–F с расстоянием примерно 4,472. При разделении задачи получаем 21 вычисление расстояния вместо 66. Сортировка в этот счётчик не входит; числа относятся к показанному набору из 12 точек. В интерактиве можно двигать, добавлять и удалять точки, выбирать примеры и сравнивать методы по шагам. После правки нажмите «Сначала», затем «Старт». Свой набор можно передать по ссылке. Визуализация — AlgiViz, запись — CanvasTake. Авторская озвучка, без музыки. #ближайшаяПараТочек #геометрия #алгоритмы #ClosestPair #AlgiViz

202просмотра

Статья и интерактив: https://grundyjs.ru/r/delaunay-short/ Как соединить точки в сетку из треугольников? Разбираем триангуляцию Делоне: сетка покрывает выпуклую оболочку, её рёбра не пересекаются, а каждая исходная точка становится вершиной. Через три вершины каждого треугольника проводим окружность. Строго внутри ограниченного ею круга не должно быть других точек набора. На самой окружности дополнительные точки допустимы. На примере двух соседних треугольников проверяем окружность ABC: точка D оказалась внутри. Пара образует выпуклый четырёхугольник, поэтому меняем общую диагональ A–C на B–D и проверяем новые треугольники. Это метод переворотов рёбер, или метод Лоусона. Если все четыре точки лежат на одной окружности, допустимы обе диагонали — результат может быть не единственным. Затем включаем диаграмму Вороного: центры окружностей треугольников совпадают с её вершинами. В интерактиве можно двигать, добавлять и удалять точки, выбирать примеры, смотреть проверки окружностей по шагам и включать слой Вороного. После редактирования остаётся готовая сетка; для пошагового разбора нажмите «Сначала», затем «Старт». Свой пример можно передать по ссылке. Визуализация — AlgiViz, запись — CanvasTake. Авторская озвучка, без музыки. #триангуляцияДелоне #геометрия #алгоритмы #Вороной #Delaunay

80просмотров

Статья и интерактив: https://grundyjs.ru/r/convex-hull-short/ Как найти внешнюю границу набора точек? Представим натянутую вокруг них резинку: она охватывает весь набор и держится за крайние точки. Эта граница вместе с областью внутри — выпуклая оболочка. Разбираем алгоритм Эндрю: упорядочиваем точки слева направо, строим нижнюю и верхнюю цепочки, затем соединяем их. Для проверки берём две последние точки цепочки и следующую точку набора. Если путь через них поворачивает вправо или все три лежат на одной прямой, убираем из текущей цепочки вторую точку тройки. Повторяем проверку перед добавлением новой точки. Точка, убранная из нижней цепочки, может войти в верхнюю — из набора она не удаляется. Перемещаем внутреннюю точку за границу и наблюдаем изменение оболочки. Если все точки лежат на одной прямой, результат — отрезок между двумя крайними. В статье можно двигать, добавлять и удалять точки, выбирать готовые примеры и разбирать построение по шагам. После редактирования остаётся готовая оболочка; для пошагового разбора нажмите «Сначала», затем «Старт». Есть ссылка на свой пример и экспорт анимации. Визуализация — AlgiViz, запись — CanvasTake. Авторская озвучка, без музыки. #выпуклаяОболочка #алгоритмЭндрю #геометрия #алгоритмы #ConvexHull

8просмотров

Статья и интерактив: https://grundyjs.ru/r/voronoi-short/ Как поделить поле между несколькими точками? Разбираем диаграмму Вороного: у каждой точки своя ячейка, а вместе они образуют мозаику. Из любого места внутри ячейки расстояние до её исходной точки меньше, чем до остальных. На общей границе расстояния до ближайших точек равны. Начинаем с двух точек: граница проходит через середину соединяющего их отрезка под прямым углом. Добавляем третью и строим ячейки, отсекая места, где другая точка ближе. Сравнение повторяется со всеми остальными точками. Перемещаем одну точку — границы перестраиваются. Здесь расстояние измеряется по прямой, без учёта дорог и препятствий. Край картинки только обрезает диаграмму: некоторые ячейки продолжаются за ним. В статье можно двигать, добавлять и удалять точки, проверять расстояния и разбирать построение по шагам. После изменения точек остаётся готовая диаграмма; для пошагового разбора нажмите «Сначала», затем «Старт». Есть ссылка на свой пример и экспорт анимации. Визуализация — AlgiViz, запись — CanvasTake. Авторская озвучка, без музыки. #диаграммыВороного #Voronoi #геометрия #алгоритмы #визуализация

7просмотров

Статья и интерактив: https://grundyjs.ru/r/rule-30-short/ Как из одной чёрной клетки получается сложный узор? Разбираем «Правило 30» — одномерный клеточный автомат с восемью ответами. Ноль — белая клетка, один — чёрная. Следующее значение зависит от тройки в старом ряду: левого соседа, самой клетки и правого соседа. Все клетки нового ряда читают старый и меняются одновременно. Ряды показывают историю: время идёт вниз. После одной чёрной клетки в следующем ряду появляются три. Но порядок соседей имеет значение: 011 даёт 1, а 110 — 0. Узор теряет симметрию. Записываем восемь ответов от тройки 111 до 000: получается 00011110₂ — двоичная запись числа 30. Если изменить только ответ для 110 с 0 на 1, получится правило 94. Сравниваем его в отдельном запуске с тем же начальным рядом. Случайных решений нет: одинаковые правило и начальный ряд дают одинаковую историю. На видео ряд конечный — 61 клетка. За его пределами считывается ноль; крайние клетки обновляются, края не соединяются. В статье можно менять начальный ряд, выбирать правило от 0 до 255 или редактировать восемь ответов, проверять поколения по шагам и перематывать историю. Есть ссылка на свой запуск и экспорт анимации. Визуализация — AlgiViz, запись — CanvasTake. Авторская озвучка, без музыки. #Правило30 #Rule30 #клеточныеавтоматы #алгоритмы #визуализация

5просмотров

Статья и интерактив: https://grundyjs.ru/r/langtons-ant-short/ Как из двух простых правил получается дорога? Разбираем муравья Лэнгтона — клеточный автомат на бесконечном клетчатом поле. Муравей читает цвет клетки под собой: на белой поворачивает на 90° направо, на чёрной — на 90° налево. Затем меняет цвет этой же клетки на противоположный и делает шаг вперёд. Цвет клетки, в которую он пришёл, пока не меняется. Через четыре шага муравей возвращается в исходную точку. Но клетка под ним уже чёрная, поэтому на пятом шаге он поворачивает налево. В показанном запуске всё поле изначально белое. После примерно десяти тысяч шагов появляется диагональное шоссе: цикл из 104 шагов повторяется со сдвигом на две клетки по каждой оси. Это наблюдение для данного старта, а не утверждение о любом начальном узоре. В статье можно менять начальные клетки и направление муравья, идти по шагам, перематывать историю и переключать камеру. Доступны ссылка на свой запуск и экспорт анимации. Поле не имеет стен и не замыкается по краям — экран показывает только его часть. Визуализация — AlgiViz, запись — CanvasTake. Авторская озвучка, без музыки. #МуравейЛэнгтона #LangtonsAnt #алгоритмы #клеточныеавтоматы #визуализация

7просмотров

Статья и интерактив: https://grundyjs.ru/r/game-of-life-short/ Как пять клеток могут ползти по полю, если ни одна из них не движется? Разбираем «Игру Жизнь» — клеточный автомат Конвея. Мёртвая клетка становится живой, если у неё ровно три живых соседа. Живая клетка умирает, если живых соседей меньше двух или больше трёх. В остальных случаях состояние сохраняется. Все клетки читают прежнее поле и обновляются одновременно. Мигалка возвращается к исходной форме через два шага, блок остаётся неподвижным, а глайдер за четыре шага повторяет форму на клетку правее и ниже. Меняются состояния клеток — так возникает движение фигуры. В интерактивном примере можно рисовать и стирать клетки, выбирать готовые фигуры, проходить поколения по шагам и разбирать соседство выбранной клетки. Доступны перемотка, ссылка на своё поле и экспорт анимации. Поле конечное: снаружи клетки считаются мёртвыми, противоположные края не соединяются. Визуализация — AlgiViz, запись — CanvasTake. Авторская озвучка, без музыки. #ИграЖизнь #GameOfLife #Конвей #клеточныеавтоматы #визуализация

4просмотра

Интерактивный разбор: https://grundyjs.ru/r/falling-sand-short Откуда берётся горка песка, если каждая песчинка знает только соседние клетки? Открываем затвор и разбираем три правила: падение, скатывание и покой. Останавливаем одну песчинку и смотрим на три клетки под ней. Затем разбираем конфликт: две песчинки выбирают одну цель, но переместиться может только одна. Все решения принимаются по старому полю, а перемещения выполняются после разрешения конфликтов. В интерактивном примере можно насыпать песок, рисовать и стирать препятствия, открывать затвор, выбирать полки или два прохода, разбирать одну песчинку и проходить симуляцию по шагам. Это учебная клеточная модель, а не точная физика сыпучих материалов. Визуализация — AlgiViz, запись — CanvasTake. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельно. #песок #симуляция #алгоритмы #визуализация #программирование

6просмотров

Интерактивный разбор: https://grundyjs.ru/r/boids-short/ Как десятки птиц поворачивают вместе? В модели Boids движение стаи возникает из трёх локальных правил: разделения, выравнивания и сближения. Останавливаем одну птицу и разбираем её соседей. Жёлтая стрелка показывает разделение, синяя — выравнивание, фиолетовая — сближение. Зелёная — сумма поправок скорости, а белый пунктир — курс на следующий шаг. Добавляем островки, стенку и узкий проход. Розовая стрелка отвечает за обход препятствий и входит в общую поправку скорости. Это учебная модель локального поведения; она не строит маршрут всей стаи к цели. В интерактивном примере на сайте можно менять число птиц и seed, отключать правила, выбирать препятствия, разбирать одну птицу, проходить шаги, делиться ссылкой на состояние и сохранять анимацию. Визуализация — AlgiViz, запись — CanvasTake. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельно. #Boids #стая #алгоритмы #визуализация #программирование

101просмотр

Интерактивный разбор: https://grundyjs.ru/r/scc-short/ Компоненты сильной связности — группы вершин ориентированного графа, внутри которых из каждой вершины можно добраться до любой другой. Сравниваем алгоритмы Косарайю и Тарьяна на одном графе. Косарайю делает два обхода: сначала записывает порядок выхода в исходном графе, затем разворачивает все стрелки и обходит граф в обратном порядке выхода. Тарьян использует один DFS, номера посещения, метки low и отдельный стек ещё не выделенных вершин. Этот стек отличается от текущего пути DFS. По ребру в вершину из стека Тарьяна учитываем её номер посещения, а при возврате из дочерней ветки — её low. Когда после проверки исходящих рёбер low равна номеру вершины, снимаем вершины со стека до неё включительно: это одна готовая компонента. В примере получаются {A, B, C}, {D, E} и {F, G}. Порядок выдачи у алгоритмов различается, состав групп совпадает. Добавьте ребро F → B в интерактивном примере и проверьте, сколько компонент останется. На сайте можно выбирать готовые графы, менять вершины и рёбра, проходить шаги, делиться ссылкой и сохранять анимацию. Такты анимации и счётчики не сравнивают время работы алгоритмов. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельно. #алгоритмы #Косарайю #Тарьян #графы #программирование

88просмотров

Интерактивный разбор: https://grundyjs.ru/r/topological-sort-short/ В каком порядке выполнять задачи с зависимостями? Топологическая сортировка располагает все вершины так, чтобы для каждого направленного ребра его начало стояло раньше конца. Сравниваем алгоритм Кана и поиск в глубину (DFS) на одном графе. Кан считает входящие рёбра и хранит готовые вершины в FIFO-очереди. После A вершина C ещё ждёт B; когда степень становится нулевой, добавляем вершину в конец очереди. DFS хранит текущий путь в стеке, записывает вершины после проверки исходящих рёбер и разворачивает полный порядок выхода. В примере без цикла Кан получает A, B, C, D, E, F, а DFS — B, D, A, C, E, F. Оба ответа соблюдают все зависимости. В другом примере Кан выдаёт только A, затем очередь пустеет. DFS находит конкретный цикл B → C → D → B. Вершины E и F тоже заблокированы, но в этот цикл не входят. При цикле полного топологического порядка нет. В интерактивном разборе можно выбирать готовые графы или менять зависимости, проходить шаги, сравнивать состояния, делиться ссылкой и сохранять анимацию. Такты анимации и счётчики рёбер не являются сравнением времени работы алгоритмов. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельно. #алгоритмы #топологическаясортировка #DFS #графы #программирование

297просмотров

Интерактивный разбор: https://grundyjs.ru/r/dsu-short/ Как быстро узнать, входят ли два элемента в одно множество? Система непересекающихся множеств (DSU, Union-Find) хранит группы как лес родительских ссылок. У каждой группы есть корень — представитель множества. find находит этот корень, union объединяет две группы, same сравнивает их представителей. На четырёх элементах A, B, C, D создаём две группы, затем объединяем их по размеру. При равных размерах сохраняем корень A. Первый поиск из D проходит D → C → A; сжатие пути заменяет ссылку D → C на D → A. Повторный поиск делает один переход. Состав множества и размер корня не меняются. B и D уже в одной группе: повторное объединение не увеличивает размер и не уменьшает число множеств. Так Краскал проверяет, не создаёт ли очередное ребро цикл. Обычная DSU умеет объединять множества, но не разделять их. Стрелки parent — внутренние ссылки DSU, а не рёбра исходного графа. В интерактивном примере можно менять число элементов и команды find, union, same, проходить шаги, делиться ссылкой и сохранять анимацию. Сравнение двух и одного перехода относится к показанному пути; это не замер времени и не гарантия одного перехода для любой операции. Авторская озвучка, без музыки. #алгоритмы #DSU #UnionFind #структурыданных #программирование

145просмотров

Интерактивное сравнение: https://grundyjs.ru/r/maze-generation-short/ На одинаковой сетке 9×7 с seed 34 сравниваем три рандомизированных генератора лабиринтов. Синий DFS продолжает текущую ветку, выбирая непосещённого соседа. Когда вариантов нет, возвращается по стеку. Жёлтый Прим расширяет одну связанную область: случайно выбирает стену из кандидатов и присоединяет новую клетку; устаревшие кандидаты отбрасывает. Зелёный Краскал заранее перемешивает внутренние стены и соединяет разные компоненты, пропуская стены, удаление которых создало бы цикл. У каждого результата 63 клетки и 62 прохода, без циклов: между любыми двумя клетками есть единственный путь. В этом примере тупиков у DFS — 8, у Прима — 23, у Краскала — 20. Это свойства конкретного seed, а не универсальный рейтинг алгоритмов или сложности прохождения. Равномерная выборка всех возможных лабиринтов не обещается. Одновременные фазы анимации сравнивают решения, а не скорость вычислений. В интерактивном примере можно менять размер и seed, проходить шаги, включать полный экран, делиться ссылкой на свой запуск и сохранять видео. Авторская озвучка, без музыки. #алгоритмы #лабиринт #DFS #Прим #Краскал #программирование

7просмотров

Интерактивное сравнение: https://grundyjs.ru/r/mst-comparison-short/ Сравниваем два алгоритма на одном неориентированном взвешенном графе. Прим растит одно дерево: каждый раз выбирает самое дешёвое ребро между уже присоединёнными вершинами и остальным графом. Краскал рассматривает рёбра всего графа по возрастанию веса и соединяет разные компоненты, пропуская циклы. Прим от A выбирает A—C = 2, C—B = 1, C—E = 5 и E—D = 2. Краскал выбирает B—C = 1, A—C = 2, D—E = 2 и C—E = 5; A—B = 4 пропускает, поскольку его концы уже соединены через C. После третьего принятого ребра у Прима сумма 8, у Краскала — 5. Это промежуточные состояния: в конце оба получают четыре ребра и общую стоимость 10. Синий — Прим, зелёный — Краскал. Общие рёбра показаны параллельными цветными линиями. Краскал временно строит несколько отдельных деревьев. Это сравнение порядка выбора, а не замер скорости: синхронные фазы анимации не равны времени работы алгоритмов. Минимальный остов всей сети и кратчайшие пути от старта — разные задачи. В интерактивном примере можно менять граф, веса и старт Прима, проходить сравнение по шагам, поделиться ссылкой на свой граф и сохранить анимацию. Нулевые и отрицательные веса допустимы; в несвязном графе оба алгоритма строят минимальный остовный лес. Авторская озвучка, без музыки. #алгоритмы #Прим #Краскал #графы #программирование

208просмотров

Интерактивный разбор: https://grundyjs.ru/r/kruskal-short/ Алгоритм Краскала строит минимальное остовное дерево неориентированного взвешенного графа: соединяет все вершины без циклов с минимальной суммой весов рёбер. Сортируем рёбра всего графа по весу. Если концы ребра находятся в разных компонентах — берём ребро и объединяем их. Если вершины уже связаны — пропускаем ребро, чтобы не создать цикл. На этом графе выбираются B—C = 1, A—C = 2, D—E = 2 и C—E = 5. Ребро A—B = 4 пропускаем: его концы уже связаны через C. Получается четыре ребра с общей стоимостью 10. Как только все вершины соединены, остальные рёбра проверять не нужно. У Прима на том же графе та же сумма, но другой порядок выбора. Минимальная стоимость всей сети и кратчайшие пути от старта — разные задачи. Нулевые и отрицательные веса допустимы. При B—C = −3 и D—E = 0 сумма становится 4. В несвязном графе получаем минимальный остовный лес: в примере два дерева, три ребра и общая сумма 5. В интерактивном примере можно менять веса, проходить алгоритм по шагам, поделиться своим графом и сохранить анимацию. Зелёный — выбранный остов, жёлтый — текущее ребро, пунктир — пропущенное ребро цикла. Группы под графом показывают компоненты, список справа — порядок рёбер. Авторская озвучка, без музыки. #алгоритмы #Краскал #графы #деревья #программирование

6просмотров

Интерактивный разбор: https://grundyjs.ru/r/prim-short/ Алгоритм Прима строит минимальное остовное дерево неориентированного взвешенного графа: соединяет все вершины без циклов с минимальной суммой весов рёбер. На каждом шаге выбираем самое лёгкое ребро на всей границе уже построенного дерева — из включённой вершины в ещё не включённую. На этом графе выбираются A—C = 2, C—B = 1, C—E = 5 и E—D = 2. Получается четыре ребра с общей стоимостью 10. После добавления B следующее ребро выходит из более ранней C: сравниваем всю границу, а не только последнюю вершину. Это минимум стоимости всей сети; кратчайшие пути от старта — другая задача. Нулевые и отрицательные веса допустимы. При B—C = −3 и D—E = 0 сумма становится 4. Если убрать связи между группами A,B,C и D,E, Прим построит минимальный остовный лес: два дерева, три ребра и общая сумма 5. В интерактивном примере можно менять веса и старт, проходить алгоритм по шагам, поделиться своим графом и сохранить анимацию. Синий пунктир показывает все рёбра границы одновременно, жёлтый — выбранный минимум, зелёный — остов. Авторская озвучка, без музыки. #алгоритмы #Прим #графы #деревья #программирование

4просмотра

Интерактивное сравнение: https://grundyjs.ru/r/shortest-path-short/ На одном ориентированном графе сравниваем три алгоритма. Дейкстра закрепляет вершину с наименьшей известной стоимостью от старта и требует неотрицательных весов. Беллман — Форд повторяет полные проходы по рёбрам; он допускает отрицательные веса. Оба вычисляют расстояния от одного источника. Флойд — Уоршелл разрешает промежуточные вершины по очереди и вычисляет матрицу расстояний между всеми парами. Для сравнения берём её строку A. На исходных весах все три находят путь A → B → C → D: 3 + 2 + 2 = 7. После изменения B → C на −2 стоимость становится 3. Дейкстру в этом режиме не запускаем; Беллман — Форд и Флойд — Уоршелл продолжают работать. Добавляем C → B веса 1: цикл B → C → B стоит −1. Повторяя его, можно удешевлять путь из A в D сколько угодно — конечного минимума нет (−∞). Но D → D остаётся 0: от D этот цикл недостижим. Обратного пути D → A нет (∞). При единичных весах минимальная стоимость совпадает с минимальным числом рёбер: прямое ребро A → D даёт стоимость 1. Такты анимации показывают этапы алгоритмов, а не замер быстродействия. В интерактивном примере можно менять веса, источник и цель, сравнивать этапы и поделиться ссылкой на свой граф. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #Дейкстра #БеллманФорд #ФлойдУоршелл #графы #программирование

216просмотров

Интерактивный разбор Флойда — Уоршелла: https://grundyjs.ru/r/floyd-warshall-short/ Флойд — Уоршелл находит минимальную стоимость путей сразу между всеми парами вершин. В матрице строка задаёт начало, столбец — конец. На каждом этапе разрешаем ещё одну промежуточную вершину k и проверяем d(i,j) = min(d(i,j), d(i,k) + d(k,j)). В примере прямой путь A → D стоит 10. Через B получается 3 + 6 = 9. Через C — маршрут A → B → C → D стоимостью 3 + (−2) + 2 = 3. Ячейки одного этапа обновляются вместе из предыдущего слоя матрицы. Обратного пути D → A здесь нет: ∞ означает недостижимость. Если все веса равны единице, минимальная стоимость совпадает с минимальным числом рёбер. В этом примере прямое ребро A → D тогда даёт стоимость 1. Отрицательные рёбра допустимы. Отрицательное число на диагонали после основных этапов указывает на отрицательный цикл. Цикл B → C → B стоит −2 + 1 = −1. Для пар, чей маршрут может пройти через такой цикл, конечного минимума нет: −∞. Остальные ответы сохраняются. Время O(V³), матрицы расстояний и восстановления маршрутов занимают O(V²). В интерактивном примере можно менять веса, выбирать пару вершин и смотреть этапы алгоритма, а также поделиться ссылкой на свой граф. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #ФлойдУоршелл #графы #программирование

7просмотров

Интерактивный разбор Беллмана — Форда: https://grundyjs.ru/r/bellman-ford-short/ Беллман — Форд ищет минимальную стоимость пути в ориентированном графе, в том числе с отрицательными весами. На каждом проходе проверяет все рёбра: если d(u) + вес меньше d(v), обновляет расстояние и предка. В исходном примере четыре вершины и три основных прохода. После первого прохода d(A) = 2, d(B) = 5. Во втором цель сначала получает оценку 4, а отрицательное ребро B → A улучшает A до 1. На третьем проходе стоимость до цели уменьшается до 3. Итоговый путь S → B → A → G: 5 − 4 + 2 = 3. После основных проходов выполняется отдельная контрольная проверка. Если достижимую оценку всё ещё можно улучшить, есть отрицательный цикл, достижимый от старта. Добавим A → B с весом 3: цикл A → B → A стоит 3 − 4 = −1. Каждый круг уменьшает стоимость. Из цикла можно попасть в G, поэтому для цели нет конечного минимума: d(G) = −∞. Недостижимый от старта цикл X ↔ Y на ответ не влияет: путь к G по-прежнему стоит 3. Отрицательное ребро само по себе не означает отрицательного цикла. Если достижимый цикл не ведёт к выбранной цели, стоимость до этой цели может оставаться конечной. На первой найденной оценке цели останавливать алгоритм нельзя. В интерактивном разборе можно пройти алгоритм по шагам, изменить вес ребра, выбрать старт и цель, сравнить пять примеров и поделиться своим графом. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #БеллманФорд #графы #программирование

155просмотров

Интерактивное сравнение BFS, Дейкстры и A*: https://grundyjs.ru/r/weighted-maze-short/ Один взвешенный лабиринт, одинаковые старт и выход — три правила выбора следующей клетки. Синий BFS ищет минимум по числу переходов и не учитывает цену клеток. Жёлтый алгоритм Дейкстры выбирает минимальную известную стоимость от старта. Фиолетовый A* добавляет к ней оценку оставшегося пути: расстояние по горизонтали и вертикали без учёта стен, умноженное на минимальную цену шага. Результаты исходной карты: • BFS: 16 переходов, стоимость 22, обработано 76 клеток. • Дейкстра: 18 переходов, стоимость 18, обработано 62 клетки. • A*: 18 переходов, стоимость 18, обработана 31 клетка. Больше переходов, зато дешевле. При единичных весах стоимость равна числу переходов: все три поиска находят путь из 16 переходов стоимостью 16. Ветви одной волны показаны одновременно, исчерпанные тупики сереют. У алгоритмов разные приоритеты; длительность анимации не измеряет быстродействие программы. На другой карте преимущество A* по числу обработанных клеток может измениться. В интерактивном разборе меняйте цену клетки, проходите поиск по шагам и сравнивайте результаты. Авторская озвучка. Музыки нет. #алгоритмы #BFS #Дейкстра #AStar #программирование