Продвинутые алгориты на графах

  1. [5 минут] Анонс. Выбор тех, кто пишет конспект.
  2. [10 минут] Концовка Гольдбега.
  3. [25 минут] Алгоритм Йена'71 поиска k-го кратчайшего пути
    1. Формулировка: возьмем все простые пути, отсортируем их по весу, нужно в этом порядке найти k-й объект
    2. Описание алгоритма: возьмём начало пути, другое ребро, кратчайший конец пути. Все не перебранные ещё пути разбиваются на множества.
    3. Оценка: память O(kn), время O(kn*Dijkstra).
    4. Область применения: к любому инкрементальному алгоритму − k-й остов (обсуждаем подробно), k-е паросочетние, k-й разрез
  4. [15 минут] От 1-k-bfs к Radix heap
    1. Цель: 1-k-bfs + dijkstra + magic = O(E + Vlogk) для той же задачи.
    2. Вспоминаем алгоритм за O(E + Vk) для графов с весами от 1 до k. Говорим, что можно хранить только k+1 очередь.
    3. Замечаем похожесть Дейкстры и 1-k-bfs. По ходу алгоритма Дейкстры есть три множества вершин: A, B, C. Расстояния в B отличаются не более чем на k.
    4. Сделаем из него O(Elogk) (куча номеров не пустых очередей)
    5. Сделаем из него O(E + Vk1/2) (будем хранить группы по k1/2)
--- Перерыв ---
  1. [25 минут] Radix heap
    1. m = logk, храним очереди q0, q1, ..., qm. В i-й очереди хранятся вершины с расстоянием из диапазона 2i-1, исключения: диапазон qm = ∞, диапазон q0 = 1.
    2. Общая суть: при extractMin или берём q0, или q1, или qi разносим на q0, q1, ..., qi-1
    3. Начало: start в q0, все вершины кроме start в qm; d0 = 0, остальные 1
    4. Как сделать decreaseKey? Пусть вершина v лежит в очереди i[v], пока диапазон очереди i[v] не включает ключ x[v], уменьшаем i[v].
    5. Суммарное время работы m операций decreaseKey равно O(m + Vlogk).
    6. Как сделать extractMin? Ищем первую непустую очередь qi (i = min). Если i ≤ 1, то мы знаем минимум, иначе делим диапазон qi (который не более 2i-1) на 1 + 1 + 2 + ... + 2i-2. Т.е. раскидываем по меньшим очередям.
    7. Суммарное время m раскидываний O(m + Vlogk).
    8. Radix heap − структура, работающая только для растущего минимума (monotone priority queue). Где мы этим пользуемся?
  2. [15 минут] Двух уровневая Radix heap
    1. Делаем O(E + Vlogk/loglogk)
    2. Фибоначчиева куча может работать за O(logk) вместо O(logn) (k − кол-во различных элементов или диапазон элементов)
    3. Делаем O(E + V(logk)1/2)