Динамикалык программалоо жана мемоизация
Мурда эсептелгенди эстеп калуу менен экспоненциалдык рекурсияны сызыктуу кодго айландырабыз
Негизги идея: Көптөгөн рекурсивдик чечимдер ошол эле кичи маселени миңдеген жолу кайра чечет. Динамикалык программалоо (ДП) — ар бир өзүнчө кичи маселени бир жолу чечип, жоопту кайра колдонуу тартиби. Мемоизация — жогорудан төмөн ыкма: аргументтер боюнча ачкычталган кэш кармайбыз. Табуляция — төмөндөн жогору ыкма: эң кичине кичи маселелерден баштап таблицаны толтурабыз. Бир эле рекурренция, эки багыт.
Аягында сиз төмөнкүлөрдү жасай аласыз:
- ДП колдонулаарынын эки белгисин таанууну: кайчылашкан кичи маселелер жана оптималдуу подструктура,
- жөнөкөй рекурсияны колжазма memo сөздүккө айландырууну,
- аргументтер хешделүүчү болгондо
functools.lru_cacheколдонууну, - жогорудан төмөн чечимди төмөндөн жогору табуляцияга кайра жазууну,
- мунун баарын Фибоначчи сандарына, тыйын майдалоого жана 0/1 рюкзак маселесине колдонууну,
- убакыт жана эстутум боюнча компромисстерди чынчыл баалоону.
Бул өнүккөн жыйынтыктоочу тема. Ал сиздин рекурсия, «О чоң» белгилөөсү, жабуулар (closure) жана мурунку декораторлор темасынан functools модулу менен эркин иштээриңизди болжолдойт. Биз аларды кайра үйрөтпөй, түздөн-түз таянабыз.
1. ДП качан колдонулат? Эки шарт
Динамикалык программалоо каалаган жай функцияга себе турган амал эмес. Бул маселеде төмөнкү эки касиеттин экөө тең болгондо гана пайда берүүчү оптималдаштыруу:
- Кайчылашкан кичи маселелер. Рекурсия ошол эле кичине нускага жоопту кайра-кайра сурайт. Эгер ар бир кичи маселе уникалдуу болсо, кэштей турган эч нерсе болбойт жана ДП бекер эле кошумча жүк болмок. (Кадимки «бөлүп башкар», мисалы, кошуп сорттоо, кайчылашпайт, ошондуктан аны мемоизациялоо эч нерсе бербейт.)
- Оптималдуу подструктура. Бүтүн маселенин оптималдуу жообу анын кичи маселелеринин оптималдуу жооптарынан курулат. Дал ушул кэштелген жыйынтыктарды кайра чыгарбай, туура бириктирүүгө мүмкүндүк берет.
Фибоначчи, эң кыска жолдор, тыйын майдалоо жана рюкзак — экөөнө тең дал келет. Өзүн кайчылашкан диапазондордо чакырган рекурренцияны көргөндө, ДП — керектүү курал.