Конспект: рюкзак, LCS и расстояние редактирования

Понятия

Псевдополиномиальная оценка - линейная по ЗНАЧЕНИЮ числа во входе, а не по длине его записи.

Подпоследовательность - символы в том же порядке, но не обязательно подряд (в отличие от подстроки).

Восстановление ответа - обратный проход по таблице, дающий не число, а сам набор, строку или список правок.

Динамика по отрезкам - состояние [i..j], переход выбирает точку разреза или корень. Цепочка матриц: m[i][j] = min (m[i][k] + m[k+1][j] + p[i−1]·p[k]·p[j]), Θ(n³). Оптимальное дерево поиска: e[i][j] = min (e[i][r−1] + e[r+1][j]) + w(i, j).

Линейное разбиение - k кусков подряд, наименьший наибольший: динамика Θ(k·n²) или поиск по ответу с жадной нарезкой O(n · log S).

Что унести

Одно состояние на все три задачи: «сколько рассмотрено из первого и сколько из второго».

БАЗА - РАЗНАЯ, И ЭТО ВАЖНО
рюкзак:        нулевая строка (из нуля предметов ничего не набрать)
LCS:           нулевая строка и столбец (с пустой строкой общего нет)
Левенштейн:    ЛЕСТНИЦА d[i][0] = i, d[0][j] = j
               нули здесь дают заниженный ответ

ВОССТАНОВЛЕНИЕ - O(n) поверх готовой таблицы
рюкзак:     dp[i][c] == dp[i−1][c] → предмет НЕ брали
LCS:        совпали символы → по диагонали в ответ; иначе туда, где больше
Левенштейн: диагональ без роста - оставили; с ростом - замена;
            сверху - удаление; слева - вставка

Замеры. Рюкзак на предметах (10,60), (20,100), (30,120) при вместимости 50: таблица даёт 220 (набор B + C), жадность по удельной цене - 160. На двенадцати предметах весом 28-35 при C = 60 жадность теряет треть цены: 95 против 147. Шаги на движке: 141 у жадности против 4684 у таблицы - цена правильности.

LCS «АЛГОРИТМ» и «ЛОГАРИФМ» = 5 («ЛГРИМ»), а самая длинная общая ПОДСТРОКА всего 2 («РИ»). Расстояние Левенштейна между ними 4, без замены - 8 + 8 − 2·5 = 6, и оптимальные выравнивания у этих двух задач РАЗНЫЕ. «КОШКА» → «ЛОЖКА» = 2 (К→Л, Ш→Ж). LCS «СТРОКА»/«СТРАНА» = 4 («СТРА»).

ТО ЖЕ, НО В ПРАКТИКЕ
LCS по строкам файла          = diff (git, редакторы)
Θ(n·m) для файлов не годится  настоящие diff считают окрестность диагонали:
                              цена зависит от РАЗМЕРА РАЗЛИЧИЙ
Левенштейн                    опечатки, нечёткий поиск, дедупликация адресов
                              (сначала отбор кандидатов, потом расстояние)
варианты штрафов              Дамерау (транспозиция), Нидлман-Вунш (ДНК)

Огрубление единиц - стандартный приём: веса в сотнях грамм вместо граммов сжимают таблицу рюкзака в сто раз. Вторая форма таблицы (по цене, Θ(n·V)) выгодна, когда цены маленькие, а вместимость огромная.

Тихие ошибки: i вместо i−1 в переходе рюкзака (получается рюкзак с повторениями); нули в базе Левенштейна; max в совпавшей ветке LCS; восстановление «по максимуму в строке» вместо равенства клеток; чтение dp[i−1][c−вес] без проверки, что предмет влезает (отрицательный индекс в Python читает с конца и даёт мусор); Θ(n·m) на файлах и длинных текстах.

Куда это ведёт

Следующая глава - про три вещи, которые в этих таблицах пока оставались за кадром: ПОРЯДОК вычисления (почему цикл по k у Флойда снаружи, а свёрнутый рюкзак требует обхода вместимости НАЗАД), экономия ПАМЯТИ до одной строки и чем за неё платишь, и ДП по МАСКАМ - состояние «подмножество», которое позволяет точно решать задачи вроде коммивояжёра при n до двадцати.