تقسیم و حل
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : powerpoint (..ppt) ( قابل ويرايش و آماده پرينت )
تعداد اسلاید : 54 اسلاید
قسمتی از متن powerpoint (..ppt) :
تقسیم و حل Divide and Conquer
1
یکی از روش های حل مسئله ، تقسیم و حل است . اساس این روش به صورت حل بالا به پایین ( Top down ) است .در این روش مسئله ای با سایز بزرگ را آن قدر کوچک می کنیم که حل آن مقدور یا بدیهی شود . سپس از ترکیب زیر مسائل حل شده به حل مسئله اصلی می رسیم.
استفاده از این روش در طراحی الگوریتم ممکن است به یکی از دلایل زیر باشد :
حل مسئله با روش دیگری امکان پذیر نباشد
الگوریتم آن نسبت به روش های دیگر کارا تر باشد.
اما قبل از اعمال این روش باید به چند سوال پاسخ دهیم:
مسئله اصلی را به چند زیر مسئله تقسیم کنیم ؟
هر زیر مسئله چه سایزی داشته باشد؟ ( زیر مسائل هم اندازه باشند یا خیر؟ )
نوع شکستن (از بالا به پایین مسئله شکسته شود یا از پایین به بالا زیر مسائل کوچکتر ترکیب شوند.)
2
الگوريتم كلي تقسيم و حل :
الگوريتم DandC در آغاز به صورت DandC (P) فراخواني مي شود . كه در آن P مسئله اصلي است كه مي بايست حل شود . Small(P) بررسي مي كند كه مسئله به اندازه كافي كوچك است كه بتوان آنرا مستقيماً حل كرد يا خير . اگر نتيجه كار مثبت باشد زير مسئله P محاسبه مي شود . ) مثلاً توسط تابعي به نام S(P) ) .
در غير اين صورت مسئله P به زيز مسئله هاي كوچكتر تقسيم مي شود . حاصل اينكار توليد زير مسئله هاي , P 2 , P 1 ... , P k مي باشد كه حاصل بازگشت هاي پي در پي مي باشد . در نهايت تابع Combine براي تركيب راه حل هاي زير مسئله براي محاسبه راه حل مسئله اصلي به كار مي رود .
3
Result DandC ( P )
{
if ( Small ( P ) )
return S( P ) ;
else{
Divide P into Smaller instances
P 1 , ... , P k for K ≥ 1 ;
/* Apply dandC to each of these Subproblems */
return Combine(DandC(P 1 ) , DandC(P 2 ),…, DandC( P k )) ;
}
}
4