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

Если ты умеешь проверить оптимальную подструктуру и объяснить, почему она есть у кратчайшего пути и нет у самого длинного простого, листай до «Теперь сам».

Как думаешь, всегда ли из лучших частей получается лучшее целое

Звучит как самоочевидное: чтобы получить лучший маршрут из A в C через B, возьми лучший маршрут A→B и лучший B→C. Для кратчайших путей так и есть - именно на этом стоит весь раздел про пути.

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

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

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

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

ДВА УСЛОВИЯ ПРИМЕНИМОСТИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

1. ПЕРЕКРЫТИЕ ПОДЗАДАЧ
   одна и та же подзадача нужна многим - иначе запоминать нечего,
   и достаточно обычного деления пополам

2. ОПТИМАЛЬНАЯ ПОДСТРУКТУРА
   оптимальный ответ целого содержит оптимальные ответы подзадач
   ⇒ можно считать подзадачи независимо и склеивать

первое условие про ЦЕНУ, второе про ПРАВИЛЬНОСТЬ.
нет первого - динамика не нужна. нет второго - динамика НЕВЕРНА

КАК ПРОВЕРЯТЬ ВТОРОЕ УСЛОВИЕ

взять оптимальный ответ целого, разрезать его по предполагаемой подзадаче
и спросить: кусок - оптимальный ответ для своей подзадачи?
    да  → подструктура есть, можно писать переход
    нет → найдёшь контрпример из трёх-четырёх элементов

признак беды: подзадачи делят ОБЩИЙ РЕСУРС
    вершины, которые нельзя посещать дважды
    место в рюкзаке, которое одно на всех
    время, которое нельзя занять двумя задачами

ПОЧЕМУ У РЮКЗАКА ПОДСТРУКТУРА ВСЁ-ТАКИ ЕСТЬ
место - общий ресурс, но мы вписали его В СОСТОЯНИЕ: подзадача «первые i
предметов при остатке c». Два разных остатка - два разных состояния,
и они уже независимы. Так лечится большинство случаев: общий ресурс
становится ещё одним параметром состояния

Правило

Динамическое программирование применимо при ДВУХ условиях. Перекрытие подзадач отвечает за цену: без него достаточно обычной рекурсии. Оптимальная подструктура отвечает за правильность: оптимальный ответ целого должен складываться из оптимальных ответов подзадач. Проверяют её так - берут оптимальный ответ, разрезают по подзадаче и смотрят, оптимален ли кусок. Беда приходит, когда подзадачи делят общий ресурс: у кратчайшего пути подструктура есть, у самого длинного ПРОСТОГО пути её нет, потому что вершины нельзя использовать дважды. Типовое лечение - внести общий ресурс в СОСТОЯНИЕ (остаток места, номер шага, маска использованного), и тогда подзадачи становятся независимыми. Если внести не удаётся - задача, скорее всего, NP-трудна.

Разбор: кратчайший путь против самого длинного простого

Кратчайший путь. Пусть лучший путь из q в t проходит через r. Тогда его кусок от q до r - лучший путь из q в r: иначе мы заменили бы кусок на более короткий и получили бы путь из q в t короче лучшего. Противоречие. Отсюда и переход Флойда-Уоршелла из одиннадцатого раздела: «лучший путь через первые k вершин» склеивается из двух таких же.

Теперь самый длинный ПРОСТОЙ путь (простой - значит без повторного посещения вершин). Граф направленный, пять рёбер:

q → r      r → t      q → s      s → t      t → r

Перебором находим самые длинные простые пути:

q → t :  2 ребра, и таких путей ДВА: q → s → t  и  q → r → t
q → r :  3 ребра: q → s → t → r
r → t :  1 ребро: r → t

То, что у q → t оптимальных путей два, здесь важно: рассуждение дальше использует второй из них.

А теперь попробуем собрать ответ «по рецепту»: лучший путь из q в t через r = лучший q→r плюс лучший r→t:

q → s → t → r   +   r → t   =   q → s → t → r → t

вершина t встречается ДВАЖДЫ - это вообще не простой путь.
рецепт дал не «путь длиной 4», а недопустимый ответ

И наоборот: возьмём второй оптимальный путь q → r → t (2 ребра). Его кусок q → r - это ОДНО ребро, а самый длинный путь из q в r содержит три. Оптимум целого содержит неоптимальную часть - значит подструктуры нет.

причина в одной фразе: у этих подзадач ОБЩИЙ РЕСУРС - множество
непосещённых вершин. Выбор в первой половине меняет правила во второй

