Бағдарламалаудың динамикалық негіздері


Күрделілік дәрежесі оңай
Жиі кіреді Infosys MAQ
Динамикалық бағдарламалау теория

Динамикалық бағдарламалау негіздерінде біз DP негіздерін және оның ашкөздік әдісі, Бөлу және жаулап алу мен рекурсиядан айырмашылығын қарастырамыз.

Динамикалық бағдарламалау - бұл рекурсия, бөлу және жаулап алу сияқты тәсіл. Ол проблеманы ішкі проблемаларға бөледі. Бөлу, бағындыру және рекурсия сияқты бұл ішкі проблемаларды өз бетінше шешудің орнына, алдыңғы есепшоттардың нәтижелерін ұқсас есептеулер үшін пайдаланады, оларды қабаттасып тұрған проблема деп те атайды.

Ол бағдарламаларды оңтайландыру үшін қолданылады. Ол бұрын есептелген нәтижелерді қолданған кезде, оның экспоненциалды уақыттық күрделілігін пайдаланып, көпмүшеге дейін төмендетуге болады. Мысалы - Шіркін сандардың рекурсивті шешімінің уақыттық күрделілігі экспоненциалды, ал DP шешімінің сызықтық.

DP кейбір негізгі проблемалары

  • Шіркін сандар проблемасы
  • Монета ауыстыру
  • Фибоначчи сандары
  • Қоңырау нөмірлері проблемасы
  • Ханой мұнарасы
  • Қоңырау нөмірлері
  • Рюкзак мәселесі

Динамикалық бағдарламалау (DP) қарсы ашкөздік әдісі

DP-де әр қадам оңтайлы шешім алу үшін қазіргі және алдыңғы шешімдерді ескере отырып шешімді бағалайды. Алайда, ашкөз алгоритмде біз тек қазіргі жағдайды ескере отырып, ең жақсы нұсқаны таңдаймыз.

Әдетте ашкөздік әдістері DP-ге қарағанда жылдамырақ, сонымен бірге жадында тиімді, өйткені ол болашақта пайдалану үшін бұрын есептелген мәндерді сақтамайды, бұл оңтайлы шешімге кепілдік бермейді.

Динамикалық бағдарламалау (DP) vs Divide & Conquer Method

Бөлу және жеңу кезінде біз проблеманы ішкі проблемаларға бөлеміз және әр ішкі проблеманы өз бетімізше шешеміз. Алайда, DP-де есептерді өз бетінше шешуден гөрі, біз бұрын алынған нәтижелерді жаңа есептеулер үшін қолданамыз. Басқаша айтқанда, біз бөлу және жеңу + есте сақтау = жоғарыдан төмен динамикалық тәсіл деп айтуға болады.

(Есте сақтау дегеніміз, бұрынғы есептеулерді қайта-қайта сол проблемалардың есептелуіне жол бермеу үшін хэш-картада жалпы есептелген нәтижелерді сақтау әдістемесі).

Динамикалық бағдарламалау (DP) және рекурсия әдісі

DP қайта есептеуді болдырмау үшін болашақта қайтадан қажет болған жағдайда оларды пайдалану үшін бұрын есептелген шешімдерді сақтайды. Алайда, рекурсия кезінде мәндерді сақтамайтындықтан, қажетсіз қайта есептеу мүмкіндігі бар.

Рекурсия есептерді бірнеше рет қайта есептеуге әкеледі, сондықтан мұндай жағдайларда рекурсияның уақыттық күрделілігі DP шешіміне қарағанда әрқашан үлкен болады.

Бұл мақалада біз туралы Динамикалық бағдарламалау негіздері. Келесі мақалаларда біз DP-ге қатысты кейбір негізгі мәселелерді қарастырамыз.

анықтамалық Сұхбат сұрақтары