Демистификация динамического программирования

demistifikacziya dinamicheskogo programmirovaniya

от Праджвал М

Есть много качественных статей о том, как стать разработчиком программного обеспечения. Они научат вас программировать, разрабатывать и использовать библиотеки. Но мало сделано для обучения Алгоритмы и Структуры данных. Независимо от того, насколько вы хорошо развиваетесь, без знания Алгоритмы и Структуры данных, вас нельзя нанять.

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

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

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

-> Identify subproblems
-> Learn how to solve subproblems
-> Identify that subproblems are repetitive 
-> Identify that subproblems have optimal substructure property
-> Learn to cache/store results of sub problems
-> Develop a recursive relation to solve the problem
-> Use top-down and bottom-up approach to solve the problem

На каком языке я буду пользоваться?

Я знаю, что большинство людей владеют или имеют опыт кодирования на JavaScript. Кроме того, как только вы научитесь JavaScript, его очень легко превратить в код Java. То же можно сказать о Python или C++. Хитрость состоит в том, чтобы понять проблемы на языке, который вам больше всего нравится. Потому я решил использовать JavaScript.

Эта публикация посвящена алгоритмам и, точнее, о динамическом программировании. В общем, это воспринимается как трудная тема. Если вы доберетесь до конца публикации, я уверен, что вы сможете самостоятельно решить многие проблемы динамического программирования ?.

Постановка проблемы

Problem: Given an integer n, find the minimum number of steps to reach integer 1.

At each step, you can:

Subtract 1,

Divide by 2, if it is divisible by 2

Divide by 3, if it is divisible by 3

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

Что такое подпроблема или состояние? Подпроблема/состояние – это меньший экземпляр исходной проблемы. Методы, используемые для решения исходной задачи и подзадачи, одинаковы.

Некоторые проблемы дадут вам правила, определяющие переходы сословий. Это одна из таких проблем. Эта проблема говорит, что вы можете перейти к n-1, n/2 или n/3, начиная с n. С другой стороны, есть проблемы, не определяющие переходы сословий. Вам придется разобраться в них самостоятельно. Я расскажу о подобных проблемах в другой публикации.

здесь,

Start state -> n
Goal -> 1
Intermediate states -> any integer number between 1 and n

Учитывая состояние (начальное или промежуточное), Вы всегда можете перейти к фиксированному количеству состояний.

from n you can move to :

n -> n-1 

if n % 2 == 0:
   n -> n/2
   
if n % 3 == 0:
   n -> n/3
   
example:

from 3 you can move to,
3 -> 3-1 = 2
3 -> 3/3 = 1

from 4 you can move to,
4 -> 4-1 = 3
4 -> 4/2 = 2

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

For n = 4:

approach one:
4 -> 3 -> 2 -> 1

approach two:
4 -> 2 -> 1 

approach three:
4 -> 3 -> 1

Здесь из трех подходов оптимальны подходы второй и третий, поскольку они требуют наименьшего количества ходов/переходов. Подход к одному худший, поскольку он требует больше ходов.

Объяснение терминологии учебника

Repetitive subproblems : You will end up solving the same problem more than once.

for n = 5
example:
5 -> 4 -> 3 -> 1
5 -> 4 -> 2 -> 1
5 -> 4 -> 3 -> 2 -> 1

observe here that 2 -> 1 occurs two times. 
also observe that 5 -> 4 occurs three times.

Optimal Substructure : Optimal solutions to subproblems give optimal solution to the entire problem

example:
2 -> 1 is optimal 
3 -> 1 is optimal 

when I am at 4,
4 -> 3 -> 2 -> 1 and 4 -> 3 -> 1 is possible
but the optimal solution of 4 is 4 -> 3 -> 1. The optimal solution of four comes from optimal solution of three (3 -> 1).

similarly,
4 -> 3 -> 2 -> 1 and 4 -> 2 -> 1 is possible
but the optimal solution of 4 is 4 -> 2 -> 1. The optimal solution of four comes from optimal solution of two (2 -> 1).

now 5,
The optimal solution of 5 depends on optimal solution to 4.
5 -> 4 -> 2 -> 1 and 5 -> 4 -> 3 -> 1 are optimal.

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

Мы решаем подзадачи всего один раз и решаем каждую подзадачу оптимально.