Самый длинный простой путь - NP-трудная задача, и это не совпадение: внести «множество использованных вершин» в состояние можно (об этом глава про ДП по маскам), но тогда состояний становится 2^n, и дешёвого решения не получается.

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

Вторая история - про жадность и динамику, и она ближе к работе. Задача: выбрать максимальное число непересекающихся занятий. В разделе 14 мы доказали, что тут работает жадность. А теперь то же, но у занятий есть ЦЕННОСТЬ, и максимизировать надо сумму.

занятия (начало, конец, ценность):
  A (0, 2, ценность 1)      B (1, 10, ценность 100)

жадность по раннему концу: берёт A (конец 2), после него B недоступно → 1
оптимум:                   взять только B                            → 100

Отношение ответов здесь 1 к 100, и его можно сделать любым: критерий, оптимальный для ЧИСЛА занятий, про ценность не знает ничего. Это тот же контрпример, что в разделе 14, - и он показывает, что взвешенная задача требует другого алгоритма, а не другого критерия.

Подструктура здесь ЕСТЬ, и это видно из формулировки перехода: отсортируем занятия по концу и для каждого i спросим - берём его или нет.

dp[i] = max( dp[i−1],                        не берём i
             ценность(i) + dp[p(i)] )        берём i, где p(i) - последнее
                                              занятие, закончившееся до начала i

Оптимальный ответ для первых i занятий содержит оптимальный ответ для первых p(i) - потому что занятия с номерами больше p(i) просто недоступны, и подзадачи независимы. Общий ресурс (время) внесён в состояние через сортировку по концу: номер занятия и есть «сколько времени уже занято».

Сравни с предыдущим абзацем: там внести ресурс в состояние дешево было нельзя, здесь - можно, и задача решается за Θ(n·log n) (сортировка по концу плюс двоичный поиск p(i) для каждого занятия). Оговорка, чтобы не осталось ложного впечатления: взвешенный выбор занятий НИКОГДА не был NP-трудным - просто жадность для него неверна. Удачное состояние не «снимает NP-трудность», оно лишь позволяет решить задачу динамикой; целый рюкзак - пример обратного, там состояние нашлось, а задача осталась NP-трудной.

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

Первое: проверить только перекрытие и начать писать таблицу. Таблица заполнится, программа выдаст число, и число будет неверным - без всяких падений. Второе: проверять подструктуру «на примерах»: прогон ничего не доказывает, потому что склейка оптимумов часто СЛУЧАЙНО совпадает с правильным ответом. В графе из разбора выше это видно прямо: для пары q → t рецепт «оптимум плюс оптимум» через s даёт верный ответ 2, и только через r - неверный 4. Один путь проверили - и ошибку не увидели. Третье: не заметить общий ресурс. Признак - в формулировке есть слово «не более одного раза», «не повторяя», «каждый ровно один раз». Четвёртое: внести ресурс в состояние и не заметить, что состояний стало 2^n: формально верно, практически неприменимо при n больше двадцати. Пятое: решить, что NP-трудность - это приговор: у таких задач остаются приближения из раздела 14 и точные методы с отсечениями из раздела 16.

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

Два условия - это чек-лист перед тем как садиться писать. Он занимает минуту и отвечает на вопрос, который иначе выясняется через день отладки: «динамика тут вообще применима?» Самая частая реальная ошибка на этом месте - пропущенная зависимость между подзадачами. Выглядит она так: кто-то написал таблицу «лучший план на день i», а планы на разные дни делят один склад, одного сотрудника или один бюджет, и оптимумы по дням в сумме дают недопустимый план. Пока данные маленькие, никто не замечает; на больших план становится невыполнимым. Второй практический вывод - словарь: если коллега говорит «задача не разбивается на независимые части», он говорит именно про отсутствие оптимальной подструктуры, и это ровно то место, где надо искать общий ресурс и либо вносить его в состояние, либо соглашаться на приближение.

Теперь сам

Задача: дана последовательность чисел, надо выбрать подпоследовательность с максимальной суммой, в которой НЕТ двух соседних элементов. Есть ли у неё оптимальная подструктура? Напиши переход.

dp[i] = max( dp[i−1],              i-й не берём
             a[i] + dp[i−2] )      i-й берём, тогда (i−1)-й запрещён
база: dp[0] = 0, dp[1] = max(0, a[1])

пример: 3, 2, 7, 10
dp[1] = 3
dp[2] = max(3, 2) = 3
dp[3] = max(3, 7 + 3) = 10
dp[4] = max(10, 10 + 3) = 13     ответ 13 - это 3 + 10