mirror of
https://github.com/krahets/hello-algo.git
synced 2026-07-08 12:06:27 +08:00
1416 lines
111 KiB
Markdown
1416 lines
111 KiB
Markdown
# Динамическое программирование
|
||
|
||
{width="3.2760411198600177in" height="4.239583333333333in"}
|
||
|
||
1. **введение в динамичеСкОе прОграммирОвание** *Динамическое программирование* является важной парадигмой в алгоритмах. Ее суть заключается в разбиении задачи на серию более мелких подзадач. Со-
|
||
|
||
> хранение решений подзадач позволяет избежать повторных вычислений, что значительно повышает временную эффективность.
|
||
>
|
||
> В этом разделе мы начнем с классического примера и сначала представим его решение методом перебора. Мы понаблюдаем за наличием перекрыва- ющихся подзадач, а затем постепенно выведем более эффективное решение с использованием динамического программирования.
|
||
>
|
||
> Как показано на рис. 14.1, для лестницы с тремя ступенями существует три способа добраться до вершины.
|
||
>
|
||
> Количество ступеней **n** =
|
||
|
||
Есть 3 способа подняться на **3-ю** ступень:
|
||
|
||
> **Рис. 14.1.** Количество способов добраться до 3-й ступени
|
||
>
|
||
> Цель этой задачи -- найти количество способов, **и можно попробовать использовать для ее решения метод поиска с возвратом**. Более конкрет- но -- можно представить подъем по лестнице как процесс многократного выбора: начать с пола, на каждом этапе выбирать подъем на одну или две ступени, при достижении вершины лестницы количество способов увели- чивается на 1, а при превышении вершины происходит обрезка. Ниже при- веден код реализации.
|
||
>
|
||
> \# === File: climbing_stairs_backtrack.py ===
|
||
>
|
||
> def backtrack(choices: list\[int\], state: int, n: int, res: list\[int\]) -\> int: \"\"\" Поиск с возвратом.\"\"\"
|
||
>
|
||
> \# Когда достигнута n-я ступень, количество способов увеличивается на 1. if state == n:
|
||
>
|
||
> res\[0\] += 1
|
||
>
|
||
> \# Перебор всех вариантов. for choice in choices:
|
||
>
|
||
> \# Обрезка: не допускается превышение n-й ступени. if state + choice \> n:
|
||
>
|
||
> continue
|
||
>
|
||
> \# Попытка: сделать выбор, обновить состояние. backtrack(choices, state + choice, n, res)
|
||
>
|
||
> \# возврат.
|
||
>
|
||
> def climbing_stairs_backtrack(n: int) -\> int:
|
||
>
|
||
> \"\"\" Подъем по лестнице: поиск с возвратом.\"\"\"
|
||
>
|
||
> choices = \[1, 2\] \# Можно выбрать подъем на 1 или 2 ступени. state = 0 \# Начало подъема с 0-й ступени.
|
||
>
|
||
> res = \[0\] \# Используется res\[0\] для записи количества способов. backtrack(choices, state, n, res)
|
||
>
|
||
> return res\[0\]
|
||
|
||
### Первый метод: полный перебор
|
||
|
||
> Алгоритм поиска с возвратом обычно не разбивает задачу явным образом, а рассматривает ее решение как серию шагов принятия решений, исследуя пути обхода и выполняя обрезку.
|
||
>
|
||
> Можно попытаться проанализировать эту задачу с точки зрения разбиения. Пусть для достижения *i*-й ступени существует *dp*\[*i*\] способов, тогда *dp*\[*i*\] являет- ся исходной задачей, а ее подзадачи включают следующие:
|
||
>
|
||
> *dp* ℘Λ*i* −1λϑ , *dp* ℘Λ*i* − 2λϑ , \... *, dp* ℘Λ2λϑ , *dp* ℘Λ1λϑ .
|
||
>
|
||
> На каждом этапе можно подниматься только на одну или две ступени, поэто- му перед на *i*-й ступенью мы находились либо на (*i* -- 1)-й, либо на (*i* -- 2)-й сту- пени. Другими словами, на *i*-ю ступень можно перейти только с (*i* -- 1)-й или (*i* -- 2)-й ступени.
|
||
>
|
||
> Отсюда следует важный вывод: **количество способов добраться до** (*i* -- 1)-**й ступени плюс количество способов добраться до** (*i* -- 2)-**й ступени равно количеству способов добраться до** *i*-**й ступени**. Формула выглядит сле- дующим образом:
|
||
>
|
||
> *dp* ℘Λ*i* λϑ *= dp* ℘Λ*i* −1λϑ + *dp* ℘Λ*i* −1λϑ .
|
||
>
|
||
> Это означает, что в задаче подъема по лестнице между подзадачами суще- ствует рекуррентная зависимость, и **решение исходной задачи можно по- строить из решений подзадач**. На рис. 14.2 демонстрируется эта рекуррент- ная зависимость.
|
||
>
|
||
> 
|
||
>
|
||
> **Рис. 14.2.** Рекуррентная зависимость количества способов подъема по лестнице
|
||
>
|
||
> Можно получить решение методом полного перебора на основе рекуррент- ной формулы. Начиная с *dp*\[*n*\], **большая задача рекурсивно разбивается на сумму двух меньших задач**, пока не будут достигнуты минимальные под- задачи *dp*\[1\] и *dp*\[2\], для которых возвращаются известные решения: *dp*\[1\] = 1, *dp*\[2\] = 2. То есть для достижения 1-й и 2-й ступеней существует 1 и 2 способа соответственно.
|
||
>
|
||
> Рассмотрим следующий код, который, как и стандартный код поиска с воз- вратом, относится к поиску в глубину, но является более лаконичным.
|
||
>
|
||
> \# === File: climbing_stairs_dfs.py === def dfs(i: int) -\> int:
|
||
>
|
||
> \"\"\" Поиск.\"\"\"
|
||
>
|
||
> \# dp\[1\] и dp\[2\] известны, возврат. if i == 1 or i == 2:
|
||
>
|
||
> return i
|
||
>
|
||
> \# dp\[i\] = dp\[i-1\] + dp\[i-2\] count = dfs(i - 1) + dfs(i - 2) return count
|
||
>
|
||
> def climbing_stairs_dfs(n: int) -\> int: \"\"\" Подъем по лестнице: поиск.\"\"\" return dfs(n)
|
||
>
|
||
> На рис. 14.3 изображено рекурсивное дерево, образованное полным перебо- ром. Для задачи *dp*\[*n*\] глубина рекурсивного дерева равна *n*, а временная слож- ность составляет *O*(2*n*). Экспоненциальный рост приводит к взрывному увели- чению, и при вводе достаточно большого *n* можно столкнуться с длительной работой алгоритма.
|
||
>
|
||
> 
|
||
>
|
||
> **Рис. 14.3.** Рекурсивное дерево для подъема по лестнице
|
||
>
|
||
> Как видно из рис. 14.3, **экспоненциальная временная сложность вызва- на перекрывающимися подзадачами**. Например, *dp*\[9\] разбивается на *dp*\[8\] и *dp*\[7\], *dp*\[8\] разбивается на *dp*\[7\] и *dp*\[6\] -- обе задачи содержат подзадачу *dp*\[7\]. Таким образом, в подзадачах содержатся более мелкие перекрывающиеся подзадачи, и большая часть вычислительных ресурсов тратится на их обработку.
|
||
|
||
### Второй метод: мемоизация поиска
|
||
|
||
> Для повышения эффективности алгоритма **необходимо**, **чтобы все пере- крывающиеся подзадачи вычислялись только один раз**. Для этого мы объ- явим массив mem для записи решений каждой подзадачи и в процессе поиска устраним необходимость их повторной обработки.
|
||
|
||
1. При первом вычислении *dp*\[*i*\] мы записываем результат в mem\[i\] для дальнейшего использования.
|
||
|
||
2. Когда требуется повторно вычислить *dp*\[*i*\], мы можем напрямую полу- чить результат из mem\[i\], избегая повторной обработки.
|
||
|
||
> Код реализации представлен ниже.
|
||
>
|
||
> \# === File: climbing_stairs_dfs_mem.py === def dfs(i: int, mem: list\[int\]) -\> int:
|
||
>
|
||
> \"\"\" мемоизация поиска.\"\"\"
|
||
>
|
||
> \# dp\[1\] и dp\[2\] известны, возврат. if i == 1 or i == 2:
|
||
>
|
||
> return i
|
||
>
|
||
> \# Если существует запись dp\[i\], возвращаем ее значение. if mem\[i\] != -1:
|
||
>
|
||
> return mem\[i\]
|
||
>
|
||
> \# dp\[i\] = dp\[i-1\] + dp\[i-2\]
|
||
>
|
||
> count = dfs(i - 1, mem) + dfs(i - 2, mem) \# Запись dp\[i\].
|
||
>
|
||
> mem\[i\] = count return count
|
||
>
|
||
> def climbing_stairs_dfs_mem(n: int) -\> int:
|
||
>
|
||
> \"\"\" Подъем по лестнице: мемоизация поиска.\"\"\"
|
||
>
|
||
> \# В mem\[i\] хранится количество способов подняться на i-ю ступень, \# -1 означает отсутствие записи.
|
||
>
|
||
> mem = \[-1\] \* (n + 1) return dfs(n, mem)
|
||
>
|
||
> После внедрения запоминания все пересекающиеся подзадачи нужно вы- числить только один раз, что оптимизирует временную сложность до *O*(*n*), это является значительным скачком, см рис. 14.4.
|
||
|
||
|
||
|
||
> **Рис. 14.4.** Мемоизация поиска и соответствующее дерево рекурсии
|
||
|
||
### Третий метод: динамическое программирование
|
||
|
||
> **Мемоизация поиска -- это метод «сверху вниз»**: мы начинаем с исходной задачи (корневой узел) и рекурсивно разбиваем более крупные подзадачи на более мелкие, пока не достигнем минимальных подзадач с известным реше- нием (листовые узлы). Затем через возврат поэтапно собираем решения под- задач, чтобы построить решение исходной задачи.
|
||
>
|
||
> В отличие от этого подхода **динамическое программирование представ- ляет собой метод «снизу вверх»**: начиная с решения минимальных подза- дач, итеративно строится решение более крупных подзадач, пока не будет по- лучено решение исходной задачи.
|
||
>
|
||
> Поскольку динамическое программирование не включает этап возврата, оно реализуется с использованием циклов и итераций, без необходимости
|
||
>
|
||
> в рекурсии. В следующем коде мы инициализируем массив dp для хранения ре- шений подзадач, который выполняет ту же функцию запоминания, что и мас- сив mem в мемоизации поиска.
|
||
>
|
||
> \# === File: climbing_stairs_dp.py === def climbing_stairs_dp(n: int) -\> int:
|
||
>
|
||
> \"\"\" Подъем по лестнице: динамическое программирование.\"\"\"
|
||
>
|
||
> if n == 1 or n == 2: return n
|
||
>
|
||
> \# Инициализация таблицы dp для хранения решений подзадач. dp = \[0\] \* (n + 1)
|
||
>
|
||
> \# Начальное состояние: предустановка решения минимальных подзадач. dp\[1\], dp\[2\] = 1, 2
|
||
>
|
||
> \# Переход состояния: постепенное решение более крупных подзадач. for i in range(3, n + 1):
|
||
>
|
||
> dp\[i\] = dp\[i - 1\] + dp\[i - 2\] return dp\[n\]
|
||
>
|
||
> На рис. 14.5 иллюстрируется процесс выполнения приведенного выше кода.
|
||
|
||
|
||
|
||
> **Рис. 14.5.** Применение динамического программирования для подъема по лестнице
|
||
>
|
||
> Как и в алгоритмах поиска с возвратом, в динамическом программировании используется концепция состояния для обозначения определенной стадии ре- шения задачи. Каждое состояние соответствует подзадаче и соответствующе- му локальному оптимальному решению. Например, состояние задачи подъема по лестнице определяется текущей ступенью *i*.
|
||
>
|
||
> На основе этого можно обобщить часто используемые термины динамиче- ского программирования.
|
||
|
||
- Массив dp называется таблицей dp, *dp*\[*i*\] обозначает решение подзадачи, соответствующей состоянию *i*.
|
||
|
||
<!-- -->
|
||
|
||
- Состояния, соответствующие минимальным подзадачам (1-я и 2-я сту- пени лестницы), называются начальными состояниями.
|
||
|
||
- Рекуррентное соотношение *dp*\[*i*\] = *dp*\[*i* − 1\] + *dp*\[*i* − 2\] называется уравне- нием перехода состояния.
|
||
|
||
### Оптимизация пространства
|
||
|
||
> Внимательный читатель может заметить, что, **поскольку** *dp*\[*i*\] **зависит только от** *dp*\[*i* − 1\] **и** *dp*\[*i* − 2\], **нам не нужно использовать целый мас- сив** *dp* **для хранения всех решений подзадач**, а достаточно использовать только две переменные для последовательного продвижения. Ниже приве- ден пример кода.
|
||
>
|
||
> \# === File: climbing_stairs_dp.py ===
|
||
>
|
||
> def climbing_stairs_dp_comp(n: int) -\> int:
|
||
>
|
||
> \"\"\" Подъем по лестнице: динамическое программирование с оптимизацией про- странства.\"\"\"
|
||
>
|
||
> if n == 1 or n == 2: return n
|
||
>
|
||
> a, b = 1, 2
|
||
>
|
||
> for \_ in range(3, n + 1): a, b = b, a + b
|
||
>
|
||
> return b
|
||
>
|
||
> Как видно из кода, за счет исключения использования массива dp простран- ственная сложность снижается с *O*(*n*) до *O*(*1*).
|
||
>
|
||
> В задачах динамического программирования текущее состояние часто за- висит только от ограниченного числа предыдущих состояний. В этом случае можно сохранить только необходимые состояния, чтобы сэкономить память. **Эта техника оптимизации пространства называется скользящие пере- менные или скользящий массив**.
|
||
|
||
1. **Особенности задач динамического программирования**
|
||
|
||
В предыдущем разделе мы изучили, как динамическое программирование ре- шает исходную задачу путем разложения на подзадачи. На самом деле раз-
|
||
|
||
> ложение на подзадачи -- это универсальный алгоритмический подход, кото- рый по-разному применяется в методах «разделяй и властвуй», динамическом программировании и поиске с возвратом.
|
||
|
||
- Алгоритм «разделяй и властвуй» рекурсивно делит исходную задачу на несколько независимых подзадач до самых минимальных и в процессе обратного хода объединяет решения всех подзадач.
|
||
|
||
- Динамическое программирование также осуществляет рекурсивное раз- биение задачи. Основное отличие от алгоритмов «разделяй и властвуй» заключается в том, что подзадачи в динамическом программировании взаимозависимы, и в процессе разбиения возникает множество пере- крывающихся подзадач.
|
||
|
||
- Алгоритмы поиска с возвратом исчерпывают все возможные решения методом проб и возвратов, осекая ненужные ветви поиска с помощью обрезки. Решение исходной задачи состоит из серии шагов принятия ре- шений, каждый шаг можно рассматривать как подзадачу.
|
||
|
||
> На практике динамическое программирование часто используется для ре- шения задач оптимизации, которые не только содержат перекрывающиеся подзадачи, но и обладают двумя другими важными свойствами: оптимальной подструктурой и отсутствием последствий.
|
||
|
||
### Оптимальная подструктура
|
||
|
||
> Чтобы лучше продемонстрировать концепцию оптимальной подструктуры, рассмотрим задачу о подъеме по лестнице с небольшими изменениями.
|
||
>
|
||
> Если стоимость на 1-й, 2-й и 3-й ступенях составляет 1, 10 и 1 соответствен- но, то минимальная стоимость подъема с пола на 3-ю ступень равна 2, как по- казано на рис. 14.6.
|
||
|
||
|
||
|
||
> **Рис. 14.6.** Минимальная стоимость подъема на 3-ю ступень
|
||
>
|
||
> Пусть *dp*\[*i*\] обозначает накопленную стоимость для подъема на *i*-ю ступень. Поскольку на *i*-ю ступень можно попасть только с (*i* -- 1)-й или (*i* -- 2)-й ступени, *dp*\[*i*\] может быть равен либо *dp*\[*i* − 1\] + *cost*\[*i*\], либо *dp*\[*i* − 2\] + *cost*\[*i*\]. Чтобы мини- мизировать расход, следует выбрать меньшее из двух значений:
|
||
>
|
||
> *dp* ℘Λ*i* λϑ *=* min(*dp* ℘Λ*i* −1λϑ , *dp* ℘Λ*i* − 2λϑ + *cost* Λ℘*i*λϑ .
|
||
>
|
||
> Этот пример иллюстрирует смысл *оптимальной подструктуры*: **оптималь- ное решение исходной задачи строится на основе оптимальных реше- ний подзадач**.
|
||
>
|
||
> Очевидно, что данная задача обладает оптимальной подструктурой: из двух оптимальных решений подзадач *dp*\[*i* − 1\] и *dp*\[*i* − 2\] выбирается лучшее, и на его основе строится оптимальное решение исходной задачи *dp*\[*i*\].
|
||
>
|
||
> Итак, имеет ли задача о подъеме по лестнице из предыдущего разде- ла оптимальную подструктуру? Цель этой задачи -- вычислить количество решений, что на первый взгляд является задачей подсчета. Но если пере- фразировать вопрос как вычисление максимального количества решений, то неожиданно обнаруживается, что, **хотя модифицированная задача эк- вивалентна**, **возникает оптимальная подструктура**: максимальное ко- личество решений для *n*-й ступени равно сумме максимального количества решений для (*n* -- 1)-й и (*n* -- 2)-й ступеней. Таким образом, интерпретация оптимальной подструктуры может быть гибкой и иметь различное значение в зависимости от задачи.
|
||
>
|
||
> Согласно уравнению перехода состояния и начальному состоянию *dp*\[1\] = *cost*\[1\] и *dp*\[2\] = *cost*\[2\], можно получить код реализации динамического про- граммирования.
|
||
>
|
||
> \# === File: min_cost_climbing_stairs_dp.py ===
|
||
>
|
||
> def min_cost_climbing_stairs_dp(cost: list\[int\]) -\> int:
|
||
>
|
||
> \"\"\" Минимальная стоимость подъема по лестнице: динамическое программирова- ние.\"\"\"
|
||
>
|
||
> n = len(cost) - 1
|
||
>
|
||
> if n == 1 or n == 2: return cost\[n\]
|
||
>
|
||
> \# Инициализация таблицы dp для хранения решений подзадач. dp = \[0\] \* (n + 1)
|
||
>
|
||
> \# Начальное состояние: предусмотреть решение минимальной подзадачи. dp\[1\], dp\[2\] = cost\[1\], cost\[2\]
|
||
>
|
||
> \# Переход состояния: постепенное решение более крупных подзадач. for i in range(3, n + 1):
|
||
>
|
||
> dp\[i\] = min(dp\[i - 1\], dp\[i - 2\]) + cost\[i\] return dp\[n\]
|
||
>
|
||
> На рис. 14.7 демонстрируется процесс динамического программирования в данном коде.
|
||
>
|
||
> 
|
||
>
|
||
> **Рис. 14.7.** Процесс динамического программирования для задачи минимальной стоимости подъема по лестнице
|
||
>
|
||
> Эту задачу также можно оптимизировать по пространству, сжав одномерное представление до нулевого, что снижает сложность по пространству с *O*(*n*) до *O*(1).
|
||
>
|
||
> \# === File: min_cost_climbing_stairs_dp.py ===
|
||
>
|
||
> def min_cost_climbing_stairs_dp_comp(cost: list\[int\]) -\> int:
|
||
>
|
||
> \"\"\" Минимальная стоимость подъема по лестнице: динамическое программирова- ние с оптимизацией по пространству.\"\"\"
|
||
>
|
||
> n = len(cost) - 1
|
||
>
|
||
> if n == 1 or n == 2: return cost\[n\]
|
||
>
|
||
> a, b = cost\[1\], cost\[2\] for i in range(3, n + 1):
|
||
>
|
||
> a, b = b, min(a, b) + cost\[i\] return b
|
||
|
||
### Отсутствие последствий
|
||
|
||
> *Отсутствие последствий* -- одно из важных свойств, позволяющих динамиче- скому программированию эффективно решать задачи. Оно определяется сле- дующим образом: **при заданном определенном состоянии его дальней- шее развитие зависит только от текущего состояния и не зависит от всех предыдущих состояний**.
|
||
>
|
||
> Возьмем, к примеру, задачу о подъеме по лестнице. При заданном состоя- нии *i* оно может развиться в состояния *i* + 1 или *i* + 2, что соответствует подъ- ему на одну или две ступени. При выборе одного из этих вариантов нет не- обходимости учитывать состояния, предшествующие *i*, так как они не влияют на будущее состояние.
|
||
>
|
||
> Однако, если добавить к задаче о подъеме по лестнице ограничения, ситуа- ция изменится.
|
||
>
|
||
> Как показано на рис. 14.8, для достижения 3-й ступени остается только два возможных варианта. Вариант с тремя последовательными подъемами по од- ной ступени не удовлетворяет условиям и поэтому отбрасывается.
|
||
|
||
|
||
|
||
> **Рис. 14.8.** Количество вариантов достижения 3-й ступени с учетом ограничений
|
||
>
|
||
> В этой задаче если на предыдущем шаге был совершен подъем на одну ступень, то на следующем шаге необходимо обязательно подняться на две ступени. Это означает, что **выбор следующего шага нельзя определить независимо от текущего состояния (текущей ступени)**. **Но следующий шаг также зависит и от предыдущего состояния (ступени на предыду- щем шаге)**.
|
||
>
|
||
> Нетрудно заметить, что данная задача не удовлетворяет условию отсутствия последствий. Уравнение перехода состояния *dp*\[*i*\] = *dp*\[*i* -- 1\] + *dp*\[*i* -- 2\] также не работает, так как *dp*\[*i* -- 1\] представляет собой подъем на одну ступень, вклю- чая варианты, в которых на предыдущем шаге был подъем на одну ступень. Чтобы выполнить условия, нельзя напрямую включать *dp*\[*i* -- 1\] в *dp*\[*i*\].
|
||
>
|
||
> Для этого необходимо расширить определение состояния: **состояние** \[*i*, *j*\] **обозначает нахождение на** *i*-й **ступени**, **при этом на предыдущем шаге был подъем на** *j* **ступеней**, где *j* ∈ {1, 2}. Это определение состояния уже раз- личает, был ли на предыдущем шаге подъем на одну или две ступени.
|
||
|
||
- Если на предыдущем шаге был подъем на одну ступень, то на шаг до это- го можно было подняться только на две ступени, т. е. *dp*\[*i*, 1\] можно полу- чить только из *dp*\[*i* -- 1, 2\].
|
||
|
||
- Если на предыдущем шаге был подъем на две ступени, то на шаг до этого можно было выбрать подъем на одну или две ступени, т. е. *dp*\[*i*, 2\] можно получить из *dp*\[*i* -- 2, 1\] или *dp*\[*i* -- 2, 2\].
|
||
|
||
> При таком определении *dp*\[*i*, *j*\] обозначает количество вариантов для состо- яния \[*i*, *j*\], как показано на рис. 14.9. В этом случае уравнение перехода состоя- ния будет следующим:
|
||
>
|
||
> ρ *dp* ℘Λ*i*, 1λϑ *= dp* ℘Λ*i* −1, 2λϑ
|
||
>
|
||
>
|
||
>
|
||
> λ*dp* ℘Λ*i*, 2λϑ *= dp* ℘Λ*i* − 2, 1λϑ + *dp* ℘Λ*i* − 2, 2λϑ.
|
||
|
||
|
||
|
||
> **Рис. 14.9.** Рекуррентное соотношение с учетом ограничений
|
||
>
|
||
> В результате возвращается сумма *dp*\[*n*, 1\] + *dp*\[*n*, 2\], которая представляет общее количество вариантов достижения *n*-й ступени.
|
||
>
|
||
> \# === File: climbing_stairs_constraint_dp.py === def climbing_stairs_constraint_dp(n: int) -\> int:
|
||
>
|
||
> \"\"\" Динамическое программирование для подъема по лестнице
|
||
>
|
||
> с ограничениями.\"\"\"
|
||
>
|
||
> if n == 1 or n == 2: return 1
|
||
>
|
||
> \# Инициализация таблицы dp для хранения решений подзадач.
|
||
>
|
||
> dp = \[\[0\] \* 3 for \_ in range(n + 1)\]
|
||
>
|
||
> \# Начальное состояние: предустановка решения минимальной подзадачи. dp\[1\]\[1\], dp\[1\]\[2\] = 1, 0
|
||
>
|
||
> dp\[2\]\[1\], dp\[2\]\[2\] = 0, 1
|
||
>
|
||
> \# Переход состояния: постепенное решение более крупных подзадач. for i in range(3, n + 1):
|
||
>
|
||
> dp\[i\]\[1\] = dp\[i - 1\]\[2\]
|
||
>
|
||
> dp\[i\]\[2\] = dp\[i - 2\]\[1\] + dp\[i - 2\]\[2\] return dp\[n\]\[1\] + dp\[n\]\[2\]
|
||
>
|
||
> В приведенном выше примере необходимо учитывать только одно преды- дущее состояние, поэтому можно расширить определение состояния, и задача все равно будет удовлетворять условию отсутствия последствий. Однако неко- торые задачи обладают серьезными условиями последствий.
|
||
>
|
||
> В этой задаче следующий шаг зависит от всех предыдущих состояний, так как каждый предыдущий шаг устанавливает препятствие на более высокой ступени. Для таких задач динамическое программирование часто оказывается неэффективным.
|
||
>
|
||
> На самом деле многие сложные задачи комбинаторной оптимизации (на- пример, задача коммивояжера) не удовлетворяют условию отсутствия по- следствий. Для решения таких задач обычно выбираются другие методы, та- кие как эвристический поиск, генетические алгоритмы, обучение с подкре- плением и т. д., чтобы получить приемлемое локальное оптимальное решение за ограниченное время.
|
||
|
||
#### подход к решению задач динамического программирования
|
||
|
||
> В предыдущих разделах были рассмотрены основные характеристики задач динамического программирования, теперь исследуем два более практичных вопроса.
|
||
|
||
1. Как определить, является ли задача задачей динамического программи- рования?
|
||
|
||
2. С чего начать решение задачи динамического программирования, како- ва полная схема решения?
|
||
|
||
### Определение задачи
|
||
|
||
> В общем случае, если задача содержит перекрывающиеся подзадачи, опти- мальную подструктуру и удовлетворяет условию отсутствия последствий, она обычно подходит для решения методом динамического программи- рования. Однако трудно извлечь эти характеристики непосредственно из описания задачи. Поэтому обычно условия смягчаются, и **сначала прове- ряется, подходит ли задача для решения методом поиска с возвратом (перебора)**.
|
||
>
|
||
> **Задачи, подходящие для решения методом поиска с возвратом, обыч- но соответствуют модели дерева решений**. Такие задачи можно описать с помощью древовидной структуры, в которой каждый узел представляет со- бой решение, а каждый путь -- последовательность решений.
|
||
>
|
||
> Иными словами, если задача включает в себя явную концепцию принятия решений и решение получается в результате серии решений, то она соответ- ствует модели дерева решений. Обычно такую задачу можно решить с помо- щью метода обратного поиска.
|
||
>
|
||
> Задачи динамического программирования, помимо вышеуказанных, долж- ны иметь некоторые дополнительные характеристики.
|
||
|
||
- Задача содержит описание оптимизации, например максимизацию или минимизацию.
|
||
|
||
- Состояние задачи можно представить с помощью списка, многомерной матрицы или дерева, и существует рекурсивная связь между состоянием и его окружением.
|
||
|
||
> Соответственно, существуют маркеры, которые говорят о неприменимости стратегии динамического программирования.
|
||
|
||
- Цель задачи -- найти все возможные решения, а не оптимальное решение.
|
||
|
||
- Описание задачи имеет явные признаки комбинаторики, и требуется вернуть несколько конкретных решений.
|
||
|
||
> Если задача соответствует модели дерева решений и обладает достаточно явными дополнительным характеристиками, можно предположить, что это задача динамического программирования, и подтвердить это в процессе решения.
|
||
|
||
### Этапы решения задачи
|
||
|
||
> Процесс решения задач динамического программирования может разли- чаться в зависимости от природы и сложности задачи, но обычно следует следующей схеме: описание решений, определение состояния, построение таблицы *dp*, вывод уравнения перехода состояния, определение граничных условий и т. д.
|
||
>
|
||
> Для более наглядного представления этапов решения рассмотрим в каче- стве примера классическую задачу «минимальная стоимость пути».
|
||
>
|
||
> На рис. 14.10 показан пример, в котором минимальная сумма пути для дан- ного массива равна 13.
|
||
>
|
||
> 
|
||
>
|
||
> **Рис. 14.10.** Пример данных для задачи минимальной стоимости пути
|
||
|
||
##### Шаг 1: обдумывание каждого решения, определение состояния, получение таблицы *dp*
|
||
|
||
> В этой задаче решение заключается в выборе следующего шага из текущей ячейки: вниз или вправо. Обозначим текущий индекс строки и столбца как \[*i*, *j*\], тогда после шага вниз или вправо индекс изменится на \[*i* + 1, *j*\] или \[*i*, *j* + 1\]. Таким образом, состояние должно включать два переменных индекса: строки и столбца, обозначаемых как \[*i*, *j*\].
|
||
>
|
||
> Подзадача, соответствующая состоянию \[*i*, *j*\], заключается в нахождении ми- нимальной стоимости пути от начальной точки \[0, 0\] до точки \[*i*, *j*\], решение обозначается как *dp*\[*i*, *j*\].
|
||
>
|
||
> Таким образом, мы получаем двумерную матрицу *dp*, размер которой со- впадает с размером входного массива *grid*, как показано на рис. 14.11.
|
||
>
|
||
> **Решение:** пройти на одну клетку вправо или вниз
|
||
>
|
||
> **Определение состояния:** индексы строки и столбца **\[i, j\]**
|
||
>
|
||
> **Таблица dp**
|
||
>
|
||
> **Подзадача:** минимальная сумма пути из левого верхнего угла до **\[i, j\]**
|
||
>
|
||
> **Таблица dp:** матрица того же размера, что и grid
|
||
>
|
||
> **Рис. 14.11.** Определение состояния и таблица dp
|
||
|
||
##### Шаг 2: нахождение оптимальной подструктуры и вывод уравнения перехода состояния
|
||
|
||
> Переход в состояние \[*i*, *j*\] возможен только из верхней ячейки \[*i* − 1, *j*\] или левой ячейки \[*i*, *j* − 1\]. Таким образом, оптимальная подструктура определяется тем, что минимальная сумма пути до \[*i*, *j*\] определяется минимальной суммой пути из \[*i*, *j* − 1\] и \[*i* − 1, *j*\].
|
||
>
|
||
> На основе вышеизложенного можно вывести уравнение перехода состоя- ния, показанное на рис. 14.12:
|
||
>
|
||
> *dp* Λ℘*i*, *j* λϑ *=* min(*dp* ℘Λ*i* −1λϑ , *dp* ℘Λ*i, j* −1λϑ + *grid* ℘Λ*i, j*λϑ .
|
||
|
||
|
||
|
||
> **Рис. 14.12.** Оптимальная подструктура и уравнение перехода состояния
|
||
|
||
##### Шаг 3: определение граничных условий и порядка перехода состояния
|
||
|
||
> В этой задаче состояния в первой строке можно получить только из левых со- стояний, а состояния в первом столбце -- только из верхних состояний, поэто- му первая строка *i* = 0 и первый столбец *j* = 0 являются граничными условиями. Поскольку каждую ячейку можно получить только из ячейки слева или сверху, мы используем цикл для обхода матрицы: внешний цикл проходит по
|
||
>
|
||
> строкам, а внутренний -- по столбцам, как показано на рис. 14.13.
|
||
>
|
||
> **Граничные условия:** инициализировать первые строку и столбец
|
||
>
|
||
> **Порядок перехода состояний:**
|
||
>
|
||
> прямой обход матрицы
|
||
>
|
||
> **Рис. 14.13.** Граничные условия и порядок перехода состояний
|
||
>
|
||
> На основе вышеизложенного анализа можно сразу написать код динами- ческого программирования. Однако разбиение подзадач -- это подход сверху вниз, поэтому реализация в порядке полный перебор → мемоизация → дина- мическое программирование более соответствует привычному мышлению.
|
||
|
||
##### Первый метод: полный перебор
|
||
|
||
> Поиск начинается с состояния \[*i*, *j*\] и постоянно разбивается на более мелкие со- стояния \[*i* -- 1, *j*\] и \[*i*, *j* -- 1\]. Рекурсивная функция включает следующие элементы.
|
||
|
||
- **Рекурсивные параметры**: состояние \[*i*, *j*\].
|
||
|
||
- **Возвращаемое значение**: минимальная стоимость пути от \[0, 0\] до \[*i*, *j*\], *dp*\[*i*, *j*\].
|
||
|
||
- **Условие завершения**: когда *i* = 0 и *j* = 0, возвращается стоимость *grid*\[0, 0\].
|
||
|
||
- **Обрезка**: при *i* \< 0 или *j* \< 0 индекс выходит за допустимые пределы, в этом случае возвращается стоимость +∞, что означает недопустимость.
|
||
|
||
> Ниже приведен код реализации.
|
||
>
|
||
> \# === File: min_path_sum.py ===
|
||
>
|
||
> def min_path_sum_dfs(grid: list\[list\[int\]\], i: int, j: int) -\> int: \"\"\" Минимальная стоимость пути: полный перебор.\"\"\"
|
||
>
|
||
> \# Если это верхний левый элемент, то поиск завершается. if i == 0 and j == 0:
|
||
>
|
||
> return grid\[0\]\[0\]
|
||
>
|
||
> \# Если индексы строки и столбца выходят за пределы, возвращается стоимость +∞. if i \< 0 or j \< 0:
|
||
>
|
||
> return inf
|
||
>
|
||
> \# Вычисление минимальной стоимости пути от верхнего левого угла до (i-1, j) и (i, j-1).
|
||
>
|
||
> up = min_path_sum_dfs(grid, i - 1, j) left = min_path_sum_dfs(grid, i, j - 1)
|
||
>
|
||
> \# Возвращение минимальной стоимости пути от верхнего левого угла до (i, j). return min(left, up) + grid\[i\]\[j\]
|
||
>
|
||
> На рис. 14.14 изображено дерево рекурсии с корневым узлом *dp*\[2, 1\], содер- жащее несколько перекрывающихся подзадач, количество которых резко уве- личивается с увеличением размера сетки grid.
|
||
>
|
||
> По сути, причиной перекрывающихся подзадач является **наличие несколь- ких путей**, **ведущих из верхнего левого угла к одной ячейке**.
|
||
|
||
|
||
|
||
> **Рис. 14.14.** Дерево рекурсии полного перебора
|
||
>
|
||
> Каждое состояние имеет два варианта выбора: вниз и вправо. Чтобы пройти из верхнего левого угла в нижний правый, требуется *m* + *n* -- 2 шагов, поэтому в худшем случае временная сложность составляет *O*(2*m*+*n*). Обратите внимание, что этот расчет не учитывает случаи, когда путь достигает границы сетки, где остается только один вариант выбора, поэтому фактическое количество путей будет меньше.
|
||
|
||
##### Второй метод: мемоизация
|
||
|
||
> Вводится список mem, имеющий те же размеры, что и сетка grid, для записи ре- шений подзадач и отсечения перекрывающихся подзадач.
|
||
>
|
||
> \# === File: min_path_sum.py === def min_path_sum_dfs_mem(
|
||
>
|
||
> grid: list\[list\[int\]\], mem: list\[list\[int\]\], i: int, j: int
|
||
>
|
||
> ) -\> int:
|
||
>
|
||
> \"\"\" Минимальная стоимость пути: мемоизация.\"\"\"
|
||
>
|
||
> \# Если это верхний левый элемент, то поиск завершается. if i == 0 and j == 0:
|
||
>
|
||
> return grid\[0\]\[0\]
|
||
>
|
||
> \# Если индексы строки и столбца выходят за пределы, возвращается стоимость +∞. if i \< 0 or j \< 0:
|
||
>
|
||
> return inf
|
||
>
|
||
> \# Если уже есть запись, то возвращается она. if mem\[i\]\[j\] != -1:
|
||
>
|
||
> return mem\[i\]\[j\]
|
||
>
|
||
> \# Минимальная стоимость пути от левого и верхнего элементов. up = min_path_sum_dfs_mem(grid, mem, i - 1, j)
|
||
>
|
||
> left = min_path_sum_dfs_mem(grid, mem, i, j - 1)
|
||
>
|
||
> \# Запись и возвращение минимальной стоимости пути от верхнего левого \# угла до (i, j).
|
||
>
|
||
> mem\[i\]\[j\] = min(left, up) + grid\[i\]\[j\] return mem\[i\]\[j\]
|
||
>
|
||
> После введения мемоизации решения всех подзадач вычисляются только один раз, как показано на рис. 14.15. Поэтому временная сложность зависит от общего числа состояний, т. е. от размера сетки *O*(*nm*).
|
||
|
||
|
||
|
||
> **Рис. 14.15.** Дерево рекурсии мемоизации
|
||
|
||
##### Третий метод: динамическое программирование
|
||
|
||
> Ниже представлена реализация решения с использованием итеративного под- хода динамического программирования.
|
||
>
|
||
> \# === File: min_path_sum.py ===
|
||
>
|
||
> def min_path_sum_dp(grid: list\[list\[int\]\]) -\> int:
|
||
>
|
||
> \"\"\" Минимальная стоимость пути: динамическое программирование.\"\"\" n, m = len(grid), len(grid\[0\])
|
||
>
|
||
> \# Инициализация таблицы dp.
|
||
>
|
||
> dp = \[\[0\] \* m for \_ in range(n)\] dp\[0\]\[0\] = grid\[0\]\[0\]
|
||
>
|
||
> \# Переход состояния: первая строка. for j in range(1, m):
|
||
>
|
||
> dp\[0\]\[j\] = dp\[0\]\[j - 1\] + grid\[0\]\[j\] \# Переход состояния: первый столбец.
|
||
>
|
||
> for i in range(1, n):
|
||
>
|
||
> dp\[i\]\[0\] = dp\[i - 1\]\[0\] + grid\[i\]\[0\]
|
||
>
|
||
> \# Переход состояния: остальные строки и столбцы. for i in range(1, n):
|
||
>
|
||
> for j in range(1, m):
|
||
>
|
||
> dp\[i\]\[j\] = min(dp\[i\]\[j - 1\], dp\[i - 1\]\[j\]) + grid\[i\]\[j\] return dp\[n - 1\]\[m - 1\]
|
||
>
|
||
> На рис. 14.16 демонстрируется процесс перехода состояний для минималь- ной стоимости пути, который охватывает всю сетку, поэтому **временная сложность составляет** *O*(*nm*). Размер массива *dp* равен *n*×*m*, следовательно, **пространственная сложность также составляет** *O*(*nm*).
|
||
|
||
|
||
|
||
> **Рис. 14.16.** Динамическое программирование для минимальной стоимости пути. Шаг 1
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.16.** *Продолжение*. Шаги 2--4
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.16.** *Продолжение*. Шаги 5--7
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.16.** *Продолжение*. Шаги 8--10
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.16.** *Окончание*. Шаги 11--12
|
||
|
||
##### Оптимизация пространства
|
||
|
||
> Поскольку каждая ячейка зависит только от ячеек слева и сверху, для реали- зации таблицы *dp* можно использовать одномерный массив. Обратите внима- ние, что, поскольку массив dp может представлять только одну строку состоя- ния, невозможно заранее инициализировать состояние первого столбца, его необходимо обновлять при обходе каждой строки.
|
||
>
|
||
> \# === File: min_path_sum.py ===
|
||
>
|
||
> def min_path_sum_dp_comp(grid: list\[list\[int\]\]) -\> int:
|
||
>
|
||
> \"\"\" Минимальная стоимость пути: динамическое программирование с оптимизацией пространства.\"\"\"
|
||
>
|
||
> n, m = len(grid), len(grid\[0\]) \# Инициализация таблицы dp.
|
||
>
|
||
> dp = \[0\] \* m
|
||
>
|
||
> \# Переход состояния: первая строка. dp\[0\] = grid\[0\]\[0\]
|
||
>
|
||
> for j in range(1, m):
|
||
>
|
||
> dp\[j\] = dp\[j - 1\] + grid\[0\]\[j\]
|
||
>
|
||
> \# Переход состояния: остальные строки. for i in range(1, n):
|
||
>
|
||
> \# Переход состояния: первый столбец. dp\[0\] = dp\[0\] + grid\[i\]\[0\]
|
||
>
|
||
> \# Переход состояния: остальные столбцы. for j in range(1, m):
|
||
>
|
||
> dp\[j\] = min(dp\[j - 1\], dp\[j\]) + grid\[i\]\[j\] return dp\[m - 1\]
|
||
|
||
#### задача о рюкзаке 0-1
|
||
|
||
> Задача о рюкзаке является отличным примером для начала изучения динами- ческого программирования и представляет собой одну из наиболее распростра- ненных форм этой задачи. Существует множество ее вариаций, таких как задача о рюкзаке 0-1, задача о полном рюкзаке, задача о многократном рюкзаке и др.
|
||
>
|
||
> В этом разделе мы сначала решим наиболее распространенную задачу о рюкзаке 0-1.
|
||
>
|
||
> Обратите внимание на рис. 14.17: поскольку нумерация предметов *i* начи- нается с 1, а индексация массива с 0, то предмету *i* соответствует масса *wgt*\[*i* -- 1\] и стоимость *val*\[*i* -- 1\].
|
||
|
||
|
||
|
||
> **Рис. 14.17.** Пример данных для задачи о рюкзаке 0-1
|
||
>
|
||
> Задачу о рюкзаке 0-1 можно рассматривать как процесс, состоящий из *n* эта- пов принятия решений. Для каждого предмета существует два решения: не класть в рюкзак или класть. Таким образом, задача соответствует модели дерева решений. Цель задачи -- найти максимальную стоимость предметов, которые можно поместить в рюкзак при заданной вместимости, что с высокой вероятностью
|
||
>
|
||
> является задачей динамического программирования.
|
||
|
||
####### Шаг 1: обдумывание каждого этапа принятия решения, определение состояния, получение таблицы dp
|
||
|
||
> Для каждого предмета справедливо утверждение: если предмет не класть в рюкзак, вместимость рюкзака не изменится; если класть, вместимость умень- шится. Отсюда определяется состояние: текущий номер предмета *i* и вмести- мость рюкзака *c*, обозначается как \[*i*, *c*\].
|
||
>
|
||
> Подзадача, соответствующая состоянию \[*i*, *c*\], заключается в **нахождении максимальной стоимости первых** *i* **предметов в рюкзаке вместимостью** *c*, обозначается как *dp*\[*i*, *c*\].
|
||
>
|
||
> Требуется получить *dp*\[*n*, *cap*\], поэтому необходима двумерная таблица dp размером (*n* + 1) × (*cap* + 1).
|
||
|
||
####### Шаг 2: выявление оптимальной подструктуры и вывод уравнения перехода состояния
|
||
|
||
> После принятия решения по предмету *i* остается подзадача принятия решений для первых *i* -- 1 предметов, которая делится на следующие два случая:
|
||
|
||
1) **не класть предмет** *i*: вместимость рюкзака не изменяется, состояние переходит в \[*i* -- 1, *c*\];
|
||
|
||
2) **класть предмет** *i*: вместимость рюкзака уменьшается на *wgt*\[*i* -- 1\], стои- мость увеличивается на *val*\[*i* -- 1\], состояние переходит в \[*i* -- 1, *c* -- *wgt*\[*i* -- 1\]\].
|
||
|
||
> Этот анализ показывает оптимальную подструктуру задачи: **максимальная стоимость** *dp*\[*i*, *c*\] **равна большей из двух стоимостей**: **не класть предмет** *i* **и класть предмет** *i*. Отсюда выводится уравнение перехода состояния:
|
||
>
|
||
> *dp*\[*i*, *c*\] = max(*dp*\[*i* -- 1, *c*\], *dp*\[*i* -- 1, *c* -- *wgt*\[*i* -- 1\]\] + *val*\[*i* -- 1\]).
|
||
>
|
||
> Следует отметить, что если текущая масса предмета wgt\[*i* -- 1\] превышает оставшуюся вместимость рюкзака c, то можно выбрать только не класть пред- мет в рюкзак.
|
||
|
||
####### Шаг 3: определение граничных условий и порядка перехода состояния
|
||
|
||
> Когда нет предметов или вместимость рюкзака равна 0, максимальная стои- мость равна 0, т. е. первый столбец *dp*\[*i*, 0\] и первая строка *dp*\[0, *c*\] равны 0.
|
||
>
|
||
> Текущее состояние \[*i*, *c*\] исходит из верхнего состояния \[*i* -- 1, *c*\] и левого верх- него состояния \[*i* -- 1, *c* -- *wgt*\[*i* -- 1\]\], поэтому достаточно пройтись по всей табли- це *dp* двумя вложенными циклами.
|
||
>
|
||
> На основе вышеизложенного анализа реализуем методы полного перебора, мемоизации поиска и динамического программирования.
|
||
|
||
1. **Первый метод: полный перебор**
|
||
|
||
> Код поиска включает следующие элементы.
|
||
|
||
- **Рекурсивные параметры**: состояние \[*i*, *c*\].
|
||
|
||
- **Возвращаемое значение**: решение подзадачи *dp*\[*i*, *c*\].
|
||
|
||
<!-- -->
|
||
|
||
- **Условие завершения**: номер предмета выходит за пределы *i* = 0 или оставшаяся вместимость рюкзака равна 0, рекурсия завершается и воз- вращается стоимость 0.
|
||
|
||
- **Обрезка**: если текущая масса предмета превышает оставшуюся вмести- мость рюкзака, можно выбрать только не класть предмет в рюкзак.
|
||
|
||
> \# === File: knapsack.py ===
|
||
>
|
||
> def knapsack_dfs(wgt: list\[int\], val: list\[int\], i: int, c: int) -\> int: \"\"\" Рюкзак 0-1: полный перебор.\"\"\"
|
||
>
|
||
> \# Если все предметы выбраны или рюкзак не имеет оставшейся вместимости, \# возвращается стоимость 0.
|
||
>
|
||
> if i == 0 or c == 0: return 0
|
||
>
|
||
> \# Если вес превышает вместимость рюкзака, можно выбрать только не класть \# в рюкзак.
|
||
>
|
||
> if wgt\[i - 1\] \> c:
|
||
>
|
||
> return knapsack_dfs(wgt, val, i - 1, c)
|
||
>
|
||
> \# Вычисление максимальной стоимости без предмета i и с ним. no = knapsack_dfs(wgt, val, i - 1, c)
|
||
>
|
||
> yes = knapsack_dfs(wgt, val, i - 1, c - wgt\[i - 1\]) + val\[i - 1\] \# Возвращение большей из двух стоимостей.
|
||
>
|
||
> return max(no, yes)
|
||
>
|
||
> Поскольку каждый предмет создает две ветви поиска -- не выбирать и выби- рать, временная сложность составляет *O*(2*n*), как показано на рис. 14.18.
|
||
>
|
||
> При наблюдении за деревом рекурсии легко заметить наличие перекрыва- ющихся подзадач, таких как *dp*\[1, 10\]. А когда количество предметов и вмести- мость рюкзака велики, особенно если есть много предметов с одинаковым ве- сом, количество перекрывающихся подзадач значительно увеличивается.
|
||
|
||
+-----------+--------+--------------+-----+--------+-----+--------------------------------------------------------+
|
||
| *Нет* | | | | > *Да* | | > *Положить предмет 3?* |
|
||
+===========+========+==============+=====+========+=====+========================================================+
|
||
| | | | | | | > **Обрезка:** *Масса предмета \> Вместимость рюкзака* |
|
||
+-----------+--------+--------------+-----+--------+-----+--------------------------------------------------------+
|
||
| > *Нет* | > *Да* | *Не* | *т* | | | > *Да Положить предмет* **2***?* |
|
||
+-----------+--------+--------------+-----+--------+-----+--------------------------------------------------------+
|
||
|
||
> **Рис. 14.18.** Дерево рекурсии полного перебора для задачи о рюкзаке 0-1
|
||
|
||
##### Второй метод: мемоизация
|
||
|
||
> Чтобы вычислять перекрывающиеся подзадачи только один раз, используем список запоминания mem для записи решений подзадач, в котором mem\[i\]\[c\] соответствует *dp*\[*i*, *c*\].
|
||
>
|
||
> После введения мемоизации временная сложность будет зависеть от коли- чества подзадач, т. е. *O*(*n* × *cap*). Ниже приведен код реализации.
|
||
>
|
||
> \# === File: knapsack.py === def knapsack_dfs_mem(
|
||
>
|
||
> wgt: list\[int\], val: list\[int\], mem: list\[list\[int\]\], i: int, c: int
|
||
>
|
||
> ) -\> int:
|
||
>
|
||
> \"\"\" Рюкзак 0-1: мемоизация\"\"\"
|
||
>
|
||
> \# Если все предметы выбраны или в рюкзаке нет оставшейся вместимости, \# возвращается значение 0.
|
||
>
|
||
> if i == 0 or c == 0: return 0
|
||
>
|
||
> \# Если запись уже существует, возврат напрямую. if mem\[i\]\[c\] != -1:
|
||
>
|
||
> return mem\[i\]\[c\]
|
||
>
|
||
> \# Если превышает вместимость рюкзака, выбирается не класть в рюкзак. if wgt\[i - 1\] \> c:
|
||
>
|
||
> return knapsack_dfs_mem(wgt, val, mem, i - 1, c)
|
||
>
|
||
> \# Вычисление максимальной стоимости без и с включением предмета i. no = knapsack_dfs_mem(wgt, val, mem, i - 1, c)
|
||
>
|
||
> yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt\[i - 1\]) + val\[i - 1\] \# Запись и возврат наибольшей стоимости из двух вариантов.
|
||
>
|
||
> mem\[i\]\[c\] = max(no, yes) return mem\[i\]\[c\]
|
||
>
|
||
> На рис. 14.19 изображены обрезанные ветви поиска в процессе мемоизации.
|
||
|
||
|
||
|
||
> **Рис. 14.19.** Рекурсивное дерево мемоизации для задачи о рюкзаке 0-1
|
||
|
||
##### Третий метод: динамическое программирование
|
||
|
||
> Динамическое программирование представляет собой процесс заполнения таблицы *dp* в процессе перехода между состояниями, как показано в коде ниже.
|
||
>
|
||
> \# === File: knapsack.py ===
|
||
>
|
||
> def knapsack_dp(wgt: list\[int\], val: list\[int\], cap: int) -\> int: \"\"\" Рюкзак 0-1: динамическое программирование.\"\"\"
|
||
>
|
||
> n = len(wgt)
|
||
>
|
||
> \# Инициализация таблицы dp.
|
||
>
|
||
> dp = \[\[0\] \* (cap + 1) for \_ in range(n + 1)\] \# Переход между состояниями.
|
||
>
|
||
> for i in range(1, n + 1):
|
||
>
|
||
> for c in range(1, cap + 1): if wgt\[i - 1\] \> c:
|
||
>
|
||
> \# Если превышается вместимость рюкзака, то предмет i не выбирается. dp\[i\]\[c\] = dp\[i - 1\]\[c\]
|
||
>
|
||
> else:
|
||
>
|
||
> \# Наибольшее значение из двух вариантов: не выбирать \# и выбирать предмет i.
|
||
>
|
||
> dp\[i\]\[c\] = max(dp\[i - 1\]\[c\], dp\[i - 1\]\[c - wgt\[i - 1\]\] + val\[i - 1\]) return dp\[n\]\[cap\]
|
||
>
|
||
> Временная и пространственная сложность определяются размером массива
|
||
>
|
||
> *dp*, т. е. *O*(*n* × *cap*), как показано на рис. 14.20.
|
||
|
||
|
||
|
||
> **Рис. 14.20.** Динамическое программирование для задачи о рюкзаке 0-1. Шаг 1
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.20.** *Продолжение*. Шаги 2--4
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.20.** *Продолжение*. Шаги 5--7
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.20.** *Продолжение*. Шаги 8--10
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.20.** *Продолжение*. Шаги 11--13
|
||
>
|
||
> 
|
||
>
|
||
> **Рис. 14.20.** *Окончание*. Шаг 14
|
||
|
||
##### Оптимизация пространства
|
||
|
||
> Поскольку каждое состояние зависит только от состояния предыдущей строки, можно использовать два массива для продвижения и снизить пространствен- ную сложность с *O*(*n*2) до *O*(*n*).
|
||
>
|
||
> А можно ли реализовать оптимизацию пространства, используя только один массив? Заметим, что каждое состояние переходит из верхней или левой верх- ней ячейки. Если используется только один массив, то при начале обхода стро- ки *i* массив все еще хранит состояние строки *i* -- 1.
|
||
|
||
- Если обход выполняется в прямом порядке, то при достижении *dp*\[*i*, *j*\] значения из левой верхней части *dp*\[*i* -- 1, 1\] \~ *dp*\[*i* -- 1, *j* -- 1\] могут быть уже перезаписаны, что делает невозможным получение правильного резуль- тата перехода состояния.
|
||
|
||
- Если обход выполняется в обратном порядке, то проблема перезаписи не возникает, и переход состояния можно выполнить корректно.
|
||
|
||
> На рис. 14.21 демонстрируется процесс перехода от строки *i* = 1 к строке *i* = 2 с использованием одного массива. Проанализируйте различия при прямом и обратном обходах.
|
||
|
||
|
||
|
||
> **Рис. 14.21.** Динамическое программирование с оптимизацией пространства для задачи о рюкзаке 0-1. Шаг 1
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.21.** *Продолжение*. Шаги 2--4
|
||
>
|
||
> 
|
||
|
||
+---------------------------------------------------------------------------------------------------------------+
|
||
| > Шаг 6 Масса Стоимость |
|
||
| > |
|
||
| > **wgt val** |
|
||
| > |
|
||
| > Используется один |
|
||
| > |
|
||
| > одномерный массив **dp** |
|
||
| > |
|
||
| > После завершения обхода в массиве **dp** содержатся все решения для i = 2 |
|
||
+=======================================================+===========================+===========================+
|
||
| | | |
|
||
+-------------------------------------------------------+---------------------------+---------------------------+
|
||
|
||
> **Рис. 14.21.** *Окончание*. Шаги 5--6
|
||
>
|
||
> В коде реализации необходимо просто удалить первую размерность *i* из массива dp и изменить внутренний цикл на обратный обход.
|
||
>
|
||
> \# === File: knapsack.py ===
|
||
>
|
||
> def knapsack_dp_comp(wgt: list\[int\], val: list\[int\], cap: int) -\> int:
|
||
>
|
||
> \"\"\" Рюкзак 0-1: динамическое программирование с оптимизацией пространства.\"\"\" n = len(wgt)
|
||
>
|
||
> \# Инициализация таблицы dp. dp = \[0\] \* (cap + 1)
|
||
>
|
||
> \# Переход между состояниями. for i in range(1, n + 1):
|
||
>
|
||
> \# Обратный обход.
|
||
>
|
||
> for c in range(cap, 0, -1): if wgt\[i - 1\] \> c:
|
||
>
|
||
> \# Если превышается вместимость рюкзака, то предмет i не выбирается.
|
||
>
|
||
> dp\[c\] = dp\[c\]
|
||
>
|
||
> else:
|
||
>
|
||
> \# Наибольшее значение из двух вариантов: не выбирать и выбирать \# предмет i.
|
||
>
|
||
> dp\[c\] = max(dp\[c\], dp\[c - wgt\[i - 1\]\] + val\[i - 1\]) return dp\[cap\]
|
||
|
||
#### задача о полном рюкзаке
|
||
|
||
> В этом разделе мы сначала решим еще одну распространенную задачу о рюк- заке -- задачу о полном рюкзаке. А затем рассмотрим ее частный случай -- за- дачу о размене монет.
|
||
|
||
### Задача о полном рюкзаке
|
||
|
||
|
||
|
||
> **Рис. 14.22.** Пример данных для задачи о полном рюкзаке
|
||
|
||
##### Динамическое программирование
|
||
|
||
> Задача о полном рюкзаке очень похожа на задачу о рюкзаке 0-1. **Различие лишь в том**, **что количество выборов предметов не ограничено**.
|
||
|
||
- В задаче о рюкзаке 0-1 каждый предмет существует в единственном эк- земпляре, поэтому после помещения предмета *i* в рюкзак можно выби- рать только из первых *i* -- 1 предметов.
|
||
|
||
- В задаче о полном рюкзаке количество предметов не ограничено, поэто- му **после помещения предмета** *i* **в рюкзак можно продолжать вы- бирать из первых** *i* **предметов**.
|
||
|
||
> В условиях задачи о полном рюкзаке изменение состояния \[*i*, *c*\] делится на два случая.
|
||
|
||
- **Не помещать предмет** *i*: аналогично задаче о рюкзаке 0-1, переход к \[*i* -- 1, *[c]{.underline}*\].
|
||
|
||
- **Помещать предмет** *i*: в отличие от задачи о рюкзаке 0-1, переход к \[*i*, *c* -- *wgt*\[*i* -- 1\]\].
|
||
|
||
> Таким образом, уравнение перехода состояния меняется на следующее:
|
||
>
|
||
> *dp*\[*i*, *c*\] = max(*dp*\[*i* -- 1, *c*\], *dp*\[*i*, *c* -- *wgt*\[*i* -- 1\]\] + *val*\[*i* -- 1\]).
|
||
|
||
##### Код реализации
|
||
|
||
> По сравнению с кодом предыдущей задачи есть одно изменение в переходе состояния с *i* -- 1 на *i*, остальной код полностью совпадает.
|
||
>
|
||
> \# === File: unbounded_knapsack.py ===
|
||
>
|
||
> def unbounded_knapsack_dp(wgt: list\[int\], val: list\[int\], cap: int) -\> int: \"\"\"Полный рюкзак: динамическое программирование.\"\"\"
|
||
>
|
||
> n = len(wgt)
|
||
>
|
||
> \# Инициализация таблицы dp.
|
||
>
|
||
> dp = \[\[0\] \* (cap + 1) for \_ in range(n + 1)\] \# Переход между состояниями.
|
||
>
|
||
> for i in range(1, n + 1):
|
||
>
|
||
> for c in range(1, cap + 1): if wgt\[i - 1\] \> c:
|
||
>
|
||
> \# Если превышается вместимость рюкзака, то предмет i не выбирается. dp\[i\]\[c\] = dp\[i - 1\]\[c\]
|
||
>
|
||
> else:
|
||
>
|
||
> \# Наибольшее значение из двух вариантов: не выбирать и выбирать \# предмет i.
|
||
>
|
||
> dp\[i\]\[c\] = max(dp\[i - 1\]\[c\], dp\[i\]\[c - wgt\[i - 1\]\] + val\[i - 1\]) return dp\[n\]\[cap\]
|
||
|
||
##### Оптимизация пространства
|
||
|
||
> Поскольку текущее состояние исходит из состояний слева и сверху, **после оп- тимизации пространства следует выполнять прямой обход каждой стро- ки в таблице** *dp*.
|
||
>
|
||
> Этот порядок обхода противоположен порядку в задаче о рюкзаке 0-1. Из- учите рис. 14.23 для понимания различий между ними.
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.23.** Динамическое программирование для задачи о полном рюкзаке после оптими- зации пространства. Шаги 1--3
|
||
|
||
|
||
|
||
+---------------------------------------------------------------------------------------------+
|
||
| > Шаг 4 Масса Стоимость |
|
||
| > |
|
||
| > **wgt val** |
|
||
| > |
|
||
| > Используется один |
|
||
| > |
|
||
| > одномерный массив **dp** |
|
||
| > |
|
||
| > Прямой обход строки i = 2, выполнение перехода состояния |
|
||
+========================+===========================================+========================+
|
||
| | | |
|
||
+------------------------+-------------------------------------------+------------------------+
|
||
|
||
+---------------------------------------------------------------------------------------------+
|
||
| > Шаг 5 Масса Стоимость |
|
||
| > |
|
||
| > **wgt val** |
|
||
| > |
|
||
| > Используется один |
|
||
| > |
|
||
| > одномерный массив **dp** |
|
||
| > |
|
||
| > Прямой обход строки i = 2, выполнение перехода состояния |
|
||
+========================+===========================================+========================+
|
||
| | | |
|
||
+------------------------+-------------------------------------------+------------------------+
|
||
|
||
|
||
|
||
> **Рис. 14.23.** *Окончание*. Шаги 4--6
|
||
>
|
||
> Код реализации достаточно прост, необходимо лишь удалить первую раз- мерность массива dp.
|
||
>
|
||
> \# === File: unbounded_knapsack.py ===
|
||
>
|
||
> def unbounded_knapsack_dp_comp(wgt: list\[int\], val: list\[int\], cap: int) -\>
|
||
>
|
||
> int:
|
||
>
|
||
> \"\"\" Полный рюкзак: динамическое программирование с оптимизацией пространства.\"\"\" n = len(wgt)
|
||
>
|
||
> \# Инициализация таблицы dp. dp = \[0\] \* (cap + 1)
|
||
>
|
||
> \# Переход состояния.
|
||
>
|
||
> for i in range(1, n + 1): \# Прямой обход.
|
||
>
|
||
> for c in range(1, cap + 1): if wgt\[i - 1\] \> c:
|
||
>
|
||
> \# Если превышается вместимость рюкзака, то предмет i не выбирается. dp\[c\] = dp\[c\]
|
||
>
|
||
> else:
|
||
>
|
||
> \# Наибольшее значение из двух вариантов: не выбирать и выбирать \# предмет i.
|
||
>
|
||
> dp\[c\] = max(dp\[c\], dp\[c - wgt\[i - 1\]\] + val\[i - 1\]) return dp\[cap\]
|
||
|
||
### Задача о размене монет
|
||
|
||
> Задача о рюкзаке является представителем большого класса задач динамиче- ского программирования, имеющего множество вариаций, таких как задача о размене монет.
|
||
|
||
|
||
|
||
> **Рис. 14.24.** Пример данных для задачи о размене монет
|
||
|
||
##### Динамическое программирование
|
||
|
||
> **Задачу о размене монет можно рассматривать как частный случай зада- чи о полном рюкзаке** со следующими сходствами и различиями.
|
||
|
||
- Обе задачи можно преобразовать друг в друга: предмет соответствует монете, масса предмета соответствует номиналу монеты, вместимость рюкзака соответствует целевой сумме.
|
||
|
||
- Цели оптимизации противоположны: задача о полном рюкзаке стре- мится максимизировать стоимость предметов, задача о размене монет -- минимизировать количество монет.
|
||
|
||
- Задача о полном рюкзаке ищет решение, не превышающее вместимость рюкзака, задача о размене монет -- решение, точно соответствующее це- левой сумме.
|
||
|
||
####### Шаг 1: определение каждого этапа принятия решения, определение состояния для получения таблицы dp
|
||
|
||
> Подзадача состояния \[*i*, *a*\] заключается в **нахождении минимального коли- чества монет для составления суммы** *a* **из первых** *i* **видов монет**, обозна- чается как *dp*\[*i*, *a*\].
|
||
>
|
||
> Размер двумерной таблицы *dp* равен (*n* + 1) × (*amt* + 1).
|
||
|
||
####### Шаг 2: нахождение оптимальной подструктуры и выведение уравнения перехода состояния
|
||
|
||
> В этой задаче уравнение перехода состояния отличается от задачи о полном рюкзаке в двух моментах.
|
||
|
||
- В этой задаче требуется найти минимальное значение, поэтому опера- тор max() заменяется на min().
|
||
|
||
- Оптимизация направлена на количество монет, а не на стоимость това- ров, поэтому при выборе монеты выполняется операция +1.
|
||
|
||
> *dp*\[*i*, *a*\] = min(*dp*\[*i* -- 1, *a*\], *dp*\[*i*, *a* -- *coins*\[*i* -- 1\]\] + 1).
|
||
|
||
####### Шаг 3: определение граничных условий и порядка перехода состояния
|
||
|
||
> Когда целевая сумма равна 0, минимальное количество монет для ее составле- ния равно 0, т. е. все *dp*\[*i*, 0\] в первом столбце равны 0.
|
||
>
|
||
> При отсутствии монет **невозможно составить любую целевую сумму** \> 0, это является недопустимым решением. Чтобы функция min() в уравнении пе- рехода состояния могла распознавать и фильтровать недопустимые решения, предлагается использовать значение +∞ для их обозначения, т. е. все *dp*\[0, *a*\] в первой строке равны +∞.
|
||
|
||
##### Код реализации
|
||
|
||
> В большинстве языков программирования нет представления для значения +∞, поэтому часто используется максимальное значение типа int. Однако это может привести к переполнению при выполнении операции +1 в уравнении перехода. Поэтому для обозначения недопустимого решения будем использовать чис- ло *amt* + 1, поскольку максимальное количество монет для составления *amt* равно *amt*. Перед возвратом проверяется, равно ли *dp*\[*n*, *amt*\] значению *amt* + 1.
|
||
>
|
||
> Если равно, возвращается --1, что означает невозможность составления целе- вой суммы. Ниже приведен код реализации.
|
||
>
|
||
> \# === File: coin_change.py ===
|
||
>
|
||
> def coin_change_dp(coins: list\[int\], amt: int) -\> int: \"\"\" Размен монет: динамическое программирование.\"\"\" n = len(coins)
|
||
>
|
||
> MAX = amt + 1
|
||
>
|
||
> \# Инициализация таблицы dp.
|
||
>
|
||
> dp = \[\[0\] \* (amt + 1) for \_ in range(n + 1)\]
|
||
>
|
||
> \# Переход состояния: первая строка и первый столбец. for a in range(1, amt + 1):
|
||
>
|
||
> dp\[0\]\[a\] = MAX
|
||
>
|
||
> \# Переход состояния: остальные строки и столбцы. for i in range(1, n + 1):
|
||
>
|
||
> for a in range(1, amt + 1): if coins\[i - 1\] \> a:
|
||
>
|
||
> \# Если превышается целевая сумма, то монета i не выбирается. dp\[i\]\[a\] = dp\[i - 1\]\[a\]
|
||
>
|
||
> else:
|
||
>
|
||
> \# Наименьшее значение между не выбирать и выбирать монету i. dp\[i\]\[a\] = min(dp\[i - 1\]\[a\], dp\[i\]\[a - coins\[i - 1\]\] + 1)
|
||
>
|
||
> return dp\[n\]\[amt\] if dp\[n\]\[amt\] != MAX else -1
|
||
>
|
||
> На рис. 14.25 демонстрируется процесс динамического программирова- ния для задачи о размене монет, который очень похож на задачу о полном рюкзаке.
|
||
|
||
|
||
|
||
> **Рис. 14.25.** Динамическое программирование задачи о размене монет. Шаг 1
|
||
|
||
{width="3.3324004811898513in" height="1.8960411198600176in"}
|
||
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.25.** *Продолжение*. Шаги 2--4
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.25.** *Продолжение*. Шаги 5--7
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.25.** *Продолжение*. Шаги 8--10
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.25.** *Продолжение*. Шаги 11--13
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.25.** *Окончание*. Шаги 14--15
|
||
|
||
##### Оптимизация пространства
|
||
|
||
> Оптимизация пространства в задаче о размене монет осуществляется анало- гично задаче о полном рюкзаке.
|
||
>
|
||
> \# === File: coin_change.py ===
|
||
>
|
||
> def coin_change_dp_comp(coins: list\[int\], amt: int) -\> int:
|
||
>
|
||
> \"\"\" Размен монет: динамическое программирование с оптимизацией простран- ства.\"\"\"
|
||
>
|
||
> n = len(coins)
|
||
>
|
||
> MAX = amt + 1
|
||
>
|
||
> \# Инициализация таблицы dp. dp = \[MAX\] \* (amt + 1) dp\[0\] = 0
|
||
>
|
||
> \# Переход состояния.
|
||
>
|
||
> for i in range(1, n + 1): \# Прямой обход.
|
||
>
|
||
> for a in range(1, amt + 1): if coins\[i - 1\] \> a:
|
||
>
|
||
> \# Если превышается целевая сумма, то не выбирается монета i. dp\[a\] = dp\[a\]
|
||
>
|
||
> else:
|
||
>
|
||
> \# Наименьшее значение между не выбирать и выбирать монету i. dp\[a\] = min(dp\[a\], dp\[a - coins\[i - 1\]\] + 1)
|
||
>
|
||
> return dp\[amt\] if dp\[amt\] != MAX else -1
|
||
|
||
### 14.5.3 Задача о размене монет II
|
||
|
||
|
||
|
||
> **Рис. 14.26.** Пример данных для задачи о размене монет II
|
||
|
||
##### Динамическое программирование
|
||
|
||
> В отличие от предыдущей задачи здесь целью является определение количе- ства комбинаций, поэтому подзадача формулируется следующим образом: **количество комбинаций, которыми можно составить сумму** *a*, **используя первые** *i* **видов монет**. Таблица *dp* по-прежнему представляет собой двумер- ную матрицу размером (*n* + 1) × (*amt* + 1).
|
||
>
|
||
> Количество комбинаций для текущего состояния равно сумме количества комбинаций без выбора текущей монеты и с выбором текущей монеты. Урав- нение перехода состояния имеет вид:
|
||
>
|
||
> *dp*\[*i*, *a*\] = *dp*\[*i* -- 1, *a*\] + *dp*\[*i*, *a* -- *coins*\[*i* -- 1\]\].
|
||
>
|
||
> Если целевая сумма равна 0, то для достижения этой суммы не требуется вы- бирать монеты, поэтому все *dp*\[*i*, 0\] в первом столбце нужно инициализировать значением 1. Если монет нет, невозможно составить любую сумму больше 0, поэтому все *dp*\[0, *a*\] в первой строке равны 0.
|
||
|
||
##### Код реализации
|
||
|
||
> \# === File: coin_change_ii.py ===
|
||
>
|
||
> def coin_change_ii_dp(coins: list\[int\], amt: int) -\> int:
|
||
>
|
||
> \"\"\" Задача о размене монет II: динамическое программирование.\"\"\" n = len(coins)
|
||
>
|
||
> \# Инициализация таблицы dp.
|
||
>
|
||
> dp = \[\[0\] \* (amt + 1) for \_ in range(n + 1)\] \# Инициализация первого столбца.
|
||
>
|
||
> for i in range(n + 1): dp\[i\]\[0\] = 1
|
||
>
|
||
> \# Переход состояния.
|
||
>
|
||
> for i in range(1, n + 1):
|
||
>
|
||
> for a in range(1, amt + 1): if coins\[i - 1\] \> a:
|
||
>
|
||
> \# Если превышается целевая сумма, монета i не выбирается. dp\[i\]\[a\] = dp\[i - 1\]\[a\]
|
||
>
|
||
> else:
|
||
>
|
||
> \# Сумма двух вариантов: без выбора и с выбором монеты i. dp\[i\]\[a\] = dp\[i - 1\]\[a\] + dp\[i\]\[a - coins\[i - 1\]\]
|
||
>
|
||
> return dp\[n\]\[amt\]
|
||
|
||
##### Оптимизация пространства
|
||
|
||
> Метод оптимизации пространства аналогичен предыдущей задаче, достаточ- но удалить измерение монет.
|
||
>
|
||
> \# === File: coin_change_ii.py ===
|
||
>
|
||
> def coin_change_ii_dp_comp(coins: list\[int\], amt: int) -\> int:
|
||
>
|
||
> \"\"\" Задача о размене монет II: динамическое программирование с оптимизацией пространства.\"\"\"
|
||
>
|
||
> n = len(coins)
|
||
>
|
||
> \# Инициализация таблицы dp. dp = \[0\] \* (amt + 1)
|
||
>
|
||
> dp\[0\] = 1
|
||
>
|
||
> \# Переход состояния.
|
||
>
|
||
> for i in range(1, n + 1): \# Прямой обход.
|
||
>
|
||
> for a in range(1, amt + 1): if coins\[i - 1\] \> a:
|
||
>
|
||
> \# Если превышает целевую сумму, монета i не выбирается. dp\[a\] = dp\[a\]
|
||
>
|
||
> else:
|
||
>
|
||
> \# Сумма двух вариантов: без выбора и с выбором монеты i. dp\[a\] = dp\[a\] + dp\[a - coins\[i - 1\]\]
|
||
>
|
||
> return dp\[amt\]
|
||
|
||
#### задача расстояния редактирования
|
||
|
||
> Расстояние редактирования, также известное как расстояние Левенштейна, -- это минимальное количество изменений, необходимых для преобразования од- ной строки в другую. Обычно используется для измерения сходства двух после- довательностей в информационном поиске и обработке естественного языка.
|
||
>
|
||
> Для преобразования kitten в sitting требуется три шага редактирования, включая две операции замены и одну операцию добавления, как показано на рис. 14.27. Для преобразования hello в algo требуется три шага, включая две операции замены и одну операцию удаления.
|
||
|
||
|
||
|
||
> **Рис. 14.27.** Пример данных для задачи расстояния редактирования
|
||
>
|
||
> **Задачу расстояния редактирования можно естественным образом объяснить с помощью модели дерева решений**. Строки соответствуют уз- лам дерева, а один шаг редактирования (одна операция редактирования) соот- ветствует ребру дерева.
|
||
>
|
||
> При отсутствии ограничений на операции каждый узел может порождать множество ребер, каждое из которых соответствует одной операции, как пока- зано на рис. 14.28. Это означает, что существует множество возможных путей для преобразования hello в algo.
|
||
>
|
||
> С точки зрения дерева решений цель задачи -- найти кратчайший путь меж- ду узлом hello и узлом algo.
|
||
|
||
|
||
|
||
> **Рис. 14.28.** Представление задачи расстояния редакти- рования на основе модели дерева решений
|
||
|
||
##### Динамическое программирование
|
||
|
||
####### Шаг 1: обдумывание каждого этапа решения, определение состояния для получения таблицы dp
|
||
|
||
> Каждый шаг решения -- это выполнение одной операции редактирования над строкой *s*.
|
||
>
|
||
> Мы стремимся к тому, чтобы в процессе выполнения операций редактиро- вания размер задачи постепенно уменьшался, что позволяет построить подза- дачи. Пусть длины строк *s* и *t* равны *n* и *m* соответственно. Рассмотрим сначала последние символы этих двух строк *s*\[*n* -- 1\] и *t*\[*m* -- 1\].
|
||
|
||
- Если *s*\[*n* -- 1\] и *t*\[*m* -- 1\] одинаковы, их можно пропустить и сразу рассмо- треть *s*\[*n* -- 2\] и *t*\[*m* -- 2\].
|
||
|
||
- Если *s*\[*n* -- 1\] и *t*\[*m* -- 1\] различны, необходимо выполнить одну операцию редактирования над *s* (вставка, удаление, замена), чтобы последние сим- волы двух строк стали одинаковыми. После этого их можно будет про- пустить и рассмотреть задачу меньшего размера.
|
||
|
||
> Таким образом, каждый шаг решения (операция редактирования) в строке *s* приводит к изменению оставшихся символов, которые необходимо сопоста- вить в *s* и *t*. Поэтому состояние определяется как текущие рассматриваемые *i*-й и *j*-й символы в *s* и *t*, обозначим его как \[*i*, *j*\].
|
||
>
|
||
> Подзадача, соответствующая состоянию \[*i*, *j*\]: **минимальное количество шагов редактирования**, **необходимых для преобразования первых** *i* **сим- волов** *s* **в первые** *j* **символов** *t*.
|
||
>
|
||
> Таким образом, получаем двумерную таблицу *dp* размером (*i* + 1) × (*j* + 1).
|
||
|
||
####### Шаг 2: нахождение оптимальной подструктуры и вывод уравнения перехода состояния
|
||
|
||
> Рассмотрим подзадачу *dp*\[*i*, *j*\], в которой последние символы двух соответству- ющих строк -- это *s*\[*i* -- 1\] и *t*\[*j* -- 1\]. В зависимости от различных операций редак- тирования можно выделить три случая, представленные на рис. 14.29.
|
||
|
||
1. Добавление *t*\[*j* -- 1\] после *s*\[*i* -- 1\], тогда оставшаяся подзадача -- *dp*\[*i*, *j* -- 1\].
|
||
|
||
2. Удаление *s*\[*i* -- 1\], тогда оставшаяся подзадача -- *dp*\[*i* -- 1, *j*\].
|
||
|
||
3. Замена *s*\[*i* -- 1\] на *t*\[*j* -- 1\], тогда оставшаяся подзадача -- *dp*\[*i* -- 1, *j* -- 1\].
|
||
|
||
|
||
|
||
> **Рис. 14.29.** Переходы состояний для расстояния редактирования
|
||
>
|
||
> На основании вышеизложенного анализа можно получить оптимальную подструктуру: минимальное количество шагов редактирования для *dp*\[*i*, *j*\] равно минимальному количеству шагов редактирования среди *dp*\[*i*, *j* -- 1\], *dp*\[*i* -- 1, *j*\], *dp*\[*i* -- 1, *j* -- 1\] плюс 1 шаг за текущее редактирование. Соответствую- щее уравнение перехода состояния выглядит следующим образом:
|
||
>
|
||
> *dp*\[*i*, *j*\] = min(*dp*\[*i*, *j --* 1\], *dp*\[*i* -- 1, *j*\], *dp*\[*i* -- 1, *j --* 1\]) + 1.
|
||
>
|
||
> Обратите внимание, что **если** *s*\[*i* -- 1\] **и** *t*\[*j* -- 1\] **совпадают**, **то редактирова- ние текущего символа не требуется**, и уравнение перехода состояния в этом случае будет следующим:
|
||
>
|
||
> *dp*\[*i*, *j*\] = *dp*\[*i* -- 1, *j --* 1\].
|
||
|
||
####### Шаг 3: определение граничных условий и порядка перехода состояний
|
||
|
||
> Когда обе строки пусты, количество шагов редактирования равно 0, т. е. *dp*\[0, 0\] = 0. Если *s* пустая, а *t* непустая, минимальное количество шагов редактирования равно длине *t*, т. е. первая строка *dp*\[0, *j*\] = *j*. Если *s* непустая, а *t* пустая, минимальное количество шагов редактирования равно длине *s*, т. е. первый столбец *dp*\[*i*, 0\] = *i*.
|
||
>
|
||
> Анализируя уравнение перехода состояния, решение *dp*\[*i*, *j*\] зависит от ре- шения слева, сверху и слева сверху. Поэтому можно обойти всю таблицу *dp* в прямом порядке с помощью двух вложенных циклов.
|
||
|
||
##### Код реализации
|
||
|
||
> \# === File: edit_distance.py ===
|
||
>
|
||
> def edit_distance_dp(s: str, t: str) -\> int:
|
||
>
|
||
> \"\"\" Расстояние редактирования: динамическое программирование.\"\"\" n, m = len(s), len(t)
|
||
>
|
||
> dp = \[\[0\] \* (m + 1) for \_ in range(n + 1)\]
|
||
>
|
||
> \# Переход состояния: первая строка и первый столбец. for i in range(1, n + 1):
|
||
>
|
||
> dp\[i\]\[0\] = i
|
||
>
|
||
> for j in range(1, m + 1): dp\[0\]\[j\] = j
|
||
>
|
||
> \# Переход состояния: остальные строки и столбцы. for i in range(1, n + 1):
|
||
>
|
||
> for j in range(1, m + 1):
|
||
>
|
||
> if s\[i - 1\] == t\[j - 1\]:
|
||
>
|
||
> \# Если два символа равны, то они пропускаются. dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\]
|
||
>
|
||
> else:
|
||
>
|
||
> \# Минимальное количество шагов редактирования =
|
||
>
|
||
> \# минимальное количество шагов для вставки, удаления, замены + 1. dp\[i\]\[j\] = min(dp\[i\]\[j - 1\], dp\[i - 1\]\[j\], dp\[i - 1\]\[j - 1\]) + 1
|
||
>
|
||
> return dp\[n\]\[m\]
|
||
>
|
||
> Как видно из рис. 14.30, процесс перехода состояния для задачи расстояния редактирования очень похож на задачу о рюкзаке, и его можно рассматривать как заполнение двумерной сетки.
|
||
|
||
|
||
|
||
> **Рис. 14.30.** Динамическое программирование для расстояния редактирования. Шаг 1
|
||
|
||
{width="3.4433311461067366in" height="2.0345833333333334in"}
|
||
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.30.** *Продолжение*. Шаги 2--4
|
||
|
||
{width="3.4471598862642168in" height="2.0345833333333334in"}
|
||
|
||
|
||
|
||
> **Рис. 14.30.** *Продолжение*. Шаги 5--7
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.30.** *Продолжение*. Шаги 8--10
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.30.** *Продолжение*. Шаги 11--13
|
||
>
|
||
> 
|
||
|
||
|
||
|
||
> **Рис. 14.30.** *Окончание*. Шаги 14--15
|
||
|
||
##### Оптимизация пространства
|
||
|
||
> Поскольку *dp*\[*i*, *j*\] зависит от *dp*\[*i* -- 1, *j*\], *dp*\[*i*, *j* -- 1\], *dp*\[*i* -- 1, *j* -- 1\], прямой обход те- ряет *dp*\[*i* -- 1, *j* -- 1\], а обратный обход не позволяет заранее построить *dp*\[*i*, *j* -- 1\]. Оба порядка обхода неприемлемы.
|
||
>
|
||
> Для оптимизации можно использовать переменную leftup, в которой будет временно хранится решение *dp*\[*i* -- 1, *j* -- 1\], что позволит учитывать только ре- шения слева и сверху. В этом случае ситуация аналогична задаче о полном рюк- заке, и можно использовать прямой обход. Код реализации представлен ниже.
|
||
>
|
||
> \# === File: edit_distance.py ===
|
||
>
|
||
> def edit_distance_dp_comp(s: str, t: str) -\> int:
|
||
>
|
||
> \"\"\" Расстояние редактирования: динамическое программирование с оптимизацией пространства.\"\"\"
|
||
>
|
||
> n, m = len(s), len(t) dp = \[0\] \* (m + 1)
|
||
>
|
||
> \# Переход состояния: первая строка. for j in range(1, m + 1):
|
||
>
|
||
> dp\[j\] = j
|
||
>
|
||
> \# Переход состояния: остальные строки. for i in range(1, n + 1):
|
||
>
|
||
> \# Переход состояния: первый столбец.
|
||
>
|
||
> leftup = dp\[0\] \# Временное хранение dp\[i-1, j-1\]. dp\[0\] += 1
|
||
>
|
||
> \# Переход состояния: остальные столбцы. for j in range(1, m + 1):
|
||
>
|
||
> temp = dp\[j\]
|
||
>
|
||
> if s\[i - 1\] == t\[j - 1\]:
|
||
>
|
||
> \# Если два символа равны, то они пропускаются. dp\[j\] = leftup
|
||
>
|
||
> else:
|
||
>
|
||
> \# Минимальное количество шагов редактирования = минимальное \# количество шагов для вставки, удаления, замены + 1.
|
||
>
|
||
> dp\[j\] = min(dp\[j - 1\], dp\[j\], leftup) + 1
|
||
>
|
||
> leftup = temp \# Обновление для следующего шага dp\[i-1, j-1\]. return dp\[m\]
|
||
|
||
#### резюме
|
||
|
||
- Динамическое программирование разбивает задачу на подзадачи, со- храняет их решения и избегает повторных вычислений, что повышает эффективность.
|
||
|
||
- Все задачи динамического программирования можно решить с помо- щью перебора (поиска в глубину), но в дереве рекурсии много повторяю- щихся подзадач, что делает его крайне неэффективным. Использование мемоизации позволяет сохранить решения всех вычисленных подзадач, гарантируя, что каждая из них будет решена только один раз.
|
||
|
||
- Мемоизация -- это рекурсивный подход сверху вниз, тогда как динами- ческое программирование -- это итеративный подход снизу вверх, по- хожий на заполнение таблицы. Поскольку текущее состояние зависит только от некоторых локальных состояний, можно устранить одно из- мерение таблицы *dp* и уменьшить пространственную сложность.
|
||
|
||
- Разбиение задачи на подзадачи -- это общий алгоритмический подход, который имеет различную реализацию в методах «разделяй и властвуй», динамическом программировании и поиске с возвратом.
|
||
|
||
- Задачи динамического программирования обладают тремя основны- ми свойствами: повторяющиеся подзадачи, оптимальная подструктура и отсутствие последствий.
|
||
|
||
- Если оптимальное решение исходной задачи можно построить из оптимальных решений подзадач, то оно обладает оптимальной под- структурой.
|
||
|
||
<!-- -->
|
||
|
||
- Отсутствие последствий означает, что будущее развитие состояния за- висит только от этого состояния и не зависит от всех предыдущих со- стояний. Многие задачи комбинаторной оптимизации не обладают этим свойством, и для их быстрого решения нельзя использовать динамиче- ское программирование.
|
||
|
||
##### Задача о рюкзаке
|
||
|
||
- Задача о рюкзаке -- одна из самых типичных задач динамического про- граммирования, имеющая такие варианты, как рюкзак 0-1, полный рюк- зак и многократный рюкзак.
|
||
|
||
- Состояние задачи о рюкзаке 0-1 определяется как максимальная сто- имость первых *i* предметов в рюкзаке вместимостью *c*. На основе двух решений -- не класть в рюкзак и класть в рюкзак -- можно получить оп- тимальную подструктуру и построить уравнение перехода состояния. В оптимизации пространства, поскольку каждое состояние зависит от состояний «прямо сверху» и «слева сверху», необходимо обходить список в обратном порядке, чтобы избежать перезаписи состояния слева сверху.
|
||
|
||
- В задаче о полном рюкзаке количество каждого вида предметов не огра- ничено, поэтому переход состояния при выборе предметов отличает- ся от задачи о рюкзаке 0-1. Поскольку состояние зависит от состояний
|
||
|
||
> «прямо сверху» и «прямо слева», в оптимизации пространства следует делать обход в прямом порядке.
|
||
|
||
- Задача о размене монет является вариантом задачи о полном рюкзаке. Она изменяет поиск максимальной стоимости на поиск минимального количества монет. Поэтому в уравнении перехода состояния max() сле- дует заменить на min(). От условия не превышать вместимость рюкзака переходят к условию точно достичь целевой суммы. Для обозначения недопустимого решения, когда невозможно достичь целевой суммы, ис- пользуется значение *amt* + 1.
|
||
|
||
- В задаче о размене монет II вместо поиска минимального количества монет ищется количество комбинаций монет. Уравнение перехода со- стояния соответственно изменяется с min() на оператор суммы.
|
||
|
||
##### Задача расстоянии редактирования
|
||
|
||
- Расстояние редактирования (расстояние Левенштейна) используется для измерения сходства между двумя строками и определяется как ми- нимальное количество шагов редактирования, необходимых для преоб- разования одной строки в другую. Операции редактирования включают добавление, удаление и замену.
|
||
|
||
- Состояние задачи о расстоянии редактирования определяется как минимальное количество шагов редактирования, необходимых для изменения первых *i* символов строки *s* в первые *j* символов строки *t*. Когда *s*\[*i*\] ≠ *t*\[*j*\], существуют три решения: добавление, удаление и за- мена, каждое из которых имеет соответствующую оставшуюся подза- дачу. На основе этого можно выявить оптимальную подструктуру и по- строить уравнение перехода состояния. Когда *s*\[*i*\] = *t*\[*j*\], редактирование текущего символа не требуется.
|
||
|
||
- В задаче о расстоянии редактирования состояние зависит от состояний
|
||
|
||
> «прямо сверху», «прямо слева» и «слева сверху». Поэтому после опти- мизации пространства ни прямой, ни обратный обход не позволяют корректно выполнить переход состояния. Для решения этой проблемы используется переменная для временного хранения состояния слева сверху. Это позволяет преобразовать задачу в эквивалентную задаче о полном рюкзаке, и после оптимизации пространства можно выпол- нять прямой обход.
|
||
>
|
||
> Глава 15
|