الگوریتمستان

یادداشت‌های یک معلم علاقه‌مند به نوشتن از آنچه آموخته و یاد می‌دهد
 

  

✤  الگوریتم‌های برنامه‌نویسی پویا

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

یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا، برنامه‌سازی پویا - 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;

}

  

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

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

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

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

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

مسعود اقدسی فام

مسعود اقدسی فام هستم.

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

algs.ir/spxpfc3     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
نوشته‌ها از این دست
آخرین نوشته‌ها
       ✦   الگوریتم آنلاین
نوشته‌های پرمخاطب
       ✦   برج هانوی
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک (محرمانه):

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• mohsen
۱۶ مرداد ۱۳۸۷، ساعت ۱۱:۵۷

با سلام و تشكر از سايت خوب شما و اطلاعات جامعي كه در مورد الگوريتمها و بخصوص آموزش زبان هاي برنامه نويسي ميدهيد. خواستم اگر زحمتي نيست در مورد radic sort اگر درست نوشته باشم مقاله و يا مرجعي در سايت بگذاريد. با تشكر

مسعود اقدسی فام
۱۶ مرداد ۱۳۸۷، ساعت ۱۷:۵۳

محسن جان ممنون از لطفت. درآینده نزدیک انشاءالله در مورد Radix Sort هم مطلب خواهیم داشت.

• مهدی عباسپور شاهمرسی
۱۶ مرداد ۱۳۸۷، ساعت ۲۰:۱۴

سلام مسعود جان . . .

مثل همیشه عالی مختصر و مفید .

مسعود اقدسی فام
۱۶ مرداد ۱۳۸۷، ساعت ۲۲:۳۹

مخلصیم مهدی جان. منتظر مطالب قشنگ شما هم هستیم.

• hossein
۱۷ مرداد ۱۳۸۷، ساعت ۰۹:۳۸

بهنام خدا

سلام دوست  عزیز از وبلاگ زیبای  شما دیدن کردم لطفاُ من رو هم از مطالب زیبات بی نسیب نکن

• leily
۱۷ مرداد ۱۳۸۷، ساعت ۱۲:۲۶

سلام امیدوارم حالتون خوب باشه. میخواستم بابت مطلب خوبتون تشکر کنم. و یه درخواست هم دارم . در مورد مدارهای هامیلتونی هم می شه مقاله بدید. ممنون می شم.

• Soroush_farda
۱۹ مرداد ۱۳۸۷، ساعت ۰۹:۱۳

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

مسعود اقدسی فام
۱۹ مرداد ۱۳۸۷، ساعت ۰۹:۲۷

از لطف همه دوستان ممنونم.

• مرضیه
۲۳ دی ۱۳۸۷، ساعت ۲۰:۴۱

لطفا در صورت امکان و سریع خواهشا الگوریتم با روش تقسیم و حل برای حساب فاصله دو نقطه در فضا ارائه دهید.

•  رویا
۱۸ بهمن ۱۳۸۷، ساعت ۱۶:۲۷

سلام

با تشکر از مطالب خوبتون میخواستم بگم میشه لطفا چند تا کتاب درباره طراحی الگوریتم معرفی کنید یا لینک PDF رو بگذارید؟

• سروش
۲۸ اردیبهشت ۱۳۸۹، ساعت ۱۹:۵۸

خيلي عالي بود

• حامد
۲۰ فروردین ۱۳۹۰، ساعت ۲۰:۴۸

لطفا اطلاعاتی هم در مورد سری لوکا

در سایت اضافه کنید و مطالب جدید در مورد

سری فیبوناچی اضافه کنید

• هژیر
۲۸ آذر ۱۳۹۰، ساعت ۱۰:۵۶

دوست عزیز مطالبی که بر روی سایت قرار می دهید هیچ سندست علمی ندارد . خواهشا از قرار دادن این مطالب بر روی وی سایت خودداری کنید . چون چند تا از آنها را که خواندم کاملا اشتباه بودند

۲۸ آذر ۱۳۹۰، ساعت ۱۱:۳۷
• مسعود اقدسی فام

هژیر عزیز

خوشحال می‌شم مطالبی رو که کاملا اشتباه هستن معرفی کنید. همینطور سندهایی که بر اساس اونها این مطالب اشتباه هستن. اگه واقعا اونطور باشه حتما نسبت به اصلاحشون اقدام می‌کنم. شما اولین نفری هستید که اینطور نظری رو مطرح می‌کنید.

• مونا
۲۴ اسفند ۱۳۹۰، ساعت ۱۲:۵۸

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

ممنون می شم اگه راجع به این مطالب هم اطلاعاتی درج کنید.

• سمانه
۹ آذر ۱۳۹۱، ساعت ۲۰:۴۲

سلام واقعا عالی بود میشه لطف کنیدکدبرنامه ای که فاکتوریل یک عددصحیح رابوسیله حلقهforمحاسبه کند ،رابنویسید

• سید جلال
۹ دی ۱۳۹۱، ساعت ۱۸:۲۳

سلام لطفا سوالی قرار بدین که با سه روش تقسیم وغلبه و پویا و حریصانه حل بشه

• مجید
۸ اردیبهشت ۱۳۹۲، ساعت ۱۰:۵۱

خیلی کاربردی و عمیق بود

با تشکر

• حسن
۱۴ خرداد ۱۳۹۲، ساعت ۲۳:۰۲

خیلی عالی بود واقعا بدردم خورد

• صالح
۱۰ مرداد ۱۳۹۳، ساعت ۱۷:۱۲

سلام به دوستان برنامه نویس.

درست میگن ی دست صدانداره،من به کمک دوستام تو آلگوریتمستان کلی موفقیت کسب کردم"خدا قوت الگوریتمستانیا"

• مریم
۲۷ آبان ۱۳۹۳، ساعت ۱۰:۴۷

سلام . مطلب کوتاه ولی مفید بود .ممنون

• pmp
۶ بهمن ۱۳۹۳، ساعت ۱۱:۵۵

سلام . مطلب کوتاه ولی مفید بود .ممنون

• شهناز
۵ آبان ۱۳۹۴، ساعت ۱۹:۳۱

عالی بود استفاده کردم .

• فاطمه
۲۰ آذر ۱۳۹۴، ساعت ۱۳:۳۷

من ی سوال داشتم ممنون میشم اگه جواب بدید خیلی حیاتی هست برنامه که ضرب اعداد بهینه را پیاده سازی کند؟ ورودی:دو عدد بزرگ خروجی:حاصلضرب آن ها

• الف
۴ مرداد ۱۳۹۵، ساعت ۲۰:۳۴

سلام عالی بود از این الگوریتم برای مسیر یابی دو نقطه متحرک در مسیریابی ربات هم می شود استفاده کرد ؟

۴ مرداد ۱۳۹۵، ساعت ۲۱:۳۲
• مسعود اقدسی فام

خیلی ممنون.

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

• سعید ونهری
۲۶ خرداد ۱۳۹۶، ساعت ۲۰:۰۸

واقعا غالی ممنونم

• میکاییل
۳ آذر ۱۳۹۹، ساعت ۱۹:۴۹

دوستی که گفتی یه دست صدا نداره

من با یه دست صدات رو در میارم میخوای امتحان کنی؟141414