الگوریتم تقسیم و غلبه Divide and Conquer
الگوریتم تقسیم و غلبه Divide & Conquer
بسیاری از مسائل کاربردی کامپیوتری با روش تقسیم و حل (Divide & Conquer) قابل حل هستند. در این روش ابتدا مساله بزرگ به زیر مسائل کوچکتر تقسیم میشود و پس از آن زیر مسائل کوچکتر نیز در صورت لزوم به زیر مسائل کوچکتری تقسیم میشوند و در نهایت با حل مسائل کوچک، مساله اصلی حل میشود.
در واقع روش تقسیم وغلبه در طراحی الگوریتم، روشی از بالا به پایین (top-down) میباشد. الگوریتم تقسیم وغلبه بازگشتی است و معمولا یک مساله کوچک ممکن است چندین بار حل شود. یعنی این روش ها معمولا از نظر زمان و حافظه بهینه نیستند ولی مزیت آنها کدنویسی راحت آنهاست.
لازم به ذکر است که تمام مسائل با روش تقسیم وغلبه قابل حل نیستند، مثلا نمیتوان برای یافتن جوابهای یک دستگاه 100 معادله 100 مجهول آن را به دو دستگاه 50 معادله 50 مجهول تبدیل کرد. ولی مثلا میتوان برای یافتن ماکزیمم یک آرایه 100 عنصری، آرایه را به 2 آرایه 50 عنصری تقسیم کرده، ماکزیمم هر قسمت را یافته سپس با مقایسه نتایج، ماکزیمم را پیدا کنیم.
میتوان الگوریتم کلی تقسیم و حل را به صورت زیر نوشت:
► اگر مسئله به اندازه کافی کوچک است و میتوان آن را حل کرد، حل کن.
► اگر مسئله بزرگ است آن را به مسائل کوچک تقسیم کن و تقسیم را ادامه بده.
► مسائل کوچکتر را حل کن (مشابه مسائل بزرگ)
► مسائل حل شده کوچک را با هم ترکیب کن تا مسئله بزرگ حل شود.
الگوریتم کلی تقسیم و حل بصورت شبه کد در زیر نوشته شده است.
الگوریتم انتزاعی روش تقسیم و غلبه
Algorithm DandC (Low , high)
if small (low , high) then return g (Low , high)
else {
mid = Divide (Low , high)
return combine ( DandC (Low , mid) , DandC (mid+1 , high) )
}
در این الگوریتم تابع small مشخص میکند آیا مساله به اندازه کافی کوچک هست که بتوان آن را بدون شکستن حل کرد یا خیر. اگر جواب مثبت باشد، تابع g فراخوانی میشود در غیر اینصوررت عمل تقسیم انجام میشود.
در ضمن اگر فرض کنیم ورودی در آرایه A[1…n] باشد، فراخوانی باید بصورت Danc(1 , n) صورت گیرد.
اگر زمان اجرای الگوریتم Combine در الگوریتم 1، f(n) فرض شود آنگاه زمان اجرای الگوریتم، برابر است با:
T(n) = 2 T(n/2) + f(n) های بزرگ nبرای
T(n) = g(n) های کوچکnبرای
در T(n) فرض شده است که n توانی از 2 است و همچنین در هر بار تقسیم، آرایه دقیقا نصف میشود. و همچنین g(n) زمان تابع g میباشد.
الگوریتم های معروفی که به روش الگوریتم تقسیم و غلبه حل میشوند عبارتنداز:
► جستوجوی دودویی
► بزرگترین و کوچکترین عنصر آرایه
► ضرب اعداد بزرگ
► ضرب چند جمله ای ها
► ضرب دو ماتریس
► مرتب سازی سریع
► مرتب سازی ادغامی
► یافتن کوچکترین (بزرگترین ) کلید دوم و یافتن کوچکترین (بزرگترین) کلید i ام.
مفید بود.ممنون
سلام خسته نباشید میشه الگورتیم معکوس یک رشته به روش تقسیم غلبه رو قرار بدین با تشکر
خسته نباشید . اگه میشه چند تا مثال در سطوح مختلف با این روش بزنید . برای فهم بیشتر . چون خیلیا مثله من رشتشون کامپیوتر نیست و ممکنه بدون مثاله کد نویسی درست متوجه نشن . ممنون