Агуулгыг алгасах

Динамик программчлалын танилцуулга

Динамик программчлалын мөн чанар нь давтан тооцооллоос зайлсхийх явдал юм. Динамик программчлалын бодлогуудыг ихэвчлэн рекурсээр байгалийн жамаар бодож болдог. Ийм тохиолдолд рекурсив шийдлийг бичээд, дараа нь давтагдах төлвүүдийг хайлтын хүснэгтэд хадгалах нь хамгийн хялбар. Энэ процессыг мемоизаци бүхий дээрээс доош динамик программчлал гэж нэрлэдэг. Үүнийг "memorization" (цээжлэх) биш, "memoization" (тэмдэглэлийн дэвтэрт бичиж байгаа мэт) гэж уншина.

Энэ процессын хамгийн энгийн, сонгодог жишээнүүдийн нэг бол Фибоначчийн дараалал юм. Түүний рекурсив томьёолол нь $f(n) = f(n-1) + f(n-2)$ бөгөөд энд $n \ge 2$, $f(0)=0$, $f(1)=1$. C++-д үүнийг дараах байдлаар илэрхийлнэ:

int f(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return f(n - 1) + f(n - 2);
}

Энэ рекурсив функцийн ажиллах хугацаа нь экспоненциал буюу ойролцоогоор $O(2^n)$, учир нь нэг функц дуудалт ($f(n)$) нь ижил хэмжээтэй 2 функц дуудалтад ($f(n-1)$ ба $f(n-2)$) хүргэдэг.

Фибоначчийг динамик программчлалаар (мемоизаци) хурдасгах

Манай рекурсив функц одоогоор Фибоначчийг экспоненциал хугацаанд боддог. Энэ нь бодлого хэт хэцүү болохоос өмнө бид зөвхөн жижиг оролтын утгуудыг зохицуулж чадна гэсэн үг. Жишээ нь $f(29)$ нь саяас дээш функц дуудалтад хүргэдэг!

Хурдыг нэмэгдүүлэхийн тулд дэд бодлогуудын тоо ердөө $O(n)$ гэдгийг бид анзаарна. Өөрөөр хэлбэл $f(n)$-г тооцоолохын тулд бид зөвхөн $f(n-1),f(n-2), \dots ,f(0)$-г мэдэх хэрэгтэй. Тиймээс эдгээр дэд бодлогуудыг дахин тооцоолохын оронд бид тэдгээрийг нэг удаа бодоод, дараа нь үр дүнг хайлтын хүснэгтэд хадгална. Дараагийн дуудалтууд энэ хайлтын хүснэгтийг ашиглаж, шууд үр дүн буцаах ба ингэснээр экспоненциал ажлыг арилгана!

Рекурсив дуудалт бүр утга тооцоологдсон эсэхийг харахын тулд хайлтын хүснэгттэй шалгана. Үүнийг $O(1)$ хугацаанд хийнэ. Хэрэв бид үүнийг өмнө нь тооцоолсон бол үр дүнг буцаана, эс бөгөөс функцийг хэвийн байдлаар тооцоолно. Нийт ажиллах хугацаа нь $O(n)$. Энэ бол манай өмнөх экспоненциал хугацааны алгоритмаас асар их сайжруулалт юм!

const int MAXN = 100;
bool found[MAXN];
int memo[MAXN];

int f(int n) {
    if (found[n]) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;

    found[n] = true;
    return memo[n] = f(n - 1) + f(n - 2);
}

Манай шинэ мемоизаци хийсэн рекурсив функцээр саяас дээш дуудалтад хүргэдэг байсан $f(29)$ одоо ердөө 57 дуудалтад хүргэх ба энэ нь бараг 20,000 дахин цөөн функц дуудалт юм! Инээдтэй нь бид одоо өгөгдлийн төрлөөрөө хязгаарлагдаж байна. $f(46)$ нь тэмдэгт 32-бит бүхэл тоонд багтах сүүлийн Фибоначчийн тоо юм.

