Кнутын оновчлол¶

Кнут-Яогийн хурдасгалт гэж бас нэрлэгддэг Кнутын оновчлол нь интервал дээрх динамик программчлалын онцгой тохиолдол бөгөөд шийдлийн time complexity-г шугаман хүчин зүйлээр, стандарт интервал дээрх DP-ийн $O(n^3)$-ээс $O(n^2)$ хүртэл оновчтой болгодог.

Нөхцөлүүд¶

Хурдасгалтыг дараах хэлбэрийн шилжилтэд хэрэглэнэ

$$dp(i, j) = \min_{i \leq k < j} [ dp(i, k) + dp(k+1, j) + C(i, j) ].$$

Хуваа ба ялагтун DP-тэй адил, шилжилт дэх илэрхийллийг хамгийн бага болгох $k$-ийн хамгийн их утгыг $opt(i, j)$ гэе ($opt$-ийг цаашид энэ өгүүлэлд "оновчтой хуваах цэг" гэж нэрлэнэ). Оновчлол дараах биелэхийг шаардана:

$$opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j).$$

$C$ өртгийн функц $a \leq b \leq c \leq d$-ийн хувьд дараах нөхцөлийг хангах үед энэ нь үнэн болохыг бид харуулж болно:

$C(b, c) \leq C(a, d)$;
$C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$ (дөрвөн өнцөгтийн тэнцэтгэл биш [QI]).

Энэ үр дүнг доор баталсан.

Алгоритм¶

$dp(i, j)$-ээс өмнө $dp(i, j-1)$ ба $dp(i+1, j)$-г тооцоолж, ингэхдээ мөн $opt(i, j-1)$ ба $opt(i+1, j)$-г тооцоолох байдлаар dp төлвүүдийг боловсруулъя. Тэгвэл $opt(i, j)$-г тооцоолохын тулд $k$-ийн утгуудыг $i$-ээс $j-1$ хүртэл шалгахын оронд бид зөвхөн $opt(i, j-1)$-ээс $opt(i+1, j)$ хүртэл шалгахад хангалттай. $(i,j)$ хосуудыг энэ дарааллаар боловсруулахын тулд $i$ нь хамгийн их утгаас хамгийн бага руу, $j$ нь $i+1$-ээс хамгийн их утга руу явдаг үүрлэсэн for давталт ашиглахад хангалттай.

Generic implementation¶

Though implementation varies, here's a fairly generic example. The structure of the code is almost identical to that of Range DP.

int solve() {
    int N;
    ... // read N and input
    int dp[N][N], opt[N][N];

    auto C = [&](int i, int j) {
        ... // Implement cost function C.
    };

    for (int i = 0; i < N; i++) {
        opt[i][i] = i;
        ... // Initialize dp[i][i] according to the problem
    }

    for (int i = N-2; i >= 0; i--) {
        for (int j = i+1; j < N; j++) {
            int mn = INT_MAX;
            int cost = C(i, j);
            for (int k = opt[i][j-1]; k <= min(j-1, opt[i+1][j]); k++) {
                if (mn >= dp[i][k] + dp[k+1][j] + cost) {
                    opt[i][j] = k; 
                    mn = dp[i][k] + dp[k+1][j] + cost; 
                }
            }
            dp[i][j] = mn; 
        }
    }

    return dp[0][N-1];
}

Complexity¶

Алгоритмын complexity-г дараах нийлбэрээр үнэлж болно:

$$ \sum\limits_{i=1}^N \sum\limits_{j=i+1}^N [opt(i+1,j)-opt(i,j-1)] = \sum\limits_{i=1}^N \sum\limits_{j=i}^{N-1} [opt(i+1,j+1)-opt(i,j)]. $$

Таны харж байгаагаар энэ илэрхийлэл дэх гишүүдийн ихэнх нь бие биенээ хассан, зөвхөн $j=N-1$-тэй эерэг гишүүд ба $i=1$-тэй сөрөг гишүүдээс бусад нь. Тиймээс бүхэл нийлбэрийг

$$ \sum\limits_{k=1}^N[opt(k,N)-opt(1,k)] = O(n^2), $$

гэж үнэлж болох ба ердийн интервал дээрх DP ашиглавал байх байсан $O(n^3)$ биш юм.

Практикт¶

Кнутын оновчлолын хамгийн түгээмэл хэрэглээ нь өгөгдсөн шилжилттэй интервал дээрх DP юм. Цорын ганц бэрхшээл нь өртгийн функц өгөгдсөн нөхцөлийг хангадгийг батлах явдал юм. Хамгийн энгийн тохиолдол бол $C(i, j)$ өртгийн функц нь зүгээр л ямар нэг массивын (асуултаас хамааран) $S[i, i+1, ..., j]$ дэд массивын элементүүдийн нийлбэр байх үе юм. Гэвч тэдгээр нь заримдаа илүү төвөгтэй байж болно.

dp шилжилт ба өртгийн функц дээрх нөхцөлөөс илүү, энэ оновчлолын түлхүүр нь оновчтой хуваах цэг дээрх тэнцэтгэл биш гэдгийг анхаарна уу. Зарим бодлогод, жишээ нь оновчтой хоёртын хайлтын модны бодлогод (энэ нь дашрамд хэлэхэд энэ оновчлолыг боловсруулсан анхны бодлого), шилжилт ба өртгийн функцүүд бага илэрхий байх боловч $opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j)$-г батлах боломжтой хэвээр байгаа тул энэ оновчлолыг ашиглаж болно.

Зөв байдлын баталгаа¶

$C(i,j)$ нөхцөлийн хувьд энэ алгоритмын зөв байдлыг батлахын тулд өгөгдсөн нөхцөл хангагдсан гэж үзээд

