Кіріспе
Проблеманы оңтайландыру әдісі
Динамикалық бағдарламалау – математикалық оңтайландыру әдісі де, алгоритмдік үлгі де болып табылады. Бұл әдіс 1950 жылдары Ричард Беллманмен әзірленген және аэроғарыш өнеркәсібінен экономикаға дейін көптеген салаларда қолданыс тапқан. Екі жағдайда да ол күрделі мәселені рекурсивті түрде қарапайым қосалқы мәселелерге бөлу арқылы жеңілдетуге қатысты. Кейбір шешімдерді осылай бөлу мүмкін болмаса да, уақыт бойынша бірнеше нүктеге созылатын шешімдер көбінесе рекурсивті түрде бөлінеді. Сол сияқты, компьютер ғылымында, егер мәселені қосалқы мәселелерге бөліп, содан кейін қосалқы мәселелерге оңтайлы шешімдерді рекурсивті түрде табу арқылы оңтайлы шешуге болады, онда ол оңтайлы құрылымға ие деп айтылады. Егер қосалқы мәселелер үлкен мәселелердің ішінде рекурсивті түрде орналасқан болса, динамикалық бағдарламалау әдістерін қолдануға болады, онда үлкен мәселенің мәні мен қосалқы мәселелердің мәндері арасында байланыс болады. Оптимизация әдебиетінде бұл қатынас Беллман теңдеуі деп аталады.
Математикалық оңтайландыру
Математикалық оңтайландыру тұрғысынан алғанда, динамикалық бағдарламалау әдетте шешімді уақыт өте келе қабылданатын шешімдер тізбегіне бөліп, оны жеңілдетуді білдіреді. Бұл V1, V2, ..., Vn функцияларының тізбесін анықтау арқылы жүзеге асырылады, мұнда y аргументі 1-ден n-ге дейінгі уақыт аралығында жүйенің күйін көрсетеді. Vn(y) анықтамасы – соңғы n уақытында y күйінде алынған мән.
The definition of Vn(y) is the value obtained in state y at the last time n.
The values Vi at earlier times i = n −1, n − 2, , 2, 1 can be found by working backwards, using a recursive relationship called the Bellman equation. For i = 2, , n, Vi−1 at any state y is calculated from Vi by maximizing a simple function (usually the sum) of the gain from a decision at time i − 1 and the function Vi at the new state of the system if this decision is made. Since Vi has already been calculated for the needed states, the above operation yields Vi−1 for those states. Finally, V1 at the initial state of the system is the value of the optimal solution. The optimal values of the decision variables can be recovered, one by one, by tracking back the calculations already performed.
Алдыңғы уақыттардағы Vi мәндерін (i = n–1, n–2, ..., 2, 1) кері есептеу арқылы табуға болады, бұл үшін Белман теңдеуі деп аталатын рекурсивті қатынас қолданылады. i = 2, ..., n үшін, кез келген күйдегі y үшін Vi–1 мәні, i–1 уақытындағы шешімнен алынған пайданың қарапайым функциясын (әдетте, қосындысын) және егер бұл шешім қабылданса, жүйенің жаңа күйіндегі Vi функциясын максимизациялау арқылы есептеледі. Vi қажетті күйлер үшін есептелгендіктен, жоғарыда аталған операция осы күйлер үшін Vi–1 мәнін береді. Ақырында, жүйенің бастапқы күйіндегі V1 – бұл оңтайлы шешімнің мәні. Шешімдік айнымалылардың оңтайлы мәндерін жасалған есептеулерді кері оқып, біртіндеп табуға болады.
The definition of Vn(y) is the value obtained in state y at the last time n.
The values Vi at earlier times i = n −1, n − 2, , 2, 1 can be found by working backwards, using a recursive relationship called the Bellman equation. For i = 2, , n, Vi−1 at any state y is calculated from Vi by maximizing a simple function (usually the sum) of the gain from a decision at time i − 1 and the function Vi at the new state of the system if this decision is made. Since Vi has already been calculated for the needed states, the above operation yields Vi−1 for those states. Finally, V1 at the initial state of the system is the value of the optimal solution. The optimal values of the decision variables can be recovered, one by one, by tracking back the calculations already performed.
Компьютерлік ғылым
Динамикалық бағдарламалауды қолдану үшін проблеманың екі маңызды қасиеті болуы керек: оңтайлы құрылым және қайталама кіші проблемалар. Егер проблеманы бір-біріне тәуелсіз кіші проблемалардың оңтайлы шешімдерін біріктіру арқылы шешуге болады, онда бұл стратегия "бөліп талқандау" деп аталады. Қалай болғанда да, мұндай әдіс тек анықталған функция үшін ғана мүмкін. Мемоизация Wolfram Language сияқты, термин алмастыруға негізделген тілдерде қолжетімді дизайн үлгісі ретінде де кездеседі.
Биоинформатика
Динамикалық бағдарламалау биоинформатикада тізбектерді салыстыру, белоктарды бүктеу, РНК құрылымын болжау және белоктардың ДНК-мен байланысуы сияқты міндеттер үшін кеңінен қолданылады. Белоктардың ДНК-мен байланысуы үшін алғашқы динамикалық бағдарламалау алгоритмдерін 1970-ші жылдары АҚШ-та Чарльз ДеЛизи және КСРО-да Георгий Гурский мен Александр Заседателев дербес әзірледі. Соңғы кезде бұл алгоритмдер биоинформатика мен есептеу биологиясында, әсіресе нуклеосомалардың орналасуын және транскрипция факторларының байланысын зерттеуде кеңінен танымал болды.
Тізбелік сәйкестендіру
Генетикада тізбектерді салыстыру динамикалық бағдарламалауды қажет ететін маңызды қолданыс болып табылады.
Басқа параметрлеуді қолдана отырып, жылдам DP шешімі
Жоғарыдағы шешім DP шешімін жасау үшін уақыт қажет екенін ескеріңіз. Бұл, жоғарыдағы рекурренциядағы оптималдық мәнді екілік іздеу арқылы жақсартуға болады, өйткені -ның мәні -мен бірге өседі, ал -ның мәні -мен бірге кемиді, сондықтан -ның жергілікті минимумдық мәні жаһандық минимумдық мән болып табылады. Сондай-ақ, DP кестесіндегі әрбір жасуша үшін оптималдық мәнді сақтап, алдыңғы жасушаның мәніне сілтеме жасау арқылы әрбір жасуша үшін оптималдық мәнді тұрақты уақытта табуға болады, осылайша оны уақытқа дейін жақсартуға болады. Дегенмен, мәселенің басқа параметрлерін қамтитын одан да жылдам шешім бар: қабаттардың жалпы саны, яғни жұмыртқалар қанша қабаттан түсірілгенде сынғанын көрсетеді (жоғарыдағы мысал -ды алумен тең). жұмыртқаны сындыру үшін оны түсіру керек ең төменгі қабат болсын. - бұл сынақтар мен жұмыртқаларды қолдана отырып ажыратуға болатын мәндерінің ең көп саны болсын. Онда барлық үшін болады. - ең жақсы стратегия бойынша бірінші жұмыртқаны тастайтын қабат болсын. Егер бірінші жұмыртқа сынса, -дан -ға дейінгі қабаттарды ең көп дегенде сынақ және жұмыртқа арқылы ажыратуға болады. Егер бірінші жұмыртқа сынбаса, -дан -ға дейінгі қабаттарды сынақ және жұмыртқа арқылы ажыратуға болады. Сондықтан, теңдеуін шешу мәселесі -ның ең төменгі мәнін табуға тең, яғни оны өсу ретімен есептеуге болады, бұл уақыт алады. Осылайша, егер біз жағдайын жеке қарастырсақ, алгоритм уақыт алады. Бірақ рекурренттік қатынасты шешуге болады, нәтижесінде болады, оны барлық үшін сәйкестігін пайдаланып уақытта есептеуге болады. барлық үшін болғандықтан, -ны табу үшін екілік іздеуді қолдануға болады, нәтижесінде алгоритмі шығады.
Let be the total number of floors such that the eggs break when dropped from the th floor (The example above is equivalent to taking ). Let be the minimum floor from which the egg must be dropped to be broken. Let be the maximum number of values of that are distinguishable using tries and eggs. Then for all
Let be the floor from which the first egg is dropped in the optimal strategy. If the first egg broke, is from to and distinguishable using at most tries and eggs. If the first egg did not break, is from to and distinguishable using tries and eggs. Therefore,
Then the problem is equivalent to finding the minimum such that
To do so, we could compute in order of increasing , which would take time. Thus, if we separately handle the case of , the algorithm would take time. But the recurrence relation can in fact be solved, giving , which can be computed in time using the identity for all
Since for all , we can binary search on to find , giving an algorithm.