Динамическое программирование: у меня есть перекрывающиеся подзадачи? - PullRequest
Новая
       25

Динамическое программирование: у меня есть перекрывающиеся подзадачи?

0 голосов
/ 11 октября 2018

Мой алгоритм

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

enter image description here

Мой псевдоалгоритм: 

function Step(cellNr):
    foreach neighborNr in neighbors_of(cellNr):
        if array_value(neighborNr) < array_value(cellNr):
            mark_cell(neighborNr)
            Step(neighborNr)
Step(centerNr)

Теперь приходит второйаспект, что я делаю это не только для одной начальной ячейки, но и для нескольких начальных ячеек, например

enter image description here

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

Я исследовал динамическое программирование и обнаружил, что для применения динамического программирования должны быть соблюдены два условия:

  • подзадачи должны перекрываться
  • подзадачи должны иметь оптимальную подструктуру

"[динамическое программирование] относится к упрощению сложной проблемы путем ее рекурсивного разбиения на более простые подзадачи [...] Если проблема может быть решенаОптимально, разбивая его на подзадачи и затем рекурсивно находя оптимальные решения подзадач, говорят, что он имеет оптимальную подструктуру. [...] Есть два ключевых атрибута, которые должна иметь проблема для того, чтобы dyприменимое программирование: оптимальная подструктура и перекрывающиеся подзадачи.Если проблема может быть решена путем объединения оптимальных решений непересекающихся подзадач, стратегия вместо этого называется «разделяй и властвуй».Вот почему сортировка слиянием и быстрая сортировка не классифицируются как проблемы динамического программирования.Оптимальная подструктура означает, что решение данной задачи оптимизации может быть получено путем комбинации оптимальных решений ее подзадач.Такие оптимальные подструктуры обычно описываются с помощью рекурсии.[...] Перекрывающиеся подзадачи означают, что пространство подзадач должно быть небольшим, то есть любой рекурсивный алгоритм, решающий проблему, должен снова и снова решать одни и те же подзадачи, а не генерировать новые подзадачи ». Википедия

Мне было интересно, является ли мой алгоритм динамическим программированием. Он определенно рекурсивный и кажется оптимальным в субструктуре. Однако я начинаю задумываться о перекрывающейся субструктуре.Пример с числами Фибоначчи, но мне кажется, что ключевым аспектом является то, что промежуточные результаты рекурсивного алгоритма могут быть сохранены. Для моего алгоритма промежуточные результаты не могут быть сохранены - по крайней мере, не для одного прогона одной стартовой ячейки. Однако, когдаЯ рассматриваю всю проблему со многими начальными ячейками, мы видим, что часть области соединена:

enter image description here

Допустим, мы начинаем с оранжевого 9на левом изображении и идите по зеленой дорожке, пока мы не достигнем синим цветом 5. Оттуда мы можем всеИтак, перейдем к синему 3 и синему 2. Мы заканчиваем наш алгоритм для левого оранжевого 9.

Теперь мы переходим к нижнему оранжевому 8 на правом изображении.Мы начинаем с этой восьмерки и идем по зеленому пути к зеленому 6. Оттуда мы получаем синий 5. Мы уже знаем из предыдущих вычислений (из оранжевого 9 на левом изображении), что синий 3 и синий 2достижимы из синего 5, поэтому мы можем просто пометить их одним махом, не пересчитывая путь.

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

Вопросы

  1. Является ли мой алгоритм / проблема динамическим программированием?Почему, почему нет?
  2. Если нет, могу ли я сделать это динамическим программированием, и если да, то как?

1 Ответ

0 голосов
/ 11 октября 2018

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

Это соответствует определению, как это:

Оптимальная структура?Да, ячейки, к которым я могу добраться из ячейки x, это x плюс объединение ячеек, к которым я могу добраться от меньших соседей x.

Перекрывающиеся подзадачи?Да, два соседа x могут совместно использовать одного и того же меньшего соседа.

Чтобы превратить ваш опубликованный алгоритм в алгоритм динамического программирования, вам просто нужно запомнить подзадачи следующим образом: 

function Step(cellNr):
    foreach neighborNr in neighbors_of(cellNr):
        if array_value(neighborNr) < array_value(cellNr) AND cell_is_not_marked(neighborNr):
            mark_cell(neighborNr)
            Step(neighborNr)
Step(centerNr)

Обратите внимание, что это также меняет ваш алгоритм с экспоненциального времени на линейное время, и что это поиск в глубину

...