Ихэвчлэн бид боломжтой бол төлвүүдийг массивт хадгалахыг оролддог, учир нь хайлтын хугацаа хамгийн бага нэмэлт зардлаар $O(1)$ байдаг. Гэвч илүү ерөнхийд нь бид төлвүүдийг дуртай аргаараа хадгалж болно. Бусад жишээнд хоёртын хайлтын мод (C++-д map) эсвэл хэш хүснэгт (C++-д unordered_map) орно.

Үүний жишээ дараах байдалтай байж болно:

unordered_map<int, int> memo;
int f(int n) {
    if (memo.count(n)) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;

    return memo[n] = f(n - 1) + f(n - 2);
}

Эсвэл үүнтэй адилаар:

map<int, int> memo;
int f(int n) {
    if (memo.count(n)) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;

    return memo[n] = f(n - 1) + f(n - 2);
}

Эдгээр хоёул нь ерөнхий мемоизаци хийсэн рекурсив функцийн хувьд массивд суурилсан хувилбараас бараг үргэлж удаан байна. Төлөв хадгалах эдгээр өөр аргууд нь голчлон вектор эсвэл тэмдэгт мөрийг төлвийн орон зайн хэсэг болгон хадгалахад ашигтай.

Мемоизаци хийсэн рекурсив функцийн ажиллах хугацааг энгийнээр шинжлэх арга нь:

$$\text{дэд бодлого тус бүрийн ажил} * \text{дэд бодлогын тоо}$$

Төлвүүдийг хадгалахад хоёртын хайлтын мод (C++-д map) ашиглах нь техникийн хувьд $O(n \log n)$ болно, учир нь хайлт ба оруулалт бүр $O(\log n)$ ажил шаардах ба $O(n)$ цор ганц дэд бодлоготой тул бид $O(n \log n)$ хугацаатай болно.

Энэ аргыг дээрээс доош гэж нэрлэдэг, учир нь бид функцийг асуулгын утгаар дуудаж болох ба тооцоо дээрээс (асуусан утга) доош (рекурсийн суурь тохиолдлууд) явж эхэлдэг бөгөөд замдаа мемоизацигаар товчлол хийдэг.

Доороос дээш динамик программчлал

Одоог хүртэл та зөвхөн мемоизаци бүхий дээрээс доош динамик программчлалыг үзсэн. Гэвч бид бодлогуудыг доороос дээш динамик программчлалаар ч бодож болно. Доороос дээш нь дээрээс доошийн яг эсрэг, та доороос (рекурсийн суурь тохиолдлууд) эхэлж, түүнийг улам олон утга руу өргөтгөнө.

Фибоначчийн тооны хувьд доороос дээш арга үүсгэхийн тулд бид суурь тохиолдлуудыг массивт эхлүүлнэ. Дараа нь бид массив дээр рекурсив тодорхойлолтыг зүгээр л ашиглана:

const int MAXN = 100;
int fib[MAXN];

int f(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) fib[i] = fib[i - 1] + fib[i - 2];

    return fib[n];
}

Мэдээж бичсэн байдлаараа энэ нь хоёр шалтгаанаар бага зэрэг утгагүй: Нэгдүгээрт, хэрэв бид функцийг нэгээс олон удаа дуудвал давтан ажил хийнэ. Хоёрдугаарт, одоогийн элементийг тооцоолохын тулд бид зөвхөн өмнөх хоёр утгыг ашиглах хэрэгтэй. Тиймээс бид санах ойгоо $O(n)$-ээс $O(1)$ болгон багасгаж болно.

$O(1)$ санах ой ашигладаг Фибоначчийн доороос дээш динамик программчлалын шийдлийн жишээ дараах байдалтай байж болно:

const int MAX_SAVE = 3;
int fib[MAX_SAVE];

