بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین Educational Codeforces Round 20

»    مسأله‌ی Encrypted SMS

»    ویدئوهای آموزشی کلاس Programming Challenges  

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
روش برنامه‌نویسی پویا - الگوریتمستان
الگوریتمستان
7914.335.00
  »  

       

آشنایی با روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا، برنامه‌سازی پویا - Dynamic Programming)  به عنوان یکی از روش‌های پر کاربرد طراحی الگوریتم برای حل بهینه‌ی مسائل با مثالی از محاسبه‌ی دنباله‌ی فیبوناچی

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «روش برنامه نویسی پویا» تیر ماه 1387 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


آنچه در این نوشته می‌خوانید:

یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا، برنامه‌سازی پویا - Dynamic Programming)  است. این روش همچون روش تقسیم و حل (Divide and Conquer)  بر پایه‌ی تقسیم مسأله بر زیرمسأله‌ها کار می‌کند. اما تفاوت‌های چشم‌گیری با آن دارد.

    زمانی که یک مسأله به دو یا چند زیرمسأله تقسیم می‌شود، دو حالت ممکن است پیش بیاید:

    1-  داده‌های زیرمسأله‌ها هیچ اشتراکی با هم نداشته و کاملا مستقل از هم هستند. نمونه‌ی چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجه حاصل از آن بخش اثری ندارند. معمولا روش تقسیم و حل برای چنین مسائلی کارآیی خوبی دارد.

    2-  داده‌های زیرمسأله وابسته به هم بوده و یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسأله‌ها هم‌پوشانی دارند. نمونه‌ی بارز چنین مسائلی محاسبه‌ی جمله‌ی n ام دنباله‌ی اعداد فیبوناچی است.

      

دنباله‌ی اعداد فیبوناچی (فیبوناتچی)

  [بازگشت به فهرست]

دنباله‌ی اعداد فیبوناچی (Fibonacci) یکی از دنباله‌های عددی مشهور ریاضیات با تعریف بازگشتی زیر است:

      

\[F(n) = F(n - 1) + F(n - 2) \qquad n > 2 \qquad, \qquad F(1) = F(2) = 1 \]

      

    محاسبه‌ی جمله‌ی n ام دنباله به محاسبه‌ی دو جمله‌ی قبلی آن نیاز دارد. پس می‌توان گفت محاسبه‌ی $ F(n - 1) $  و $ F(n - 2) $  دو زیرمسأله برای مسأله‌ی اصلی هستند. اما در عین حال این دو زیرمسأله از هم مستقل نیستند. برای محاسبه‌ی $ F(n - 1) $  بر اساس رابطه‌ی بالا باید داشته باشیم:

      

\[F(n - 1) = F(n - 2) + F(n - 3) \]

      

    که نشان می‌دهد خود $ F(n - 1) $  وابسته به $ F(n - 2) $  است.

    اگر این مسأله را به روش تقسیم و حل - که ساده‌ترین روش است - حل کنیم:

int fibo(int n){
  if(n > 2)
    return fibo(n - 1) + fibo(n - 2);
  return 1;
}

      

    تابع fibo  مقدار n  را دریافت کرده و به صورت بازگشتی و بر اساس رابطه‌ی ذکر شده، جمله‌ی n ام دنباله‌ی فیبوناچی را محاسبه می‌کند. حال درخت فراخوانی‌های بازگشتی تابع را به ازای n = 7  رسم می‌کنیم:

      

      

