Сертифицирующий алгоритм: ответ вместе с доказательством

Если ты знаешь, что такое сертификат ответа и как проверить кратчайшие пути за V + E, листай до «Теперь сам».

Как думаешь, можно ли проверить

Библиотека посчитала кратчайшие расстояния от склада до миллиона адресов. Пересчитать заново, чтобы сравнить, - значит доверять второй программе не больше, чем первой. Перебора на миллионе вершин нет. Можно ли проверить ответ, не решая задачу ещё раз?

Ответь себе до чтения. Можно, если вместе с расстояниями дан родитель каждой вершины - последняя вершина на кратчайшем пути. Тогда проверка - один проход по рёбрам: ни одно ребро не должно давать путь короче обещанного, и у каждой вершины ребро от родителя должно давать ровно обещанное. Это быстрее, чем Дейкстра, и не повторяет её логику.

На что это похоже

Контрольная по математике с ответом в конце учебника - проверяет, совпал ли ответ, но не почему. А решение с подстановкой - «нашёл x = 3, подставил в уравнение, получилось верное равенство» - проверяет само себя: подстановка не зависит от того, как искали корень. Сертификат - это подстановка для алгоритма.

Механизм: постусловие, которое проверяется

В разделе 1 правильность задавалась постусловием. Беда в том, что для многих задач постусловие дорого проверить: «расстояние кратчайшее» означает «не короче ни одного пути», а путей экспоненциально много. Сандерс в книге «Sequential and Parallel Algorithms and Data Structures» (раздел 2.6.4) формулирует выход: вычислить дополнительную информацию, с которой постусловие проверить легко. Эта информация - сертификат (свидетель), а алгоритм, который её выдаёт, - сертифицирующий. Там же замечание: большинство алгоритмов можно сделать сертифицирующими без ухудшения асимптотики.

Последние три строки знакомы: двойственность из раздела 12 - это и есть сертификат оптимальности. Одного потока мало - он доказывает только «столько можно»; разрез той же величины доказывает «больше нельзя». А сертификат из раздела 21, который делает задачу членом NP, - сертификат ответа «да».

Правило

Если ответ дорого перепроверить, требуй от алгоритма сертификат - данные, по которым ответ проверяется быстро и независимо от способа решения. Проверку пиши отдельно и проще самого алгоритма: чем она проще, тем меньше шанс, что в ней та же ошибка.

Разбор: проверка сортировки за линию

Выход сортировки сам себе сертификат, но проверять надо оба свойства: упорядоченность и то, что это перестановка входа. Одна упорядоченность пропускает потерянные и подменённые элементы.

def proverit_sortirovku(vhod, vyhod):
    # два свойства, оба за линейное время:
    # 1) выход упорядочен; 2) выход - перестановка входа (те же числа
    #    столько же раз)
    for i in range(len(vyhod) - 1):
        if vyhod[i] > vyhod[i + 1]:
            return "не упорядочен на месте " + str(i)
    schet = {}
    for x in vhod:
        schet[x] = schet.get(x, 0) + 1
    for x in vyhod:
        if schet.get(x, 0) == 0:
            return "лишний элемент " + str(x)
        schet[x] = schet[x] - 1
    for x in vhod:
        if schet[x] > 0:
            return "потерян элемент " + str(x)
    return "верно"

def puzyrek_odin_prohod(a):
    b = a[:]
    for i in range(len(b) - 1):
        if b[i] > b[i + 1]:
            t = b[i]
            b[i] = b[i + 1]
            b[i + 1] = t
    return b

a = [5, 3, 8, 3, 1, 9, 5]
podmena = [1, 3, 3, 5, 5, 8, 10]
print("sorted:        ", proverit_sortirovku(a, sorted(a)))
print("sorted(set(a)):", proverit_sortirovku(a, sorted(set(a))))
print("один проход:   ", proverit_sortirovku(a, puzyrek_odin_prohod(a)))
print("9 подменили:   ", proverit_sortirovku(a, podmena))

sorted:         верно
sorted(set(a)): потерян элемент 5
один проход:    не упорядочен на месте 1
9 подменили:    лишний элемент 10

sorted(set(a)) выдал упорядоченный список - проверка одной упорядоченности его бы пропустила. Счётчик значений заметил, что пятёрка была дважды, а осталась один раз (тройка тоже, но проверка остановилась на первой потере). Один проход пузырька оставил список неупорядоченным, подмена 9 на 10 - упорядоченным, но чужим. Проверка линейна, а сортировка - n log n: проверять дешевле, чем решать.

Разбор: проверка кратчайших путей по родителям

Сертификат - расстояния dist и родители. Проверка из двух частей:

• никакое ребро не короче: для каждого ребра u → v выполняется dist[v] ≤ dist[u] + w. Отсюда по индукции вдоль любого пути: расстояние до вершины не больше длины любого пути до неё, то есть dist - не завышено;
• обещание достижимо: у каждой достижимой вершины, кроме старта, ребро от родителя тугое - dist[v] = dist[родитель] + w. Идя по родителям, получаем путь длины ровно dist[v], то есть dist - не занижено. При положительных весах расстояние вдоль родителей строго убывает, поэтому цепочка не может зациклиться и кончается в старте - единственной вершине без родителя.