int f(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i % MAX_SAVE] = fib[(i - 1) % MAX_SAVE] + fib[(i - 2) % MAX_SAVE];

    return fib[n % MAX_SAVE];
}

Бид тогтмолыг MAXN-ээс MAX_SAVE болгож өөрчилснийг анхаарна уу. Учир нь бидний хандах шаардлагатай элементийн нийт тоо ердөө 3. Энэ нь оролтын хэмжээгээр цаашид өсөхгүй бөгөөд тодорхойлолтоороо $O(1)$ санах ой юм. Түүнчлэн бид зөвхөн хэрэгтэй утгуудаа хадгалахын тулд түгээмэл арга (модулийн операторыг ашиглах)-ыг хэрэглэнэ.

Ингээд л боллоо. Энэ бол динамик программчлалын үндэс: Өмнө хийсэн ажлаа бүү давт.

Динамик программчлалд илүү сайжрах аргуудын нэг бол зарим сонгодог жишээг судлах явдал юм.

Динамик программчлалын сонгодог бодлогууд

Нэр Тайлбар/Жишээ
0-1 Үүргэвч Жин $w_i$, үнэ цэнэ $v_i$-тэй $N$ эд зүйл ба хамгийн их жин $W$ өгөгдсөн үед $\sum_{i=1}^{k} w_i \le W$ байхыг хангангаа $k$ хэмжээтэй ($1 \le k \le N$) эд зүйлийн дэд олонлог бүрийн хувьд хамгийн их $\sum_{i=1}^{k} v_i$ хэд вэ?
Дэд олонлогийн нийлбэр $N$ бүхэл тоо ба $T$ өгөгдсөн үед элементүүд нь $T$ болж нийлбэрлэгддэг өгөгдсөн олонлогийн дэд олонлог байгаа эсэхийг тодорхойл.
Хамгийн урт өсөх дэд дараалал (LIS) Танд $N$ бүхэл тоо агуулсан массив өгөгдсөн. Таны даалгавар бол массив дахь LIS буюу элемент бүр нь өмнөхөөсөө их байх дэд дарааллыг тодорхойлох явдал юм.
2D массив дахь замуудыг тоолох $N$ ба $M$ өгөгдсөн үед $(1,1)$-ээс $(N, M)$ хүртэлх бүх боломжит ялгаатай замыг тоол, энд алхам бүр нь $(i,j)$-ээс $(i+1,j)$ эсвэл $(i,j+1)$ руу байна.
Хамгийн урт нийтлэг дэд дараалал Танд $s$ ба $t$ тэмдэгт мөр өгөгдсөн. $s$ ба $t$ хоёуланд нь дэд дараалал болох хамгийн урт тэмдэгт мөрийн уртыг ол.
Чиглэлтэй циклгүй граф (DAG) дахь хамгийн урт зам Чиглэлтэй циклгүй граф (DAG) дахь хамгийн урт замыг олох.
Хамгийн урт палиндром дэд дараалал Өгөгдсөн тэмдэгт мөрийн хамгийн урт палиндром дэд дарааллыг (LPS) олох.
Саваа зүсэх $n$ нэгж урттай саваа ба cuts[i] нь зүсэлт хийх байрлалыг заах cuts бүхэл тоон массив өгөгдсөн. Нэг зүсэлтийн өртөг нь зүсэгдэх савааны урт юм. Зүсэлтүүдийн хамгийн бага нийт өртөг хэд вэ?
Засварын зай Хоёр тэмдэгт мөрийн хоорондын засварын зай гэдэг нь нэг тэмдэгт мөрийг нөгөө рүү хувиргахад шаардагдах үйлдлийн хамгийн бага тоо юм. Үйлдлүүд нь ["Нэмэх", "Хасах", "Солих"]

Холбогдох сэдвүүд

Мэдээж хамгийн чухал арга бол дасгал хийх явдал юм.

Дасгал бодлогууд

DP тэмцээнүүд