الگوریتم های برنامه نویسی پویا که هر برنامه نویسی باید بداند

معرفی

برنامه نویسی پویا تکنیکی است که به ما امکان می دهد مسائل پیچیده را به زیرمشکلات کوچکتر و قابل مدیریت تقسیم کنیم. این شامل حل مشکلات فرعی فقط یک بار و ذخیره نتایج در حافظه برای استفاده در آینده، به جای حل مکرر آنها است. این تکنیک به طور گسترده ای در علوم کامپیوتر استفاده می شود و می تواند برای طیف گسترده ای از مسائل از جمله مسائل بهینه سازی، زمان بندی، رشته ها و گراف ها استفاده شود.

در این مقاله، برخی از الگوریتم‌های ضروری برنامه‌نویسی پویا را که هر برنامه‌نویسی باید بداند، با مثال‌ها و تکه‌های کد بررسی می‌کنیم.

برنامه نویسی پویا چیست؟

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

مشکلات فرعی همپوشانی

یکی از ویژگی های کلیدی برنامه نویسی پویا، همپوشانی مشکلات فرعی است. این بدان معنی است که یک مشکل فرعی می تواند چندین بار در طول حل یک مشکل بزرگتر رخ دهد. به عنوان مثال، در دنباله فیبوناچی، محاسبه nامین عدد فیبوناچی شامل محاسبه اعداد فیبوناچی (n-1) و (n-2)امین است که خود نیاز به محاسبه (n-2)امین و (n-3)ام دارند. اعداد فیبوناچی و غیره.

زیرسازی بهینه

یکی دیگر از ویژگی های کلیدی برنامه نویسی پویا، زیرساخت بهینه است. این بدان معنی است که راه حل بهینه برای یک مسئله بزرگتر می تواند از راه حل های بهینه برای مسائل فرعی آن ساخته شود. به عنوان مثال، در مسئله کوله پشتی، راه حل بهینه برای یک کوله پشتی با سایز S و مجموعه ای از اقلام با وزن و مقادیر را می توان از راه حل های بهینه برای کوله های سایز S-1 و مجموعه ای از اقلام مشابه ساخت.

حفظ کردن

حافظه‌سازی تکنیکی است که برای اجرای برنامه‌نویسی پویا با ذخیره‌سازی نتایج فراخوانی‌های تابع گران قیمت و برگرداندن نتیجه ذخیره شده در حافظه پنهان هنگامی که همان ورودی‌ها دوباره تکرار می‌شوند، استفاده می‌شود. به عبارت دیگر، حافظه‌گذاری، ذخیره کردن نتایج فراخوانی‌های تابع گران قیمت است تا بتوانیم از محاسبات مکرر اجتناب کنیم.

در اینجا نمونه ای از یادداشت در عمل با استفاده از دنباله فیبوناچی آورده شده است:

pythonCopy codefib_cache = {}

def fib(n):
    if n in fib_cache:
        return fib_cache[n]
    if n <= 1:
        return n
    fib_cache[n] = fib(n-1) + fib(n-2)
    return fib_cache[n]

جدول بندی

جدول بندی تکنیک دیگری است که برای پیاده سازی برنامه نویسی پویا استفاده می شود، که شامل پر کردن جدول با نتایج مسائل فرعی به روشی از پایین به بالا است. به عبارت دیگر، به جای حل بازگشتی مسائل فرعی و ذخیره نتایج در حافظه، آنها را به صورت تکراری حل کرده و نتایج را در یک جدول ذخیره می کنیم.

در اینجا نمونه ای از جدول بندی در عمل با استفاده از دنباله فیبوناچی آورده شده است:

Copy code
def fib(n):
    if n <= 1
    # Initialize the table
    fib_table = [0, 1]

    # Fill up the table in a bottom-up manner
    for i in range(2, n+1):
        fib_table.append(fib_table[i-1] + fib_table[i-2])

    # Return the nth Fibonacci number
    return fib_table[n]

دنباله فیبوناچی

دنباله فیبوناچی یک مثال کلاسیک از یک مسئله است که با استفاده از برنامه نویسی پویا قابل حل است. دنباله فیبوناچی مجموعه‌ای از اعداد است که در آن هر عدد حاصل جمع دو عدد قبلی است که از 0 و 1 شروع می‌شود. ، 34 و غیره.

در اینجا نمونه ای از حل دنباله فیبوناچی با استفاده از برنامه نویسی پویا، با جدول بندی آورده شده است:

pythonCopy codedef fib(n):
    if n <= 1:
        return n

    # Initialize the table
    fib_table = [0, 1]

    # Fill up the table in a bottom-up manner
    for i in range(2, n+1):
        fib_table.append(fib_table[i-1] + fib_table[i-2])

    # Return the nth Fibonacci number
    return fib_table[n]

مشکل کوله پشتی

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

در اینجا مثالی از حل مسئله کوله پشتی با استفاده از برنامه نویسی پویا با جدول بندی آورده شده است:

pythonCopy codedef knapsack(W, wt, val, n):
    # Initialize the table
    K = [[0 for x in range(W+1)] for x in range(n+1)]

    # Build the table in a bottom-up manner
    for i in range(n+1):
        for w in range(W+1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]

    # Return the maximum value
    return K[n][W]

طولانی ترین دنباله متداول

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

در اینجا مثالی از حل طولانی‌ترین مسئله متداول زیر دنباله‌ای با استفاده از برنامه‌نویسی پویا، با جدول‌بندی آورده شده است:

pythonCopy codedef lcs(X, Y):
    m = len(X)
    n = len(Y)

    # Initialize the table
    L = [[0 for x in range(n+1)] for x in range(m+1)]

    # Build the table in a bottom-up manner
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])

    # Return the length of the longest common subsequence
    return L[m][n]

نتیجه

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

در این مقاله به سه مثال کلاسیک از الگوریتم های برنامه نویسی پویا پرداختیم: دنباله فیبوناچی، مسئله کوله پشتی و طولانی ترین مسئله متداول زیر دنباله. ما نشان دادیم که چگونه می توان هر یک از این مسائل را با استفاده از برنامه نویسی پویا با جدول بندی حل کرد.

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

نوشتن همیشه اشتیاق من بوده است و کمک و الهام بخشیدن به مردم برایم لذت بخش است. اگر سوالی دارید، در صورت تمایل با ما تماس بگیرید!

منو وصل کن توییتر، لینکدین و گیت هاب!

برای مقالات بیشتر مانند این از DEV من دیدن کنید.