Информатикада көйгөй бир нече жолу кайталануучу чакан көйгөйлөргө бөлүнсө же маселенин рекурсивдүү алгоритми ар дайым жаңыны жаратпай, бир эле чакан маселени кайра-кайра чечсе, маселенин бири-бирин кайталаган ички көйгөйлөрү бар деп айтылат. субпроблемалар.
Динамикалык программалоодо оптималдуу подструктура жана бири-бирин кайталаган чакан көйгөйлөр кандай?
Маселенин оптималдуу подструктуралык касиети бар, эгерде берилген маселенин оптималдуу чечими анын чакан проблемаларынын оптималдуу чечилишин колдонуу менен алынса. Динамикалык программалоо чечим табуу үчүн бул касиеттен пайдаланат.
Динамикалык программалоодо бири-бирин кайталаган чакан көйгөй эмнеде?
1) Кайталанган чакан көйгөйлөр:
Динамикалык программалоо негизинен бир эле чакан маселелердин чечилиши кайра-кайра талап кылынганда колдонулат. Динамикалык программалоодо подпроблемалардын эсептелген чечимдери таблицада сакталат, андыктан аларды кайра эсептөөнүн кереги жок.
Оптималдуу подструктура менен бири-бирин кайталаган субпроблемалардын ортосунда кандай айырма бар?
Оптималдуу подструктура n киргизүүнүн негизинде оптималдуу чечимди эсептеген эки ыкманын тең максаттуу мамилесин түшүнөм, ал эми Кайталануучу чакан көйгөйлөр киргизүү диапазону үчүн бардык чечимдерди максат кылат, мисалы, 1ден n.. Таяк кесүү көйгөйү сыяктуу көйгөй үчүн.
Бул Техникалардын кайсынысында чакан көйгөйлөрдүн бири-бирине дал келиши колдонулат?
Динамикалык программалоо – бул бири-бирин кайталаган ички көйгөйлөрү бар маселелерди чечүү ыкмасы. Мында биз келечекте кайра колдонуу үчүн бир жолу чечилген суб-проблеманын натыйжасын сактайбыз. Көйгөйдүн чакан чечимдерин сактоо ыкмасы эске салуу деп аталат.
