Порядок вычисления: почему от перестановки циклов ломается ответ

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

Как думаешь, что решает порядок

Переход и состояние определены, таблица объявлена. Остался технический вопрос: в каком порядке заполнять клетки. Кажется, что это дело вкуса - лишь бы все заполнились.

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

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

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

Механизм: зависимости и правило обхода

ПРАВИЛО
клетка считается ПОСЛЕ всех клеток, на которые ссылается её переход

формально: состояния - вершины графа, зависимости - рёбра,
нужен ТОПОЛОГИЧЕСКИЙ порядок (раздел 10). На практике порядок виден
прямо из индексов в формуле перехода

ЧИТАЕМ ПОРЯДОК ИЗ ПЕРЕХОДА

dp[i] = f(dp[i−1], dp[i−2])          → i по возрастанию
dp[i][j] = f(dp[i−1][j], dp[i][j−1]) → строки сверху вниз, в строке слева направо
dp[i][c] = f(dp[i−1][c], dp[i−1][c−w]) → строка i после строки i−1, внутри любой порядок
dp[m][v] = f(dp[меньшая маска][u])   → маски по возрастанию числа

МЕМОИЗАЦИЯ ПОРЯДКА НЕ ТРЕБУЕТ
рекурсия сама спускается к тому, что нужно. Это её главный плюс:
если порядок сложный или неочевидный, мемоизация просто работает.
Плата - стек и невозможность сэкономить память

Правило

Клетка таблицы считается только после всех клеток, на которые ссылается её переход; формально это топологический порядок на графе зависимостей состояний, а практически порядок читается прямо из индексов в формуле. Если переход ссылается на предыдущую СТРОКУ (dp[i−1][...]), строки идут по порядку, а внутри строки - как угодно. Если переход ссылается на ТУ ЖЕ строку (dp[i][...]), порядок внутри строки становится критичным: он определяет, можно ли использовать уже обновлённое значение того же шага. Мемоизация от этой проблемы избавляет полностью - порядок получается сам, - но платит стеком и памятью. Неверный порядок не вызывает ошибки: таблица заполняется, программа отвечает, и ответ неверен.

Разбор: свёрнутый рюкзак и направление обхода

Таблица рюкзака из прошлой главы ссылается только на предыдущую строку - значит всю таблицу хранить не нужно, достаточно ОДНОЙ строки, которую обновляем на месте:

dp = [0] * (C + 1)
i = 0
while i < len(ves):
    c = C
    while c >= ves[i]:              # НАЗАД, от C к весу предмета
        if dp[c - ves[i]] + cena[i] > dp[c]:
            dp[c] = dp[c - ves[i]] + cena[i]
        c = c - 1
    i = i + 1

Почему назад. При обходе назад клетка dp[c − вес] ещё не тронута на этом шаге - в ней значение из ПРЕДЫДУЩЕЙ строки, то есть ответ без текущего предмета. Именно это и нужно: предмет берётся не больше одного раза. При обходе вперёд в dp[c − вес] уже лежит значение, УЧИТЫВАЮЩЕЕ текущий предмет, и он берётся второй раз, третий, четвёртый.

ЗАМЕР на движке: предметы (10,60), (20,100), (30,120), вместимость 50

двумерная таблица        220    1116 шагов
одна строка, назад       220     522 шага
одна строка, вперёд      300     480 шагов     ← НЕВЕРНО

Откуда 300: предмет весом 10 и ценой 60 взят ПЯТЬ раз - 5 × 60 = 300, вес 5 × 10 = 50. Обход вперёд превратил задачу в рюкзак С ПОВТОРЕНИЯМИ, а это другая задача (и, кстати, её переход отличается от правильного ровно одним индексом - dp[i] вместо dp[i−1]).

Теперь самое неприятное:

тот же замер на двенадцати предметах весом 28-35 при C = 60:

двумерная таблица        147   4639 шагов
одна строка, назад       147   1639 шагов
одна строка, вперёд      147   1634 шага      ← тоже 147!

Неверный код дал верный ответ. И причина тоньше, чем «предметы не влезают дважды»: при C = 60 предметы весом 28, 28, 29 и 30 влезают по два раза. Дело в том, что повтор здесь НЕ ВЫГОДЕН:

лучший вариант «один предмет дважды»:   28 + 28 = 56, цена 65 + 65 = 130
честный оптимум из РАЗНЫХ предметов:    32 + 28 = 60, цена 82 + 65 = 147

неограниченный рюкзак (то, что считает обход вперёд)  = 147
рюкзак 0/1 (то, что нужно)                            = 147

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

Отсюда правило для тестов: свёрнутый рюкзак проверяют на данных, где повтор ВЫГОДЕН - где есть лёгкий предмет с хорошей удельной ценой, которым можно забить рюкзак целиком. В первом наборе урока это (10, 60): пять штук дают 300 против честных 220.

Разбор: почему у Флойда k снаружи

Напомним переход из одиннадцатого раздела: d[i][j] через вершины с номерами до k.

правильно:                          неправильно:
for k: for i: for j:                for i: for j: for k:
    d[i][j] = min(d[i][j],              d[i][j] = min(d[i][j],
                  d[i][k] + d[k][j])                  d[i][k] + d[k][j])

Смысл внешнего k в том, что он нумерует СЛОИ: после k-й итерации в таблице лежат ответы для путей, которым разрешены промежуточные вершины 1...k. Это и есть параметр состояния, просто сэкономленный по памяти - полная таблица была бы трёхмерной d[k][i][j].

Если k оказывается внутри, то для пары (i, j) перебираются все промежуточные вершины сразу - но значения d[i][k] и d[k][j] в этот момент могут быть ещё не досчитаны: до пар, которые дают короткий путь через две пересадки, цикл просто не дошёл. Путь, состоящий из двух улучшений, при таком порядке теряется.

ПРИМЕР, НА КОТОРОМ ЭТО ВИДНО
граф из трёх вершин: 1 → 2 (вес 1), 2 → 3 (вес 1), прямого 1 → 3 нет

при внешнем k: на итерации k = 2 клетка d[1][3] становится 2 - путь найден
при внутреннем k: для пары (1, 3) перебираются все k, но d[1][2] и d[2][3]
    к этому моменту ещё лежат как «нет пути» - потому что цикл по парам
    до них не дошёл. Ответ остаётся «пути нет»

то же проверено фикстурой раздела 11 на большем графе: код с переставленными
циклами теряет путь. Правильность Флойда - это правильность ПОРЯДКА, а не формулы

Третий типовой случай порядка - ДП по маскам (третий урок этой главы): там переход идёт от маски к маске с одним добавленным элементом, то есть к БОЛЬШЕМУ числу, и достаточно обходить маски по возрастанию их числового значения.

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

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

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

Порядок вычисления - то место, где ломаются готовые решения при переносе. Классический сюжет: человек видит в чужом коде свёрнутый в одну строку рюкзак, копирует его в задачу, где предметы можно брать по многу раз (или наоборот), и ответ получается тихо неверным, потому что направление обхода не соответствует задаче. Второй практический слой - отладка. Если динамика отвечает «почти правильно» (на некоторых входах верно, на некоторых нет), первая версия диагноза не «ошибка в формуле», а «ошибка в порядке»: стоит заменить таблицу на мемоизацию и сравнить ответы. Мемоизация порядка не требует, поэтому расхождение сразу показывает, что переход верен, а обход нет. Третье - выбор между подходами в проде: таблица быстрее и экономнее по памяти, мемоизация надёжнее при сложной структуре состояний, и это не вопрос вкуса, а осознанный компромисс.

Теперь сам

Переход задачи: dp[i][j] = dp[i−1][j] + dp[i][j−1] (число путей в таблице). В каком порядке заполнять и что будет при обходе строк снизу вверх?

правильный обход:                   обход снизу вверх:
i = 1..n                            i = n..1
  j = 1..m                            j = 1..m
     dp[i][j] = dp[i−1][j] + dp[i][j−1]

при обходе снизу вверх dp[i−1][j] - это клетка строки ВЫШЕ, которая
при таком порядке ещё не посчитана: в ней ноль. Слагаемое «пришли
сверху» исчезает, и остаются только пути, идущие по строке ВПРАВО

1  1  1
1  1  1
0  0  0      ← последняя строка считалась ПЕРВОЙ, когда строка выше была пуста