Сведение: решить новую задачу вызовом известной

Если ты привык первым делом спрашивать «к какой известной задаче это сводится», листай до «Теперь сам».

Как думаешь, что здесь за алгоритм

На шахматной доске 8 × 8 стоят фигуры-препятствия: на занятую клетку конь не встаёт и никого не берёт. Конь в углу. За какое наименьшее число ходов он доберётся до противоположного угла - и доберётся ли вообще?

Ответь себе до чтения: нужен ли тут специальный «шахматный» алгоритм? Не нужен. «Наименьшее число шагов, каждый шаг одинаковой цены» - это кратчайший путь в графе без весов, а он ищется поиском в ширину из раздела 10. Вся работа - понять, что такое вершины и рёбра: клетки и ходы коня.

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

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

Механизм: перевод туда, вызов, перевод обратно

Сведение из раздела 21 выглядело так же, но служило другому: там доказывали, что задача трудная («если бы эту решили быстро, решили бы и ту, а её быстро не решает никто»). Здесь направление обратное: своя задача сводится к известной лёгкой, и это доказывает, что она решается не дороже.

Три вопроса делают перевод правильным. Каждому ли входу моей задачи соответствует вход известной? Каждый ли ответ известной переводится в ответ моей - в том числе «ответа нет»? Сколько стоят переводы - не съедают ли они выигрыш?

Правило

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

Разбор: конь и поиск в ширину без графа

Вершины - свободные клетки, рёбра - ходы коня. Строить этот граф заранее не нужно: соседей клетки можно вычислять в тот момент, когда до неё дошла очередь. Такой граф называют неявным.

def hody_konya(n, zanyato, start, cel):
    # клетка - [строка, столбец]; вершины и рёбра графа не хранятся:
    # соседи клетки вычисляются, когда до неё дошла очередь.
    # Ключ словаря - str(клетка): в учебном движке нет кортежей-ключей,
    # в обычном Python здесь был бы кортеж (строка, столбец).
    # Предусловие: start и cel - свободные клетки доски
    dist = {}
    dist[str(start)] = 0
    ochered = [start]
    golova = 0
    while golova < len(ochered):
        k = ochered[golova]
        golova = golova + 1
        if k == cel:
            return dist[str(k)]
        for d in [[1, 2], [2, 1], [2, -1], [1, -2],
                  [-1, -2], [-2, -1], [-2, 1], [-1, 2]]:
            s = [k[0] + d[0], k[1] + d[1]]
            if 0 <= s[0] < n and 0 <= s[1] < n:
                if str(s) not in zanyato and str(s) not in dist:
                    dist[str(s)] = dist[str(k)] + 1
                    ochered.append(s)
    return -1

zanyato = set()
print("пустая доска 8×8, из угла в угол:",
      hody_konya(8, zanyato, [0, 0], [7, 7]))
for k in [[1, 2], [2, 1]]:
    zanyato.add(str(k))
print("угол заперт двумя фигурами:     ",
      hody_konya(8, zanyato, [0, 0], [7, 7]))
print("пустая доска, из угла в [1, 1]: ",
      hody_konya(8, set(), [0, 0], [1, 1]))

пустая доска 8×8, из угла в угол: 6
угол заперт двумя фигурами:      -1
пустая доска, из угла в [1, 1]:  4

Все три вопроса о переводе решились сами. Каждой расстановке фигур соответствует граф - если старт и цель свободны: занятая клетка не вершина, и путь из неё не ищут (это предусловие функции, его проверяет вызывающий). Ответ «нет пути» известная задача уже умеет выдавать: очередь кончилась, а цель не достигнута - это -1. Перевод дешёвый: у клетки восемь кандидатов в соседи. Последняя строка показывает, зачем доверять алгоритму, а не интуиции: до соседней по диагонали клетки коню нужно четыре хода, хотя «она же рядом»: например, [0, 0] → [1, 2] → [2, 4] → [3, 2] → [1, 1]. Быстрее нельзя: каждый ход меняет цвет клетки, а [0, 0] и [1, 1] одного цвета, значит, ходов чётное число, а за два хода конь до [1, 1] не достаёт.

Разбор: правильное сведение, которое дороже прямого решения

Наибольшая возрастающая подпоследовательность (НВП) - самая длинная цепочка элементов списка, идущих в нём слева направо и строго возрастающих. Её можно свести к общей подпоследовательности из раздела 15: возрастающая подпоследовательность списка a - это в точности общая подпоследовательность a и отсортированного списка его различных значений. Различных - потому что в строго возрастающей цепочке каждое значение встречается не больше одного раза. Перевод - одна сортировка, известный алгоритм - таблица n × n.

