Динамическое программирование. Базовые понятия.
Задача 1. Новый Лабиринт Амбера
Идея решения: Понятно, что в первую ячейку согласно условия мы попасть не можем, поэтому после чтения исходных данных занесем в нее 0, в не зависимости от того, что нам предлагается для неё при считывании исходных данных, а во вторую и третью мы можем попасть единственным образом с начальной нулевой ячейки. Для всех остальных ячеек у нас есть выбор: попасть в нее либо с ячейки под номером i–2, либо с ячейки под номером i–3. Выбирать, естественно будем ту, где перед этим уже имеется большая сумма. Схематически это можно изобразить так (на примере с условия задачи):
Номера ячеек | |||||
0 | 1 | 2 | 3 | 4 | 5 |
0 | 1000 | 2 | 3 | 1 | 3 |
Содержимое ячеек |
Заменяем содержимое ячейки 1 и начиная с четвертой ячейки, начинаем заниматься решением вопроса, откуда же выгоднее в неё попасть: с ячейки a[i–2] или a[i–3]?
Естественно, что выгоднее в ячейку под номером 4 попасть с ячейки под номером 2 (с индексом i–2), так как там уже есть 2 монетки и сумма будет 3, а в ячейке под номером 1 (с индексом i–3) уже накоплено 0 монеток, и сумма будет 1, что является не выгодным. Не заводя дополнительный массив, будем хранить в этой текущей рассматриваемой ячейке найденную сумму, которую формально можно описать так:
Тогда при переходе к выбору стратегии перехода в следующей ячейке под номером 5, наш выбор изменится на следующий:
Естественно, что и в эту ячейку выгоднее попасть с ячейки с индексом i–2, где хранится монет на единицу больше. В результате наша таблица будет иметь вид:
Номера ячеек | |||||
0 | 1 | 2 | 3 | 4 | 5 |
0 | 0 | 2 | 3 | 3 | 6 |
Содержимое ячеек |
В результате у нас в конечной (N-той) ячейке всегда будет находится ответ к задаче.
Описанный выше подход лежит в основе динамического программирования. В основу принципа динамического программирования положено следующую простую стратегию оптимальной политики, указанную Р.Беллманом и названную им принципом оптимальности: „Именно оптимальной политике присуще то свойство, что какими бы не были начальное состояние и первое решение, последующие решения составляют оптимальную политику относительно начального состояния, полученного в результате первого решения.”
Задача 2. Лесенка
Идея решения: Решение данной задачи немногим отличается от предыдущей только тем, что на каждую текующую рассматривуемую ступеньку мы можем попасть уже имея выбор не из 2-х возможных, а из K предыдущих ступенек. Этот подход легко реализуется при помощи дополнительного цикла. Чтобы не изменять логику поиска предыдущей программы зададим массив используя ту особенность языка паскаль, что нумеровать массив можно начиная с произвольного индекса.
Подсказка: массив чисел, хранящихся на ступеньках, следует объявить как a : array[-1000..1001] of longint;
Задача 3. Единицы
Идея решения: Понятно, что для того, чтобы получить число 1 достаточно просто написать одну единицу, а число 2 получается путем сложения двух еиниц. Дальнейшая логика такова: мы можем любое следующее число найти, прибавив к предыдущему одну единицу (a[k] = a[k-1] + 1) - это и есть первое приближение оптимального решения. После этого пробуем число k разложить на два множителя, и если это удалось, то сума единиц, входящих в каждый из сомножителей проверятся с текущим оптимальным значением a[k], если найденное число оказывется меньшим, естественно принимаем его за оптимальное. Искать разложение достаточно до sqrt(k).
Задача 4. Paint2D
Идея решения: Идею решения данной задачи разберем более детально.
(Продолжение следует)