تقسیم و حل

اگر بخواهیم خیلی ساده بگوییم، الگوریتم، روش حل مسائل است. یک دسته از این روش‌ها، تقسیم و حل (Divide and Conquer) است. این روش برای طراحی الگوریتم‌ها از روی راهبرد درخشانی الگوبرداری شده است که ناپلئون، امپراتوری فرانسه در نبرد اوسترلیتز در دوم دسامبر 1805 به‌کار برد. ارتشی مرکب از سربازان اتریشی و روسی به جنگ با ناپلئون آمده بود که تعداد آنها 15000 نفر از افراد ناپلئون بیشتر بود.سپاه اتریشی_روسی حمله‌ای گسترده علیه فرانسویان آغاز کرد.

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

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

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