yashar
11-13-2009, 03:40 PM
یکی از روشهای پرکاربرد و مشهور طراحی الگوریتم روش برنامه نویسی پویا (Dynamic Programming) است. این روش نیز همچون روش تقسیم و حل (Divide and Conquer) بر پایه تقسیم مساله بر زیرمساله ها کار می کند. اما تفاوتهای چشم گیری با آن دارد!
زمانی که یک مساله به دو یا چند زیر مساله تقسیم می شود، دو حالت ممکن است پیش بیاید:
1- داده های زیر مساله ها هیچ اشتراکی با هم نداشته و کاملا مستقل از هم هستند. نمونه چنین مواردی مرتب سازی آرایه ها با روش ادغام یا روش سریع است که داده ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می شوند. در این حالت داده های یکی از بخش ها هیچ ارتباطی با داده های بخش دیگر نداشته و در نتیجه حاصله از آن بخش اثری ندارند. معمولا روش تقسیم و حل برای چنین مسائلی کارآیی خوبی دارد.
2- داده های زیر مساله وابسته به هم بوده و یا با هم اشتراک دارند. در این حالت به اصطلاح زیر مساله ها هم پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله فیبوناتچی است.
دنباله فیبوناتچی:
می دانیم که تعریف بازگشتی دنباله فیبوناتچی به این ترتیب است:
F( n ) = F ( n - 1 ) + F ( n - 2 ) n > 2 , 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 رسم می کنیم:
http://pnu-club.com/imported/2009/11/1556.jpg
هر گره درخت، فراخوانی تابع را با مقدار داخل آن نشان می دهد. برای محاسبه جمله هفتم دنباله فیبوناتچی تابع fibo به صورت ( fibo( 7 فراخوانی می شود، که آن هم ( fibo( 6 و ( fibo( 5 را فراخوانی می کند و الی آخر. همانطور که مشاهده می کنید برای محاسبه این جمله، ( fibo( 7 یک بار، ( fibo( 6 یک بار، ( fibo( 5 دو بار، ( fibo( 4 سه بار، ( fibo( 3 پنج بار، ( fibo( 2 هشت بار، ( fibo( 1 سیزده بار، و روی هم رفته تابع fibo سی و سه بار فراخوانی می شود!
قبلا مطلبی با عنوان "بازگشتی یا غیربازگشتی؟" از این سایت منتشر شده است که در مورد دنباله فیبوناتچی هم بحثهایی دارد. در آنجا می خوانیم که برای محاسبه جمله چهلم دنباله فیبوناتچی تابع فوق حدود 204 میلیون بار خود را فراخوانی می کند!!! چرا که مرتبه اجرایی آن به صورت نمایی است. اما اگر همین مساله را به یک کودک دبستانی بدهید در کمتر از چند دقیقه جمله چهلم را محاسبه می کند!
ما خود چگونه جملات دنباله فیبوناتچی را محاسبه می کنیم؟ ابتدا جمله اول و دوم را جمع زده و جمله سوم را محاسبه می کنیم. سپس با استفاده از جمله به دست آمده و جمله دوم، جمله چهارم را محاسبه می کنیم و الی آخر:
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 عمل جمع نیاز است که در مورد n = 40 تقابل عدد 204 میلیون و عدد 38 جالب می نماید! دلیل اختلاف فاحش این دو عدد در این است که در حالت دوم، هر جمله دنباله فقط و فقط یک بار محاسبه می شود. این همان روش برنامه نویسی پویا است!
در برنامه نویسی پویا مساله به صورت جزء به کل حل می شود. یعنی ابتدا زیر مسائل خرد حل شده و نتیجه آنها در مکانی دخیره می شود. سپس به سمت زیر مسائل کلی تر رفته و با استفاده از داده های از پیش محاسبه شده آنها نیز حل می شوند. در مورد دنباله فیبوناتچی می توان نوشت:
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 به ۱، که در روش تقسیم و حل استفاده می شود)، از جزء به سمت کل حرکت می کنیم. همانطور که عنوان کردیم هر جمله دنباله تنها به دو جمله ماقبل خود نیاز دارد، که با حرکت جزء به کل قبلا محاسبه شده اند و نیاز به محاسبه محدد آنها نیست. البته این کد را می توان ساده تر کرد:
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;
}
تحلیل این تابع ساده را به خود شما وا می گذاریم.
مثال دیگری از کاربرد برنامه نویسی پویا محاسبه ضرایب بسط دو جمله ای نیوتن است که قبلا در مطلبی با عنوان "بسط دوجمله ای نیوتن به دو روش" به آن پرداخته ایم. توضیح اضافی اینکه می توان ثابت کرد محاسبه ضرایب بسط دو جمله ای نیوتن به روش تقسیم و حل نیز همانند دنباله فیبوناتچی از مرتبه نمایی است.
توجه داشته باشید که اگر زیر مساله ها هم پوشانی نداشته باشند Dynamic Programming هیچ کمکی به ما نخواهد کرد. چرا که خاصیت اصلی این روش ذخیره داده هایی است که ممکن است به کرات به آنها مراجعه شود. حال اگر هیچ اشتراکی در کار نباشد، طبیعتا از هر داده تنها یک بار استفاده خواهد شد.
برنامه نویسی پویا برای طراحی الگوریتمهای محاسبه حالت های بهینه مسائل نیز کاربرد زیادی دارد. به عنوان مثال در یافتن کوتاهترین مسیر بین دو نقطه به روش فلوید، محاسبه بهینه ترین حالت ضرب زنجیری ماتریسها، درخت جستجوی بهینه، مساله فروشنده دوره گرد، محاسبه ضرب چند جمله ای ها، مساله کوله پشتی ۱ - ۰ و چندین مساله دیگر از Dynamic Programming استفاده می شود. شرط اساسی امکان استفاده از این روش برای محاسبه حالت بهینه به اصل بهینگی مشهور است.
اصل بهینگی: اصل بهینگی یعنی حل مساله به صورت بهینه، حاوی حل بهینه تمامی زیر مسائل آن نیز باشد.
به عبارت دیگر مساله باید به گونه ای باشد که با یافتن حل بهینه آن، حل بهینه همه زیر مساله ها نیز به دست آمده باشد. به عنوان مثال در یافتن کوتاهترین مسیر، مسیر بین مبدا و هر گرهی که در مسیر بهینه وجود دارد، بهینه ترین مسیر بین آن دو نیز هست. در مسائلی مانند دنباله فیبوناتچی با محاسبه جمله nام، مقادیر تمام جملات کوچکتر از n هم از طریق آرایه در دسترس قرار می گیرد.
منبع:
http://pnu-club.com/imported/2009/11/111.png (http://www.pcpedia.ir/)
زمانی که یک مساله به دو یا چند زیر مساله تقسیم می شود، دو حالت ممکن است پیش بیاید:
1- داده های زیر مساله ها هیچ اشتراکی با هم نداشته و کاملا مستقل از هم هستند. نمونه چنین مواردی مرتب سازی آرایه ها با روش ادغام یا روش سریع است که داده ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می شوند. در این حالت داده های یکی از بخش ها هیچ ارتباطی با داده های بخش دیگر نداشته و در نتیجه حاصله از آن بخش اثری ندارند. معمولا روش تقسیم و حل برای چنین مسائلی کارآیی خوبی دارد.
2- داده های زیر مساله وابسته به هم بوده و یا با هم اشتراک دارند. در این حالت به اصطلاح زیر مساله ها هم پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله فیبوناتچی است.
دنباله فیبوناتچی:
می دانیم که تعریف بازگشتی دنباله فیبوناتچی به این ترتیب است:
F( n ) = F ( n - 1 ) + F ( n - 2 ) n > 2 , 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 رسم می کنیم:
http://pnu-club.com/imported/2009/11/1556.jpg
هر گره درخت، فراخوانی تابع را با مقدار داخل آن نشان می دهد. برای محاسبه جمله هفتم دنباله فیبوناتچی تابع fibo به صورت ( fibo( 7 فراخوانی می شود، که آن هم ( fibo( 6 و ( fibo( 5 را فراخوانی می کند و الی آخر. همانطور که مشاهده می کنید برای محاسبه این جمله، ( fibo( 7 یک بار، ( fibo( 6 یک بار، ( fibo( 5 دو بار، ( fibo( 4 سه بار، ( fibo( 3 پنج بار، ( fibo( 2 هشت بار، ( fibo( 1 سیزده بار، و روی هم رفته تابع fibo سی و سه بار فراخوانی می شود!
قبلا مطلبی با عنوان "بازگشتی یا غیربازگشتی؟" از این سایت منتشر شده است که در مورد دنباله فیبوناتچی هم بحثهایی دارد. در آنجا می خوانیم که برای محاسبه جمله چهلم دنباله فیبوناتچی تابع فوق حدود 204 میلیون بار خود را فراخوانی می کند!!! چرا که مرتبه اجرایی آن به صورت نمایی است. اما اگر همین مساله را به یک کودک دبستانی بدهید در کمتر از چند دقیقه جمله چهلم را محاسبه می کند!
ما خود چگونه جملات دنباله فیبوناتچی را محاسبه می کنیم؟ ابتدا جمله اول و دوم را جمع زده و جمله سوم را محاسبه می کنیم. سپس با استفاده از جمله به دست آمده و جمله دوم، جمله چهارم را محاسبه می کنیم و الی آخر:
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 عمل جمع نیاز است که در مورد n = 40 تقابل عدد 204 میلیون و عدد 38 جالب می نماید! دلیل اختلاف فاحش این دو عدد در این است که در حالت دوم، هر جمله دنباله فقط و فقط یک بار محاسبه می شود. این همان روش برنامه نویسی پویا است!
در برنامه نویسی پویا مساله به صورت جزء به کل حل می شود. یعنی ابتدا زیر مسائل خرد حل شده و نتیجه آنها در مکانی دخیره می شود. سپس به سمت زیر مسائل کلی تر رفته و با استفاده از داده های از پیش محاسبه شده آنها نیز حل می شوند. در مورد دنباله فیبوناتچی می توان نوشت:
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 به ۱، که در روش تقسیم و حل استفاده می شود)، از جزء به سمت کل حرکت می کنیم. همانطور که عنوان کردیم هر جمله دنباله تنها به دو جمله ماقبل خود نیاز دارد، که با حرکت جزء به کل قبلا محاسبه شده اند و نیاز به محاسبه محدد آنها نیست. البته این کد را می توان ساده تر کرد:
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;
}
تحلیل این تابع ساده را به خود شما وا می گذاریم.
مثال دیگری از کاربرد برنامه نویسی پویا محاسبه ضرایب بسط دو جمله ای نیوتن است که قبلا در مطلبی با عنوان "بسط دوجمله ای نیوتن به دو روش" به آن پرداخته ایم. توضیح اضافی اینکه می توان ثابت کرد محاسبه ضرایب بسط دو جمله ای نیوتن به روش تقسیم و حل نیز همانند دنباله فیبوناتچی از مرتبه نمایی است.
توجه داشته باشید که اگر زیر مساله ها هم پوشانی نداشته باشند Dynamic Programming هیچ کمکی به ما نخواهد کرد. چرا که خاصیت اصلی این روش ذخیره داده هایی است که ممکن است به کرات به آنها مراجعه شود. حال اگر هیچ اشتراکی در کار نباشد، طبیعتا از هر داده تنها یک بار استفاده خواهد شد.
برنامه نویسی پویا برای طراحی الگوریتمهای محاسبه حالت های بهینه مسائل نیز کاربرد زیادی دارد. به عنوان مثال در یافتن کوتاهترین مسیر بین دو نقطه به روش فلوید، محاسبه بهینه ترین حالت ضرب زنجیری ماتریسها، درخت جستجوی بهینه، مساله فروشنده دوره گرد، محاسبه ضرب چند جمله ای ها، مساله کوله پشتی ۱ - ۰ و چندین مساله دیگر از Dynamic Programming استفاده می شود. شرط اساسی امکان استفاده از این روش برای محاسبه حالت بهینه به اصل بهینگی مشهور است.
اصل بهینگی: اصل بهینگی یعنی حل مساله به صورت بهینه، حاوی حل بهینه تمامی زیر مسائل آن نیز باشد.
به عبارت دیگر مساله باید به گونه ای باشد که با یافتن حل بهینه آن، حل بهینه همه زیر مساله ها نیز به دست آمده باشد. به عنوان مثال در یافتن کوتاهترین مسیر، مسیر بین مبدا و هر گرهی که در مسیر بهینه وجود دارد، بهینه ترین مسیر بین آن دو نیز هست. در مسائلی مانند دنباله فیبوناتچی با محاسبه جمله nام، مقادیر تمام جملات کوچکتر از n هم از طریق آرایه در دسترس قرار می گیرد.
منبع:
http://pnu-club.com/imported/2009/11/111.png (http://www.pcpedia.ir/)