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

مقدمه‌ای بر برنامه‌نویسی پویا (Dynamic Programming)

جوهر اصلی برنامه‌نویسی پویا، پرهیز از محاسبات تکراری است. اغلب، مسائل برنامه‌نویسی پویا به طور طبیعی با بازگشت (recursion) قابل حل هستند. در چنین مواردی، ساده‌ترین راه این است که ابتدا راه‌حل بازگشتی را بنویسیم، سپس حالت‌های تکراری را در یک جدول جستجو (lookup table) ذخیره کنیم. این فرآیند به عنوان برنامه‌نویسی پویای بالا به پایین (top-down) با memoization شناخته می‌شود. این کلمه «memoization» تلفظ می‌شود (شبیه نوشتن در یک دفترچه یادداشت یا memo pad) و نه memorization (به معنی به خاطر سپردن).

یکی از اساسی‌ترین و کلاسیک‌ترین مثال‌های این فرآیند، دنباله فیبوناچی است. فرمول بازگشتی آن به صورت $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);
}

زمان اجرای این تابع بازگشتی به صورت نمایی (exponential) است - تقریباً $O(2^n)$، زیرا یک فراخوانی تابع ($f(n)$) منجر به ۲ فراخوانی تابع با اندازه‌ای مشابه ($f(n-1)$ و $f(n-2)$) می‌شود.

سرعت بخشیدن به فیبوناچی با برنامه‌نویسی پویا (Memoization)

تابع بازگشتی فعلی ما فیبوناچی را در زمان نمایی حل می‌کند. این بدان معناست که ما فقط می‌توانیم مقادیر ورودی کوچک را پردازش کنیم قبل از اینکه مسئله بیش از حد دشوار شود. به عنوان مثال، $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);
}

با تابع بازگشتی جدید ما که از memoization استفاده می‌کند، محاسبه $f(29)$ که قبلاً منجر به بیش از ۱ میلیون فراخوانی می‌شد، اکنون فقط ۵۷ فراخوانی دارد، یعنی تقریباً ۲۰٬۰۰۰ برابر فراخوانی تابع کمتر! جالب اینجاست که اکنون ما با نوع داده خود محدود شده‌ایم. $f(46)$ آخرین عدد فیبوناچی است که می‌تواند در یک عدد صحیح ۳۲ بیتی علامت‌دار (signed 32-bit integer) جای گیرد.

معمولاً، در صورت امکان، سعی می‌کنیم حالت‌ها را در آرایه‌ها ذخیره کنیم، زیرا زمان جستجو با کمترین سربار $O(1)$ است. با این حال، به طور کلی‌تر، می‌توانیم حالت‌ها را به هر روشی که دوست داریم ذخیره کنیم. مثال‌های دیگر شامل درخت‌های جستجوی دودویی (map در C++) یا جداول هش (unordered_map در C++) است.

یک مثال از این ممکن است به این صورت باشد:

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

هر دوی این روش‌ها تقریباً همیشه برای یک تابع بازگشتی عمومی با memoization کندتر از نسخه مبتنی بر آرایه خواهند بود. این روش‌های جایگزین برای ذخیره حالت عمدتاً زمانی مفید هستند که vector یا string به عنوان بخشی از فضای حالت ذخیره می‌شوند.

روش غیرتخصصی تحلیل زمان اجرای یک تابع بازگشتی با memoization به این صورت است:

$$\text{کار برای هر زیرمسئله} * \text{تعداد زیرمسئله‌ها}$$

استفاده از یک درخت جستجوی دودویی (map در C++) برای ذخیره حالت‌ها از نظر فنی منجر به زمان اجرای $O(n \log n)$ می‌شود، زیرا هر جستجو و درج $O(\log n)$ کار می‌برد و با $O(n)$ زیرمسئله منحصربه‌فرد، ما زمان $O(n \log n)$ را خواهیم داشت.

این رویکرد بالا به پایین (top-down) نامیده می‌شود، زیرا می‌توانیم تابع را با یک مقدار پرس‌وجو فراخوانی کنیم و محاسبه از بالا (مقدار پرس‌وجو شده) به سمت پایین (حالت‌های پایه بازگشتی) شروع می‌شود و در طول مسیر از طریق memoization میان‌بر می‌زند.

برنامه‌نویسی پویای پایین به بالا (Bottom-up)

