динамическое программирование
Oct. 29th, 2018 03:34 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sab123Как-то вот подход динамического программирования прошел мимо меня. Мне про него запомнилась только статья из "Юного техника", от которого у меня осталось ощущение, что это такой перебор вариантов. Но мне продолжают встречаться упоминания, так что я удосужился наконец-то поинтересоваться.
Выяснилось, что эта хрень по сути - рекурсия с мемоизацией. Ну, и перебор вариантов в ней может присутствовать, да, но необязательно. В частности, вычисление чисел Фибоначчи через рекурсию с мемоизацией тоже записывают в динамическое программирование, хоть и никакого перебора там нет. Такую хрень я уже делал, не зная, что это динамическое программирование.
Но это, видимо, более современный подход. В классическом подходе, который видимо и излагался в "Юном Технике", все пространство аргументов сначала упорядочивается каким-то образом, чтобы каждое решение для каждого аргумента могло зависеть только от решений с аргументами, идущими до него в порядке, а потом тупо хреначат и вычисляют лучшие решения для каждого аргумента по порядку, пока не дойдут до заданного.
Если оказывается, что все или почти все аргументы будут так или иначе использованы в рекурсии, то классический подход ничем не хуже рекурсии, а даже наоборот лучше, поскольку не требует глубокого стека. Так что, блин, всего около 30 лет прошло, и achievement unlocked, познал динамическое программирование.
Забавно, кстати, что тот "Юный Техник" вроде как ссылался на Колмогорова, а на самом деле эту хрень изобрел некто Ричард Беллман.
Выяснилось, что эта хрень по сути - рекурсия с мемоизацией. Ну, и перебор вариантов в ней может присутствовать, да, но необязательно. В частности, вычисление чисел Фибоначчи через рекурсию с мемоизацией тоже записывают в динамическое программирование, хоть и никакого перебора там нет. Такую хрень я уже делал, не зная, что это динамическое программирование.
Но это, видимо, более современный подход. В классическом подходе, который видимо и излагался в "Юном Технике", все пространство аргументов сначала упорядочивается каким-то образом, чтобы каждое решение для каждого аргумента могло зависеть только от решений с аргументами, идущими до него в порядке, а потом тупо хреначат и вычисляют лучшие решения для каждого аргумента по порядку, пока не дойдут до заданного.
Если оказывается, что все или почти все аргументы будут так или иначе использованы в рекурсии, то классический подход ничем не хуже рекурсии, а даже наоборот лучше, поскольку не требует глубокого стека. Так что, блин, всего около 30 лет прошло, и achievement unlocked, познал динамическое программирование.
Забавно, кстати, что тот "Юный Техник" вроде как ссылался на Колмогорова, а на самом деле эту хрень изобрел некто Ричард Беллман.
Почти
Date: 2018-10-29 11:23 pm (UTC)А так вообще-то динамическое программирование это спортивный навык, вроде умения прыгать с шестом. За пределами олимпиад и прочих соревнований не очень часто нужен.
Re: Почти
Date: 2018-10-30 12:15 am (UTC)А так - да, оказалось, что то же самое делал, не зная, что это оно, да и то очень редко. Собственно, с чего вся началось-то - люди на интервью пытаются решать задачи с использованием этого динамического прогоаммирования, но во-первых это подход неправильный для моих задач, во-вторых оказывается, что они не могут вспомнить, как это самое динамическое программирование делать.
Re: Почти
Date: 2018-10-30 01:08 am (UTC)