پرش به محتویات

بهینه‌سازی Knuth

بهینه‌سازی Knuth، که با نام Knuth-Yao Speedup نیز شناخته می‌شود، حالت خاصی از برنامه‌نویسی پویا روی بازه‌ها است که می‌تواند پیچیدگی زمانی راه‌حل‌ها را به اندازه یک ضریب خطی، از $O(n^3)$ برای برنامه‌نویسی پویای بازه‌ای استاندارد به $O(n^2)$ کاهش دهد.

شرایط

این بهینه‌سازی (Speedup) برای انتقال‌هایی به شکل زیر اعمال می‌شود:

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

مشابه با برنامه‌نویسی پویای تقسیم و غلبه، فرض کنید $opt(i, j)$ مقداری از $k$ باشد که عبارت موجود در انتقال را کمینه می‌کند ($opt$ در ادامه این مقاله به عنوان «نقطه شکست بهینه» نامیده می‌شود). این بهینه‌سازی نیازمند برقراری شرط زیر است:

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

می‌توان نشان داد که این شرط زمانی برقرار است که تابع هزینه $C$ در شرایط $a \leq b \leq c \leq d$ صدق کند:

  1. $C(b, c) \leq C(a, d)$;

  2. $C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$ (نامساوی چهارضلعی یا Quadrangle Inequality [QI]).

این نتیجه در ادامه اثبات می‌شود.

الگوریتم

بیایید حالت‌های dp را به گونه‌ای پردازش کنیم که $dp(i, j-1)$ و $dp(i+1, j)$ را قبل از $dp(i, j)$ محاسبه کنیم و در حین این کار، $opt(i, j-1)$ و $opt(i+1, j)$ را نیز به دست آوریم. سپس برای محاسبه $opt(i, j)$، به جای آزمودن مقادیر $k$ از $i$ تا $j-1$، تنها لازم است مقادیر را از $opt(i, j-1)$ تا $opt(i+1, j)$ بررسی کنیم. برای پردازش زوج‌های $(i,j)$ با این ترتیب، کافی است از حلقه‌های for تودرتو استفاده کنیم که در آن $i$ از مقدار بیشینه به کمینه و $j$ از $i+1$ تا مقدار بیشینه حرکت می‌کند.

پیاده‌سازی عمومی

اگرچه پیاده‌سازی‌ها متفاوت است، در اینجا یک مثال نسبتاً عمومی آورده شده است. ساختار کد تقریباً با برنامه‌نویسی پویای بازه‌ای (Range DP) یکسان است.

int solve() {
    int N;
    ... // خواندن N و ورودی
    int dp[N][N], opt[N][N];

    auto C = [&](int i, int j) {
        ... // پیاده‌سازی تابع هزینه C.
    };

    for (int i = 0; i < N; i++) {
        opt[i][i] = i;
        ... // مقداردهی اولیه dp[i][i] بر اساس مسئله
    }

    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];
}

پیچیدگی

پیچیدگی الگوریتم را می‌توان با جمع زیر تخمین زد:

$$ \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), $$

به جای $O(n^3)$ که در صورت استفاده از یک برنامه‌نویسی پویای بازه‌ای معمولی به دست می‌آمد.

در عمل

رایج‌ترین کاربرد بهینه‌سازی Knuth در برنامه‌نویسی پویای بازه‌ای (Range 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)$ نیز در نامساوی چهارضلعی صدق می‌کند، به شرطی که شرایط مسئله برقرار باشند.

اثبات

اثبات این لم از استقرای قوی استفاده می‌کند. این اثبات از مقاله Efficient Dynamic Programming Using Quadrangle Inequalities، نوشته F. Frances Yao که بهینه‌سازی Knuth-Yao Speedup را معرفی کرد، گرفته شده است (این گزاره خاص، لم 2.1 در آن مقاله است). ایده اصلی، استقرا بر روی طول $l = d - a$ است. حالت $l = 1$ بدیهی است. برای $l > 1$ دو حالت را در نظر می‌گیریم:

  1. $b = c$
    نامساوی به $dp(a, b) + dp(b, d) \leq dp(a, d)$ کاهش می‌یابد (این فرض می‌کند که $dp(i, i) = 0$ برای تمام $i$ها، که در تمام مسائلی که از این بهینه‌سازی استفاده می‌کنند، صادق است). فرض کنید $opt(a,d) = z$.

    • اگر $z < b$ باشد،
      توجه داشته باشید که

      $$ 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)$. ترکیب این دو واقعیت با نامساوی بالا، نتیجه مطلوب را به دست می‌دهد.

    • اگر $z \geq b$ باشد، اثبات این حالت متقارن با حالت قبلی است.

  2. $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). $$

      با استفاده از QI روی $C$ و روی حالت dp برای اندیس‌های $z+1 \leq y+1 \leq c \leq d$ (از فرض استقرا)، نتیجه مطلوب به دست می‌آید.

    • اگر $z > y$ باشد، اثبات این حالت متقارن با حالت قبلی است.

این، اثبات لم را کامل می‌کند.

اکنون، ساختار زیر را در نظر بگیرید. دو اندیس $i \leq p \leq q < j$ داریم. قرار می‌دهیم $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)$ است، که نیمه اول نامساوی را اثبات می‌کند.

اکنون، با استفاده از QI روی اندیس‌های $p+1 \leq q+1 \leq j-1 \leq j$، داریم:

$$\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)$ نشان داد.

این اثبات را کامل می‌کند.

مسائل تمرینی

مراجع