تا به حال فقط برنامه‌نویسی پویای بالا به پایین با memoization را دیده‌اید. با این حال، ما می‌توانیم مسائل را با برنامه‌نویسی پویای پایین به بالا نیز حل کنیم. پایین به بالا دقیقاً برعکس بالا به پایین است، شما از پایین (حالت‌های پایه بازگشتی) شروع می‌کنید و آن را به مقادیر بیشتر و بیشتری گسترش می‌دهید.

برای ایجاد یک رویکرد پایین به بالا برای اعداد فیبوناچی، ما حالت‌های پایه را در یک آرایه مقداردهی اولیه می‌کنیم. سپس، به سادگی از تعریف بازگشتی روی آرایه استفاده می‌کنیم:

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 تغییر داده‌ایم. این به این دلیل است که تعداد کل عناصری که نیاز به دسترسی داریم فقط ۳ است. دیگر با اندازه ورودی مقیاس نمی‌شود و بنا به تعریف، حافظه $O(1)$ است. علاوه بر این، ما از یک ترفند رایج (استفاده از عملگر باقیمانده) استفاده می‌کنیم و فقط مقادیری را که نیاز داریم حفظ می‌کنیم.

تمام شد. این‌ها اصول اولیه برنامه‌نویسی پویا بودند: کاری را که قبلاً انجام داده‌اید، تکرار نکنید.

یکی از ترفندها برای بهتر شدن در برنامه‌نویسی پویا، مطالعه برخی از مثال‌های کلاسیک است.

مسائل کلاسیک برنامه‌نویسی پویا

نام توضیح/مثال
کوله‌پشتی صفر و یک (0-1 Knapsack) با داشتن $W$ ،$N$ و $N$ آیتم با وزن‌های $w_i$ و ارزش‌های $v_i$، حداکثر مقدار $\sum_{i=1}^{k} v_i$ برای هر زیرمجموعه از آیتم‌ها به اندازه $k$ ($1 \le k \le N$) چقدر است، به طوری که شرط $\sum_{i=1}^{k} w_i \le W$ برقرار باشد؟
مجموع زیرمجموعه (Subset Sum) با داشتن $N$ عدد صحیح و یک عدد $T$، مشخص کنید آیا زیرمجموعه‌ای از مجموعه داده شده وجود دارد که مجموع اعضای آن برابر با $T$ باشد.
طولانی‌ترین زیردنباله افزایشی (LIS) یک آرایه شامل $N$ عدد صحیح به شما داده شده است. وظیفه شما تعیین LIS در آرایه است، یعنی زیردنباله‌ای که در آن هر عنصر از عنصر قبلی خود بزرگ‌تر باشد.
شمردن مسیرها در یک آرایه دو بعدی با داشتن $N$ و $M$، تمام مسیرهای متمایز ممکن از $(1,1)$ به $(N, M)$ را بشمارید، به طوری که هر گام یا از $(i,j)$ به $(i+1,j)$ یا از $(i,j)$ به $(i,j+1)$ باشد.
طولانی‌ترین زیردنباله مشترک رشته‌های $s$ و $t$ به شما داده شده‌اند. طول طولانی‌ترین رشته‌ای را که زیردنباله‌ای از هر دو رشته $s$ و $t$ باشد، پیدا کنید.
طولانی‌ترین مسیر در یک گراف جهت‌دار غیرمدور (DAG) یافتن طولانی‌ترین مسیر در یک گراف جهت‌دار غیرمدور (DAG).
طولانی‌ترین زیردنباله پالیندروم یافتن طولانی‌ترین زیردنباله پالیندروم (LPS) از یک رشته داده شده.
برش میله یک میله به طول $n$ واحد و یک آرایه از اعداد صحیح به نام cuts داده شده است که cuts[i] موقعیتی را نشان می‌دهد که باید در آن برشی انجام دهید. هزینه یک برش برابر با طول میله‌ای است که برش داده می‌شود. حداقل هزینه کل برش‌ها چقدر است.
فاصله ویرایش (Edit Distance) فاصله ویرایش بین دو رشته، حداقل تعداد عملیات لازم برای تبدیل یک رشته به رشته دیگر است. عملیات‌ها عبارتند از: ["افزودن"، "حذف"، "جایگزینی"]

موضوعات مرتبط

  • برنامه‌نویسی پویا با بیت‌مسک (Bitmask)
  • برنامه‌نویسی پویا بر روی ارقام (Digit DP)
  • برنامه‌نویسی پویا روی درخت‌ها

البته، مهم‌ترین ترفند، تمرین کردن است.

مسائل تمرینی

مسابقات برنامه‌نویسی پویا