Прямой алгоритм устроен иначе. Он держит список hvosty: hvosty[k] - наименьший последний элемент, каким может кончаться возрастающая цепочка длины k + 1. Этот список сам возрастает, поэтому место для нового элемента ищется двоичным поиском: элемент либо продлевает самую длинную цепочку, либо улучшает хвост какой-то более короткой. Замена хвоста ничего не теряет, потому что в списке хранятся не цепочки, а только их наименьшие хвосты. Если x встаёт на место lo > 0, то hvosty[lo − 1] < x (при lo = 0 сам x - цепочка длины 1): цепочку длины lo с этим хвостом x продлевает, и получается цепочка длины lo + 1 с хвостом x - меньшим прежнего. Всё, что продлевало старую цепочку, продлит и новую, а длина списка не меняется. Поэтому длина списка всегда равна длине лучшей цепочки, хотя сам список цепочкой быть не обязан: для [3, 4, 1] он станет [1, 4], хотя 1 стоит в списке после 4.

import random

shagov = [0]

def lcs(a, b):
    # общая подпоследовательность: таблица (len a + 1) × (len b + 1)
    t = []
    for i in range(len(a) + 1):
        t.append([0] * (len(b) + 1))
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            shagov[0] = shagov[0] + 1
            if a[i - 1] == b[j - 1]:
                t[i][j] = t[i - 1][j - 1] + 1
            else:
                t[i][j] = max(t[i - 1][j], t[i][j - 1])
    return t[len(a)][len(b)]

def nvp_cherez_lcs(a):
    # сведение: возрастающая подпоследовательность a - это общая
    # подпоследовательность a и отсортированных различных значений a
    return lcs(a, sorted(set(a)))

def nvp_hvosty(a):
    # прямой способ: hvosty[k] - наименьший хвост цепочки длины k + 1
    hvosty = []
    for x in a:
        lo = 0
        hi = len(hvosty)
        while lo < hi:
            shagov[0] = shagov[0] + 1
            mid = (lo + hi) // 2
            if hvosty[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        if lo == len(hvosty):
            hvosty.append(x)
        else:
            hvosty[lo] = x
    return len(hvosty)

random.seed(26)
for n in [50, 100, 200]:
    a = []
    for i in range(n):
        a.append(random.randint(1, 1000))
    shagov[0] = 0
    d1 = nvp_cherez_lcs(a)
    s1 = shagov[0]
    shagov[0] = 0
    d2 = nvp_hvosty(a)
    print("n =", n, "| через LCS:", d1, "за", s1,
          "| хвостами:", d2, "за", shagov[0])

n = 50 | через LCS: 11 за 2450 | хвостами: 11 за 140
n = 100 | через LCS: 17 за 9600 | хвостами: 17 за 328
n = 200 | через LCS: 29 за 36400 | хвостами: 29 за 787

Ответы совпадают везде - сведение верное. Обе функции отдают только длину: саму цепочку восстанавливают по таблице или по ссылкам на предыдущий элемент, как в разделе 15, - здесь нам нужна лишь цена. Счётчики считают разное - клетки таблицы у сведения (их n × число различных значений: на 50 числах различных 49, отсюда 2450) и сравнения двоичного поиска у прямого алгоритма, - поэтому смотреть надо на рост. При удвоении n сведение дорожает почти вчетверо (2450 → 9600 → 36 400), а прямой алгоритм - чуть больше чем вдвое. На 200 числах счётчики различаются в 46 раз, на миллионе сведение просто не поместится в память. Это граница правила: сведение доказывает «решается за n²», но не «нельзя быстрее». Зато сведённое решение остаётся полезным - им проверяют прямое.

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

Свой алгоритм с ошибкой на краю. Самописный «поиск пути коня» с ручным перебором ходов забывает про недостижимую клетку и зацикливается. Поиск в ширину обрабатывает её сам.

Перевод теряет ответ «нет». Свели к задаче, которая всегда возвращает число, и не заметили, что в своей задаче ответа может не быть.

Дорогой перевод. Явное построение графа из 10⁸ клеток ради поиска пути длиной 5 - память кончится раньше, чем начнётся поиск. Неявный граф обходится только посещёнными клетками.

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

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

Теперь сам

1. «Можно ли из комнаты A попасть в комнату B, если некоторые двери заперты?» Во что это сводится? Что будет вершинами и рёбрами?
2. Для списка [3, 1, 4, 1, 5, 9, 2, 6] найди длину наибольшей возрастающей подпоследовательности.
3. Сведение работает за O(n) на перевод и O(n log n) на известный алгоритм. Какова цена решения?