Вместе это и значит «кратчайшее». Граф из урока о признаках, три ответа.

def proverit_puti(n, rebra, s, dist, roditel):
    # сертификат: расстояния dist и родители roditel; проверка за V + E.
    # Предусловие: веса положительны; dist = BESK - «недостижима»
    if dist[s] != 0:
        return "до старта не ноль"
    for r in rebra:
        u = r[0]
        v = r[1]
        if dist[u] < BESK and dist[v] > dist[u] + r[2]:
            luchshe = dist[u] + r[2]
            return ("ребро " + str(u) + "->" + str(v) + " короче: "
                    + str(luchshe) + " < " + str(dist[v]))
    # веса рёбер по паре концов - чтобы ребро от родителя искать сразу
    vesa = {}
    for r in rebra:
        k = str(r[0]) + ">" + str(r[1])
        if k not in vesa:
            vesa[k] = []
        vesa[k].append(r[2])
    for v in range(n):
        if v != s and dist[v] < BESK:
            p = roditel[v]
            k = str(p) + ">" + str(v)
            tugo = False
            if k in vesa and dist[p] < BESK:
                # в списке - веса параллельных рёбер p -> v; каждое ребро
                # смотрим один раз за всю проверку, итого O(V + E)
                tugo = dist[v] - dist[p] in vesa[k]
            if not tugo:
                return "у вершины " + str(v) + " нет пути такой длины"
    return "верно"

rebra = [[0, 4, 50], [0, 1, 10], [1, 2, 10], [2, 3, 10], [3, 4, 10],
         [0, 2, 35]]
# метка «недостижима»: больше суммы всех весов, а длиннее этой суммы
# кратчайший путь не бывает - он не проходит ребро дважды
BESK = 1
for r in rebra:
    BESK = BESK + r[2]
# ответ Дейкстры
print("Дейкстра:      ", proverit_puti(5, rebra, 0,
      [0, 10, 20, 30, 40], [-1, 0, 1, 2, 3]))
# ответ поиска в ширину по числу рёбер (урок о признаках)
print("поиск в ширину:", proverit_puti(5, rebra, 0,
      [0, 10, 35, 45, 50], [-1, 0, 0, 2, 0]))
# «слишком хороший» ответ: до вершины 4 обещано 25
print("занижено:      ", proverit_puti(5, rebra, 0,
      [0, 10, 20, 30, 25], [-1, 0, 1, 2, 3]))

Дейкстра:       верно
поиск в ширину: ребро 1->2 короче: 20 < 35
занижено:       у вершины 4 нет пути такой длины

Ответ поиска в ширину проверка отвергла с указанием: ребро 1 → 2 даёт 20, а обещано 35. Заниженный ответ - «до вершины 4 всего 25» - отвергнут второй частью: ни одно ребро в вершину 4 не даёт 25. Проверка ни разу не искала путей - только прошла по рёбрам и для каждой вершины заглянула в ребро от её родителя: O(V + E). Граница правила - предусловие о положительных весах. При рёбрах веса 0 родители могут ходить по кругу: рёбра 1 → 2 и 2 → 1 веса 0, dist = [0, 0, 0] и родители [-1, 2, 1] пройдут обе части проверки, хотя из старта в вершины 1 и 2 пути нет. Для таких графов проверка должна ещё пройти от каждой вершины по родителям и убедиться, что цепочка приходит в старт. Чтобы не уйти в O(V²), вершины помечают: идут вверх до старта или до уже проверенной вершины, а все пройденные помечают проверенными; вершина, встреченная дважды на одном подъёме, - это цикл. Каждая вершина проходится один раз - O(V).

Что ломается без этого

Проверка тем же способом. Сравнить ответ Дейкстры с ответом второй Дейкстры из той же библиотеки - обе ошибутся одинаково.

Проверка половины постусловия. Только «упорядочен» - и потеря дубликатов проходит незамеченной.

Ответ без сертификата. Функция возвращает «граф не двудольный» - и проверить это нечем, кроме как поверить. С нечётным циклом это проверяется глазами.

Зачем это в работе

Ночной пересчёт маршрутов, расписаний или остатков на складе - большие объёмы, эталона нет, ошибка обнаруживается через неделю жалоб. Проверка сертификата после каждого пересчёта стоит долю его цены и ловит ошибку в ту же ночь. Так проверяют и результаты чужих решателей: оптимизатор ЛП вернул «оптимум» - двойственное решение с тем же значением это подтверждает; не вернул двойственного - повод не верить.

Теперь сам

1. Функция отвечает «граф двудольный». Какой сертификат ты потребуешь и как его проверить?
2. Расстояния [0, 10, 20, 30, 40] и родители [-1, 0, 1, 2, 0] для графа урока. Пройдёт ли проверку?
3. Почему проверка сортировки должна смотреть на мультимножество, а не на множество значений?