6.3. Динамическое программирование

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

Ключевые вопросы параграфа

• Как работает динамическое программирование и зачем оно нужно?
• Как разбивать задачу на подзадачи и переиспользовать решения?
• Когда стоит выбрать универсальный алгоритм, а когда — частный и быстрый?

Что такое динамическое программирование

Некоторые алгоритмы разбивают задачу на более мелкие подзадачи и используют решения подзадач, чтобы собрать решение для главной. Во время этого процесса количество подзадач может стать очень большим, и некоторые алгоритмы решают одну и ту же подзадачу многократно, что чрезмерно увеличивает время выполнения.

Динамическое программирование упорядочивает вычисления и позволяет не вычислять уже известные значения повторно. Зачастую это экономит массу времени.

Игра в «Камни»

Задача со звонящим телефоном не подразумевает решения с помощью динамического программирования, поэтому мы рассмотрим другую.

Представьте, что вместо ответа на звонок вы решаете поиграть в «Камни»: игру для двух игроков с двумя наборами камней по десять штук.

С каждым ходом один игрок может взять один камень (из любого набора) или два камня (по одному из обоих). Когда камень забрали, он выходит из игры. Побеждает игрок, который заберет последний камень. Первый ход за вами.

Чтобы найти стратегию для выигрыша в игре на , мы можем составить таблицу, которую мы назовем (рис.).

Вместо того, чтобы решать задачу с камнями в каждом из наборов, мы решим более общую задачу с камней в одном наборе и камней в другом (игра на ), где и — это произвольные целые неотрицательные числа.

• Если игрок 1 может гарантированно выигрывать игру на , тогда мы будем говорить, что .
• Если у игрока 1 нет стратегии для выигрыша против игрока, который всегда делает правильные ходы, мы будем писать .

Вычисление для произвольных и может звучать сложно, но мы воспользуемся результатами вычислений для меньших значений.

Некоторые варианты игры, — в особенности , и , — явно приведут к победе игрока 1, так как игрок 1 может выиграть первым ходом. Таким образом, мы заполняем ячейки , и как . рис. (a)

Заполнив ячейки , и , можно попробовать заполнить другие.

Например, в случае с единственный ход, который может сделать игрок 1, приводит к — это выигрышный вариант для оппонента. Аналогичный анализ применим к случаю , что приводит к таблице из рис. рис. (b).

В случае игрок 1 может сделать три разных хода, которые приведут к , и соответственно.

• Один из этих случаев, , приводит к проигрышной позиции оппонента.
• Соответственно, — это выигрышная позиция.
• Случаи и симметричны, поэтому мы получаем таблицу из рис. рис. (c).

Теперь мы можем заполнить .

В случае игрок 1 может сделать три разных хода, которые приведут к ячейкам , и . Эти ячейки — выигрышные позиции для оппонента. Так, : см рис. рис. (d).

Мы можем продолжить заполнять , обращая внимание на то, что ячейка будет , если ячейки сверху, слева и слева по диагонали будут . Эти ячейки (, и ) соответствуют трем ходам, которые может сделать игрок 1. См. рис. рис. (e)

Алгоритм Rocks

Алгоритм Rocks определяет, выиграет игрок 1 или нет. Если игрок 1 выигрывает , то Rocks выдаст . Если игрок 1 проигрывает, то Rocks выдаст . Мы ввели искусственное начальное условие, , чтобы упростить псевдокод.

1Rocks(n, m):
2    R(0,0) = L
3    for i from 1 to n:
4        if R(i-1,0) = W:
5            R(i,0) = L
6        else:
7            R(i,0) = W
8    for j from 1 to m:
9        if R(0,j-1) = W:
10            R(0,j) = L
11        else:
12            R(0,j) = W
13    for i from 1 to n:
14        for j from 1 to m:
15            if R(i-1,j-1)=W and R(i,j-1)=W and R(i-1,j)=W:
16                R(i,j) = L
17            else:
18                R(i,j) = W
19    return R(n,m)

Более быстрый алгоритм для решения этой головоломки опирается на простую закономерность в и проверяет, чётные и или нет. Если оба числа чётные, то игрок проигрывает (см. таблицу выше).

1FastRocks(n, m):
2    if n % 2== 0 and m % 2 == 0: // оба числа чётные
3        return L
4    else:
5        return W

Тем не менее, хотя FastRocks и эффективнее, чем Rocks, изменить его для схожих вариантов игры может быть сложно. Например, вариант, в котором игрок может убирать до трёх камней из наборов. Перед нами пример того, как более медленный алгоритм может быть полезнее, чем быстрый.

Что дальше

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

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

А пока вы не ушли дальше — закрепите материал на практике:

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

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

• Динамическое программирование позволяет решать задачи быстрее за счёт повторного использования подзадач.
• Вместо того чтобы пересчитывать, мы сохраняем уже найденные решения и используем их повторно.
• Метод особенно полезен, когда подзадачи пересекаются и их много.
• Иногда универсальный, но медленный алгоритм оказывается практичнее, чем быстрый, но узкоспециализированный.