درخت فراخوانی بازگشتی تابع فیبوناچی

      

    هر گره درخت، فراخوانی تابع را با مقدار داخل آن نشان می‌دهد. برای محاسبه‌ی جمله‌ی هفتم دنباله‌ی فیبوناچی تابع fibo  به صورت (fibo(7  فراخوانی می‌شود که آن هم (fibo(6  و (fibo(5  را فراخوانی می‌کند و الی آخر. همانطور که مشاهده می‌کنید، برای محاسبه‌ی این جمله، (fibo(7  یک بار، (fibo(6  یک بار، (fibo(5  دو بار، (fibo(4  سه بار، (fibo(3  پنج بار، (fibo(2  هشت بار، (fibo(1  پنج بار و روی هم رفته تابع fibo  بیست و پنج بار فراخوانی می‌شود.

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

1  1  2(= 1 + 1)

1  1  2  3(= 2 + 1)

1  1  2  3  5(= 3 + 2)

1  1  2  3  5  8(= 5 + 3)

1  1  2  3  5  8  13(= 8 + 5)

  

    و به این ترتیب جمله‌ی هفتم دنباله تنها با پنج محاسبه‌ی ساده به دست می‌آید. در حالت کلی با استفاده از این روش تنها به n - 2  عمل جمع نیاز است که نشان از الگوریتمی با مرتبه‌ی خطی دارد. در حالی که می‌توان ثابت کرد در حالت اول تعداد کل فراخوانی‌های بازگشتی تابع از مرتبه‌ی نمایی است. دلیل اختلاف این دو عدد در این است که در حالت دوم، هر جمله‌ی دنباله فقط و فقط یک بار محاسبه می‌شود. این همان روش برنامه‌نویسی پویا است.

    در برنامه‌نویسی پویا مسأله به صورت جزء به کل حل می‌شود. یعنی ابتدا زیرمسائل خرد حل شده و نتیجه‌ی آنها در مکانی دخیره می‌شود. سپس به سمت زیرمسائل کلی‌تر رفته و با استفاده از داده‌های از پیش محاسبه شده، آنها نیز حل می‌شوند. در مورد دنباله‌ی فیبوناچی می‌توان نوشت:

      

int fibo(int n){
  int f[MAX], i;
  f[1] = f[2] = 1;
  for(i = 3 ; i <= n ; i++)
    f[i] = f[i - 1] + f[i - 2];
  return f[n];
}

  

    در این روش ما جملات دنباله‌ها را پس از محاسبه در یک آرایه ذخیره می‌کنیم. برای این کار به جای حرکت از کل به جزء (یعنی از n  به 1  که در روش تقسیم و حل استفاده می‌شود)، از جزء به سمت کل حرکت می‌کنیم. هر جمله‌ی دنباله تنها به دو جمله‌ی قبل خود نیاز دارد که با حرکت جزء به کل قبلا محاسبه شده‌اند و نیاز به محاسبه‌ی مجدد آنها نیست. البته این کد را می‌توان ساده‌تر کرد:

      

int fibo(int n){
  int i, f1, f2, f3;
  f1 = f2 = 1;
  for(i = 3 ; i <= n ; i++){
    f3 = f1 + f2;
    f1 = f2;
    f2 = f3;
  }
  return f3;
10 }

  

    تحلیل این تابع ساده را به خود شما وا می‌گذارم.

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

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

    اصل بهینگی: اصل بهینگی یعنی حل مسأله به صورت بهینه، حاوی حل بهینه‌ی تمامی زیرمسائل آن نیز باشد.

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


این نوشته آخرین بار در تاریخ پنجشنبه، ۱۶ دی ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016  سایت تهران
        آشنایی با الگوریتم فلوید-وارشال برای یافتن کوتاهترین مسیرهای گراف با قطعه کد نمونه به زبان برنامه‌نویسی ++C
        بررسی مسأله‌ی اعداد اردوش (Erdos Numbers)  یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی
        بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
        بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها
        معرفی کتاب Programming Challenges  برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی یا معرفی پیوند دانلود فایل‌های صوتی، تصویری و اسلایدهای کلاس درس نویسنده
        معرفی کتاب Introduction to Algorithms: A Creative Approach  
        معرفی کتاب Art of Programming Contest  برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود نسخه‌ی الکترونیکی
        معرفی کتاب Introduction to Algorithms ( ویراست سوم) به عنوان مرجع مباحث طراحی الگوریتم‌ها و ساختمان داده‌ها
        بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه‌ی دترمینان ماتریس مربعی و پیچیده‌گی زمانی آنها
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» الف

دوشنبه، ۴ مرداد ماه ۱۳۹۵، ساعت ۲۰:۳۴
سلام عالی بود از این الگوریتم برای مسیر یابی دو نقطه متحرک در مسیریابی ربات هم می شود استفاده کرد ؟


دوشنبه، ۴ مرداد ماه ۱۳۹۵، ساعت ۲۱:۳۲
مسعود:
خیلی ممنون.
بله، از برنامه‌نویسی پویا هم برای مسیریابی می‌شه استفاده کرد. چند الگوریتم مسیریابی همین سایت بحث شدن.

» فاطمه

جمعه، ۲۰ آذر ماه ۱۳۹۴، ساعت ۱۳:۳۷
من ی سوال داشتم ممنون میشم اگه جواب بدید خیلی حیاتی هست برنامه که ضرب اعداد بهینه را پیاده سازی کند؟ ورودی:دو عدد بزرگ خروجی:حاصلضرب آن ها

» شهناز

سه‌شنبه، ۵ آبان ماه ۱۳۹۴، ساعت ۱۹:۳۱
عالی بود استفاده کردم .

» pmp

دوشنبه، ۶ بهمن ماه ۱۳۹۳، ساعت ۱۱:۵۵
سلام . مطلب کوتاه ولی مفید بود .ممنون

» مریم

سه‌شنبه، ۲۷ آبان ماه ۱۳۹۳، ساعت ۱۰:۴۷
سلام . مطلب کوتاه ولی مفید بود .ممنون

» صالح

جمعه، ۱۰ مرداد ماه ۱۳۹۳، ساعت ۱۷:۱۲
سلام به دوستان برنامه نویس.
درست میگن ی دست صدانداره،من به کمک دوستام تو آلگوریتمستان کلی موفقیت کسب کردم"خدا قوت الگوریتمستانیا"

» حسن

سه‌شنبه، ۱۴ خرداد ماه ۱۳۹۲، ساعت ۲۳:۰۲
خیلی عالی بود واقعا بدردم خورد

» مجید

یکشنبه، ۸ اردیبهشت ماه ۱۳۹۲، ساعت ۱۰:۵۱
خیلی کاربردی و عمیق بود
با تشکر

» سید جلال

شنبه، ۹ دی ماه ۱۳۹۱، ساعت ۱۸:۲۳
سلام لطفا سوالی قرار بدین که با سه روش تقسیم وغلبه و پویا و حریصانه حل بشه

» سمانه

پنجشنبه، ۹ آذر ماه ۱۳۹۱، ساعت ۲۰:۴۲
سلام واقعا عالی بود میشه لطف کنیدکدبرنامه ای که فاکتوریل یک عددصحیح رابوسیله حلقهfor محاسبه کند ،رابنویسید

» مونا

چهارشنبه، ۲۴ اسفند ماه ۱۳۹۰، ساعت ۱۲:۵۸
سلام. مطالب خوب و مفیدی رو راجع به مرتب سازی ها ارائه داده بودین. ضمن تشکر می خواستم اگه مقدوره اطلاعاتی را جع به کاربرد الگوریتم هایی مثل کوله پشتی، پویا و فروشنده دوره گرد ارائه بدین. اینکه کجاها این الگوریتم ها به کار می یان. من یه مطلبی خوندم که مثلا کوله پشتی توی سیستم عامل کاربرد داره. یا مثلا توی برش کالا. اما دقیقاً کارایی شون رو متوجه نشدم.
ممنون می شم اگه راجع به این مطالب هم اطلاعاتی درج کنید.

» هژیر

دوشنبه، ۲۸ آذر ماه ۱۳۹۰، ساعت ۱۰:۵۶
دوست عزیز مطالبی که بر روی سایت قرار می دهید هیچ سندست علمی ندارد . خواهشا از قرار دادن این مطالب بر روی وی سایت خودداری کنید . چون چند تا از آنها را که خواندم کاملا اشتباه بودند


دوشنبه، ۲۸ آذر ماه ۱۳۹۰، ساعت ۱۱:۳۷
مسعود:
هژیر عزیز
خوشحال می‌شم مطالبی رو که کاملا اشتباه هستن معرفی کنید. همینطور سندهایی که بر اساس اونها این مطالب اشتباه هستن. اگه واقعا اونطور باشه حتما نسبت به اصلاحشون اقدام می‌کنم. شما اولین نفری هستید که اینطور نظری رو مطرح می‌کنید.

» حامد

شنبه، ۲۰ فروردین ماه ۱۳۹۰، ساعت ۲۰:۴۸
لطفا اطلاعاتی هم در مورد سری لوکا
در سایت اضافه کنید و مطالب جدید در مورد
سری فیبوناچی اضافه کنید

» سروش

سه‌شنبه، ۲۸ اردیبهشت ماه ۱۳۸۹، ساعت ۱۹:۵۸
خيلي عالي بود