we will solve the subproblems 3 -> 1 and 2 -> 1 only once and optimally.

Now for 4 we will solve only once by 4 -> 3 -> 1 and optimally. You can also solve as 4 -> 2 -> 1 but that is left to you. 

Finally for 5 we will solve only once by 5 - > 4 -> 3 -> 1 and optimally.

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

Как измерить Оптимальность

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

In 5 -> 4 -> 3 -> 1 
for 5 -> 4 cost is 1 
for 4 -> 3 cost is 1
for 3 -> 1 cost is 1

The total cost of 5 -> 4 -> 3 -> 1 is the total sum of 3.

In In 5 -> 4 -> 3 -> 2 -> 1
for 5 -> 4 cost is 1
for 4 -> 3 cost is 1 
for 3 -> 2 cost is 1
for 2 -> 1 cost is 1
The total cost of 5 -> 3 -> 2 -> 1 is the total sum of 4.

The optimal solution of 5 -> 4 -> 3 -> 1 has a cost of three which is the minimum. Hence we can see that optimal solutions have optimal costs

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

For the above problem, let us define minOne as the function that we will use to solve the problem and the cost of moving from one state to another as 1.

if n = 5,
solution to 5 is cost + solution to 4
recursive formulae/relation is 
minOne(5) = 1 + minOne(4) 

Similarly,
if n = 6,
recursive formulae/relation is
minOne(6) = min(             
              1 + minOne(5),
              1 + minOne(3),
              1 + minOne(2) )

код

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

Top Down : Solve problems recursively. 
for n = 5, you will solve/start from 5, that is from the top of the problem.
It is a relatively easy approach provided you have a firm grasp on recursion. I say that this approach is easy as this method is as simple as transforming your recursive relation into code.

Bottom Up : Solve problems iteratively.
for n = 5, you will solve/start from 1, that is from the bottom of the problem.
This approach uses a for loop. It does not lead to stack overflow as in recursion. This approach is also slightly more optimal.

Какой подход лучше?

Это зависит от вашего комфорта. Оба дают одинаковые решения. В очень больших проблемах выгодно использовать снизу вверх, поскольку это не приводит к переполнению стека. Если вы выберете вход 10000, подход сверху вниз даст превышение максимального размера стека вызовов, но подход снизу вверх даст вам решение.

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

Подход «снизу вверх».

/*
Problem: Given an integer n, find the minimum number of steps to reach integer 1.
At each step, you can:
Subtract 1,
Divide by 2, if it is divisible by 2 
Divide by 3, if it is divisible by 2 
*/


// bottom-up
function minOneBottomUp(n) {

    const cache = [];
    // base condition
    cache[1] = 0;

    for (i = 2; i <= n; i++) {

        // initialize a , b and c to some very large numbers
        let a = 1000, b = 1000, c = 1000;

        // one step from i -> i-1
        a = 1 + cache[i - 1];

        // one step from i -> i/2 if i is divisible by 2
        if (i % 2 === 0) {
            b = 1 + cache[i / 2];
        }

        // one step from i -> i/3 if i is divisible by 3
        if (i % 3 === 0) {
            c = 1 + cache[i / 3];
        }

        // Store the minimum number of steps to reach i
        cache[i] = Math.min(a, b, c);
    }

    // return the number minimum number of steps to reach n
    return cache[n];
}

console.log(minOneBottomUp(1000));
Line 11 : The function that will solve the problem is named as minOneBottomUp. It takes n as the input.

Line 13 : The array that will be used to store results of every solved state so that there is no repeated computation is named cache. Some people like to call the array dp instead of cache. In general, cache[i] is interpreted as the minimum number of steps to reach 1 starting from i.

Line 15 : cache[1] = 0 This is the base condition. It says that minimum number of steps to reach 1 starting from 1 is 0.

Line 17 - 37 : For loop to fill up the cache with all states from 1 to n inclusive.

Line 20 : Initialize variables a, b and c to some large number. Here a represents minimum number of steps. If I did the operation n-1, b represents the minimum number of steps. If I did the operation n/2, c represents the minimum number of steps. If I did the operation n/3. The initial values of a, b and c depends upon the size of the problem.

Line 23 : a = 1 + cache[i-1]. This follows from the recursive relation we defined earlier.

