Алгозадачи 3: графы, кучи и динамика

Финальный уровень алгоблока. Здесь таблицы и массивы перестают быть просто хранилищами: из них собираются графы, очереди с приоритетом и таблицы подзадач. Всё построенное в уроке про структуры идёт в дело: куча ведёт Дейкстру, идеи ДНМ ждут тебя в упражнениях.

Граф это таблица массивов

Учебники рисуют графы кружочками, но в коде граф это ответ на один вопрос: кто соседи вершины? Значит, таблица «вершина, массив соседей»:

Вершинами годится что угодно, что можно положить ключом: числа, кейворды, строки, кортежи координат. Последнее сразу пригодится: клетка сетки [ряд столбец] это уже вершина графа, никакой перекодировки не нужно.

Обход в глубину: острова

Сетка из единиц и нулей, единицы это суша. Сколько островов? Задача Number of Islands, самая известная задача на обход в глубину.

План: идём по клеткам, встретили сушу, увеличили счётчик и затопили весь остров целиком, чтобы не посчитать его дважды. Сетку держим в буферах, они изменяемые, топить будем прямо в них:

Локальные defn внутри функции это обычные замыкания: land? и flood-fill видят сетку и размеры без передачи параметров.

Рекурсивное затопление лаконично, но глубина рекурсии равна размеру острова. Огромная сетка из сплошной суши положит стек. Лекарство ты уже собирал: рекурсия по сути пользуется стеком вызовов, замени его на явный стек-массив:

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

Топологическая сортировка: порядок курсов

Есть n курсов и зависимости «сначала пройди то, потом это». Можно ли пройти все, и в каком порядке? Задачи Course Schedule и Course Schedule II, а под капотом топологическая сортировка, тот же алгоритм, что решает порядок сборки пакетов в jpm и порядок миграций в базе.

Алгоритм Кана: считаем входящие рёбра, снимаем вершины, у которых их ноль, и уменьшаем счётчики соседей:

В учебнике здесь очередь, у нас array/pop, то есть стек. Это не ошибка: алгоритму Кана всё равно, в каком порядке снимать готовые вершины, любой порядок даст корректную топологическую сортировку. Очередь нужна, только если требуется конкретный порядок, например лексикографически наименьший, и тогда вместо неё берут кучу. В реестре пакетов ту же работу делает tsort, но теперь ты знаешь, что внутри у него двадцать строк.

Дейкстра: куча выходит на сцену

Взвешенный граф, старт, найти кратчайшие расстояния до всех вершин. Задача Network Delay Time даёт ей сюжет: сигнал расходится по сети, через сколько дойдёт до самого дальнего узла?

Жадная идея Дейкстры: из непосещённых вершин всегда обрабатывай ближайшую. «Дай минимум быстро» это ровно то, что умеет куча. Сохрани кучу из урока про структуры в файл heap.janet рядом с решением и подключи её как модуль, как в уроке про модули:

(use ./heap)

(defn shortest-paths [n edges start]
  (def neighbors (tabseq [i :range [0 n]] i @[]))
  (each [from to weight] edges
    (array/push (in neighbors from) [to weight]))
  (def dist (array/new-filled n math/inf))
  (put dist start 0)
  (def pq (heap/new (fn [a b] (< (first a) (first b)))))
  (heap/push pq [0 start])
  (label done
    (while true
      (def pair (heap/pop pq))
      (unless pair (return done))
      (def [d vertex] pair)
      # запись устарела: вершину уже достали с меньшим расстоянием
      (unless (> d (in dist vertex))
        (each [neighbor weight] (in neighbors vertex)
          (def next-dist (+ d weight))
          (when (< next-dist (in dist neighbor))
            (put dist neighbor next-dist)
            (heap/push pq [next-dist neighbor]))))))
  dist)

(shortest-paths 4 [[0 1 1] [0 2 4] [1 2 2] [2 3 1]] 0)
# @[0 1 3 4]

В куче лежат кортежи «расстояние и вершина», компаратор сравнивает первые элементы. Мы не удаляем из кучи устаревшие записи, это дорого, вместо этого пропускаем их при извлечении, сверившись с массивом расстояний. Ответ для Network Delay Time это максимум по массиву: (max ;dist), и если там math/inf, до кого-то сигнал не дошёл.

Время O(E log V): каждое ребро может положить в кучу одну запись, каждая операция кучи логарифмическая.

Динамика: размен монет

Даны номиналы монет и сумма. Каким минимальным числом монет её набрать? Задача Coin Change, дверь в динамическое программирование.

Рекурсивная формулировка честная: минимум монет для суммы это один плюс минимум по всем «сумма минус номинал». Беда в том, что подзадачи повторяются, и без кеша дерево вызовов взрывается экспоненциально. Мемоизация чинит это одной таблицей:

Две janetовские детали держат этот код: недостижимые суммы обозначены math/inf, а не nil, потому что put с nil удалил бы ключ из кеша, и (in cache 0) возвращает истинный ноль, потому что ноль в Janet истинен.

Тот же расчёт снизу вверх обходится без рекурсии вовсе: массив dp, где индекс это сумма, заполняется от нуля к цели:

Заметь, как два глагола в одном loop дали вложенный перебор «для каждой суммы, для каждой монеты». Обе версии O(сумма умножить на число номиналов). Рекурсия с кешем ближе к постановке задачи, таблица снизу вверх быстрее и не рискует стеком. Выбор тот же, что весь блок: сначала формулировка, потом стиль.

Что запомнить

• Граф это таблица «вершина, массив соседей». Кортеж координат уже вершина, кодировать клетки в числа не нужно.
• Обход в глубину: рекурсия или явный стек. Замена стека на очередь даёт обход в ширину.
• Алгоритм Кана: счётчики входящих рёбер, снимаем нулевые. Не снялись все, значит цикл. Порядок снятия не важен.
• Дейкстра это куча с кортежами «расстояние и вершина» плюс пропуск устаревших записей.
• Динамика в двух исполнениях: рекурсия с мемо-таблицей и массив снизу вверх. В кеше держи math/inf, а не nil: put с nil удаляет ключ.
• Все структуры блока сошлись: буферы под сетку, стек и очередь под обходы, куча под Дейкстру, таблица под мемоизацию.

Упражнения

Дальше

Алгоблок закрыт. Остался финальный урок раздела: карта экосистемы, идеи проектов и разговор о том, куда двигаться с Janet дальше.