$$ opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j) $$

-г батлахад хангалттай.

Лемм

Бодлогын нөхцөл хангагдсан үед $dp(i, j)$ мөн дөрвөн өнцөгтийн тэнцэтгэл бишийг хангана.

Баталгаа

Энэ леммийн баталгаа хүчтэй индукц ашигладаг. Үүнийг Кнут-Яогийн хурдасгалтыг танилцуулсан F. Frances Yao-ийн бичсэн Efficient Dynamic Programming Using Quadrangle Inequalities өгүүллээс авсан (энэ тодорхой батламж нь өгүүлэл дэх Лемм 2.1 юм). Санаа нь $l = d - a$ уртаар индукц хийх явдал юм. $l = 1$ тохиолдол тривиаль. $l > 1$-ийн хувьд 2 тохиолдлыг авч үзье:

$b = c$
Тэнцэтгэл биш нь $dp(a, b) + dp(b, d) \leq dp(a, d)$ болж буурна (Энэ нь бүх $i$-ийн хувьд $dp(i, i) = 0$ гэж үзэж байгаа бөгөөд энэ оновчлолыг ашигладаг бүх бодлогод тийм байдаг). $opt(a,d) = z$ гэе.
- Хэрэв $z < j$ бол,
  Анхаарна уу:
  
  $$ dp(a, b) \leq dp_{z}(a, b) = dp(a, z) + dp(z+1, b) + C(a, b). $$
  
  Тиймээс,
  
  $$ dp(a, b) + dp(b, d) \leq dp(a, z) + dp(z+1, b) + dp(b, d) + C(a, b) $$
  
  Индукцийн таамаглалаас $dp(z+1, b) + dp(b, d) \leq dp(z+1, d)$. Мөн $C(a, b) \leq C(a, d)$ гэж өгөгдсөн. Эдгээр 2 баримтыг дээрх тэнцэтгэл биштэй хослуулбал хайж буй үр дүн гарна.
- Хэрэв $z \geq j$ бол энэ тохиолдлын баталгаа өмнөх тохиолдолтой тэгш хэмтэй.
$b < c$
$opt(b, c) = z$ ба $opt(a, d) = y$ гэе.
- Хэрэв $z \leq y$ бол,
  
  $$ dp(a, c) + dp(b, d) \leq dp_{z}(a, c) + dp_{y}(b, d) $$
  
  энд
  
  $$ dp_{z}(a, c) + dp_{y}(b, d) = C(a, c) + C(b, d) + dp(a, z) + dp(z+1, c) + dp(b, y) + dp(y+1, d). $$
  
  $z+1 \leq y+1 \leq c \leq d$ индексүүдийн хувьд $C$ дээр ба dp төлөв дээр QI-г ашиглавал (индукцийн таамаглалаас) хайж буй үр дүн гарна.
- Хэрэв $z > y$ бол энэ тохиолдлын баталгаа өмнөх тохиолдолтой тэгш хэмтэй.

Энэ нь леммийн баталгааг дуусгана.

Одоо дараах тохиргоог авч үзье. Бидэнд $i \leq p \leq q < j$ гэсэн 2 индекс бий. $dp_{k} = C(i, j) + dp(i, k) + dp(k+1, j)$ гэж тавь.

Бид дараахыг харуулна гэж бодъё

$$ dp_{p}(i, j-1) \geq dp_{q}(i, j-1) \implies dp_{p}(i, j) \geq dp_{q}(i, j). $$

$q = opt(i, j-1)$ гэж тавибал тодорхойлолтоор $dp_{p}(i, j-1) \geq dp_{q}(i, j-1)$. Тиймээс бүх $i \leq p \leq q$-д тэнцэтгэл бишийг хэрэглэснээр бид $opt(i, j)$ нь наад зах нь $opt(i, j-1)$ хэмжээтэй гэж дүгнэж болох ба энэ нь тэнцэтгэл бишийн эхний хагасыг батална.

Одоо $p+1 \leq q+1 \leq j-1 \leq j$ зарим индексүүд дээр QI-г ашиглавал бид

$$\begin{align} &dp(p+1, j-1) + dp(q+1, j) ≤ dp(q+1, j-1) + dp(p+1, j) \\ \implies& (dp(i, p) + dp(p+1, j-1) + C(i, j-1)) + (dp(i, q) + dp(q+1, j) + C(i, j)) \\ \leq& (dp(i, q) + dp(q+1, j-1) + C(i, j-1)) + (dp(i, p) + dp(p+1, j) + C(i, j)) \\ \implies& dp_{p}(i, j-1) + dp_{q}(i, j) ≤ dp_{p}(i, j) + dp_{q}(i, j-1) \\ \implies& dp_{p}(i, j-1) - dp_{q}(i, j-1) ≤ dp_{p}(i, j) - dp_{q}(i, j) \\ \end{align}$$

Эцэст нь,

$$\begin{align} &dp_{p}(i, j-1) \geq dp_{q}(i, j-1) \\ &\implies 0 \leq dp_{p}(i, j-1) - dp_{q}(i, j-1) \leq dp_{p}(i, j) - dp_{q}(i, j) \\ &\implies dp_{p}(i, j) \geq dp_{q}(i, j) \end{align}$$

Энэ нь тэнцэтгэл бишийн эхний хэсэг буюу $opt(i, j-1) \leq opt(i, j)$-г батална. Хоёр дахь хэсэг $opt(i, j) \leq opt(i+1, j)$-г $dp(i, p) + dp(i+1, q) ≤ dp(i+1, p) + dp(i, q)$ тэнцэтгэл бишээс эхлэн ижил санаагаар харуулж болно.

Энэ нь баталгааг дуусгана.