Line 26 - 28: if(i % 2 == 0){
                  b = 1 + cache[i/2];
              }
              
This follows from the recursive relation we defined earlier.

Line 31 - 33: if(i % 3== 0){
                  c= 1 + cache[i/3];
              }
This follows from the recursive relation we defined earlier.

Line 36 : This the most important step.
cache[i] = Math.min(a, b, c). This essentially determines and stores which of a, b and c gave the minimum number of steps.

Line 40 : All the computations are completed. Minimum steps for all states from 1 to n is calculated. I return cache[n](minimum number of steps to reach 1 starting from n) which is the answer we wanted.

Line 43 : Testing code. It returns a value of 9

Подход сверху вниз

/*
Problem: Given an integer n, find the minimum number of steps to reach integer 1.
At each step, you can:
Subtract 1,
Divide by 2, if it is divisible by 2 
Divide by 3, if it is divisible by 2 
*/


// top-down
function minOne(n, cache) {

    // if the array value at n is not undefined, return the value at that index
    // This is the heart of dynamic programming 
    if (typeof (cache[n]) !== 'undefined') {
        return cache[n];
    }

    // if n has reached 1 return 0
    // terminating/base condition
    if (n <= 1) {
        return 0;
    }

    // initialize a , b and c to some very large numbers
    let a = 1000, b = 1000, c = 1000;

    // one step from n -> n-1
    a = 1 + minOne(n - 1, cache);

    // one step from n -> n/2 if n is divisible by 2
    if (n % 2 === 0) {
        b = 1 + minOne(n / 2, cache);
    }

    // one step from n -> n/3 if n is divisible by 3
    if (n % 3 === 0) {
        c = 1 + minOne(n / 3, cache);
    }

    // Store the minimum number of steps to reach n 
    return cache[n] = Math.min(a, b, c);

}



const cache = [];
console.log(minOne(1000, cache));
Line 11 : The function that will solve the problem is named as minOne. It takes n and cache as the inputs.

Line 15 - 16 : It checks if for a particular state the solution has been computed or not. If it is computed it returns the previously computed value. This is the top-down way of not doing repeated computation.

Line 21 - 23 : It is the base condition. It says that if n is 1 , the minimum number of steps is 0.

Line 26 :  Initialize variables a, b and c to some large number. Here a represents minimum number of steps if I did the operation n-1, b represents the minimum number of steps if I did the operation n/2 and c represents the minimum number of steps if I did the operation n/3. The initial values of a, b and c depends upon the size of the problem.

Line 29 : a = 1 + minOne(n-1, cache). This follows from the recursive relation we defined earlier.

Line 32 - 34 : if(n % 2 == 0){
                  b = 1 + minOne(n/2, cache);
              }
This follows from the recursive relation we defined earlier.

Line 37 - 39 : if(n % 3== 0){
                  c = 1 + minOne(n/3, cache);
              }
This follows from the recursive relation we defined earlier.

Line 42 : return cache[n] = Math.min(a, b, c) . This essentially determines and stores which of a, b and c gave the minimum number of steps.

Line 48 - 49 : Testing code. It returns a value of 9

Временная сложность

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

В этой задаче для заданного n есть п уникальные состояния/подпроблемы. Для удобства говорят, что каждое состояние решается за постоянное время. Отсюда сложность времени O(n*1).

Это можно проверить с помощью цикла for, который мы использовали в подходе снизу вверх. Мы видим, что для решения проблемы используем только один цикл for. Отсюда сложность времени O(n ) или линейный.

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

Сложность пространства

Мы используем один массив под названием кэш для хранения результатов n состояний. Следовательно, размер массива равен n. Поэтому сложность пространства есть O(n).

DP как компромисс пространство-время

Динамическое программирование использует пространство для более быстрого решения проблемы. В этой задаче мы используем O(n) пространство для решения проблемы O(n) время. Поэтому мы обмениваем пространство на скорость/время. Поэтому его точно называют Компромисс пространство-время.

Подведению

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

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

Если вам нравится эта публикация, поддержите ее, похлопав в ладоши? (вы можете достичь 50) и следите за мной здесь на Medium ✌️. Вы можете связаться со мной в LinkedIn. Вы также можете следить за мной на Github.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *