برای طراحی الگوریتم‌ها 5 رویکرد معروف و کلاسیک وجود دارد:
    - رویکرد تقسیم و غلبه (Divide & Conquer)
    - رویکرد برنامه‌نویسی پویا (Dynamic Programming)
    - رویکرد حریصانه (Greedy)
    - رویکرد عقبگرد (Backtracking)
    - رویکرد شاخه و قید (Branch & Bound)
معمولا الگوریتم حل مسئله‌های کلاسیک و الگوریتمی با یکی از این روش‌ها طراحی می‌شود. در این مطلب قصد دارم شما را قدم به قدم با رویکرد تقسیم و غلبه آشنا کنم.

همان‌طور که از نام این رویکرد هم پیداست، ایده‌ی طراحی الگوریتم به‌روش تقسیم و غلبه، شکستن (Divide) مسئله به زیرمسئله‌های کوچک‌تر و حل (Conquer) جداگانه‌ی هریک از آن‌هاست. ممکن است پس از حل زیرمسئله‌ها، برای ساخت جواب نهایی لازم باشد مراحل درهم ادغام (Merge) شوند. در این پایگاه دانش برای حل مسئله‌های زیر از رویکرد تقسیم و غلبه استفاده کرده‌ایم:
    - جستجوی دودویی (Binary Search)
    - مرتب سازی ادغامی (Merge Sort)
    - مرتب سازی سریع (Quick Sort)
    - ضرب ماتریس‌ها - روش استراسن
    - ضرب اعداد صحیح بزرگ

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

هنگامی از رویکرد تقسیم و غلبه استفاده می‌کنیم که مسئله را بتوان به دو یا چند زیرمسئله‌ی مشابه با اندازه‌ی کوچک و مجزا (Disjoint) تقسیم کرد.

روش تقسیم و غلبه یک روش طراحی بالا به پایین (Top-Down) است. به این معنی که حل یک نمونه‌ی سطح بالا از مسئله، با رفتن به جزء و زیرمسئله‌های کوچکتر حاصل می‌شود. و دقیقا به‌خاطر همین ویژگی خاص می‌توان اغلب یک پیاده‌سازی بازگشتی (Recursive) ارائه داد. نکته‌ای که در این بین وجود دارد، این‌است که برای بهره‌مندی از این روش و حصول کارایی بیشتر، لازم است زیرمسئله‌های تولید شده هم‌پوشانی نداشته باشند. البته هر مسئله‌ای لزوما دارای قابلیت این‌چنینی نیست و اگر زیرمسئله‌های تکراری داشته باشد، از رویکرد برنامه‌نویسی پویا (Dynamic Programming) استفاده خواهیم کرد.

پس از تقسیم مسئله به زیرمسئله‌هایی با اندازه‌ی کوچک‌تر، درمورد هر زیرمسئله تصمیم‌گیری جداگانه‌ای انجام می‌دهیم و ممکن است یکی از راهبردهای زیر را پیش بگیریم:
    - اندازه‌ی زیرمسئله هنوز بزرگ است و باید شکسته شود
    - زیرمسئله نامعتبر است و باید کنار گذاشته شود
    - زیرمسئله به اندازه‌ی کافی کوچک است و راه حل مستقیم دارد

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

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

حالت شروع برای یک مسئله‌ی نمونه - شما باید مهره‌ها را یکی یکی از میله‌ی A به میله‌ی C انتقال دهید. دقت داشته باشید هیچ‌وقت حق ندارید مهره بزرگی را بر روی مهره‌ی کوچک قرار دهید. از میله‌ی B به‌عنوان میله‌ی کمکی استفاده کنید.

برای دریافت جزئیات بیشتر، مسئله‌ی جابجایی برج‌های هانوی را ببینید.

تعداد مهره‌ها در این مسئله همواره برابر 3 است اما تعداد مهره‌ها (n) را مسئله مشخص می‌کند. در شکل بالا یک مسئله‌ی نمونه با 3 مهره نشان داده شده است. هدف یافتن یک ترتیب درست برای جابجایی مهره‌ها از میله‌ 1 به میله‌ی 3 با استفاده از میله‌ی 2 به شرطی که در طول جابجایی و در هیچ‌یک از میله‌ها مهره‌ی با شماره‌ی (اندازه‌ی) بزرگ‌تر بر روی مهره‌ی کوچک‌تر قرار نگیرد. یک جواب قابل قبول می‌تواند این‌چنین باشد:

حالت شروع	حرکت اول: انتقال مهره‌ی 1 از میله‌ی A به میله‌ی C
حرکت دوم: انتقال مهره‌ی 2 از میله‌ی A به میله‌ی B	حرکت سوم: انتقال مهره‌ی 1 از میله‌ی C به میله‌ی B
حرکت چهارم: انتقال مهره‌ی 3 از میله‌ی A به میله‌ی C	حرکت پنجم: انتقال مهره‌ی 1 از میله‌ی B به میله‌ی A
حرکت ششم: انتقال مهره‌ی 2 از میله‌ی B به میله‌ی C	حرکت هفتم: انتقال مهره‌ی 1 از میله‌ی A به میله‌ی C

برای حل این مساله بیایید به این سوال پاسخ دهیم که اگر فقط یک مهره داشتیم چگونه آن را انتقال می‌دادیم؟ واضح است که بدون نیاز به میله‌ی کمکی می‌توانستیم آن را مستقیما از میله‌ی A به میله‌ی C منتقل کنیم. اما برای چند مهره چطور؟ اگر تعداد مهره‌ها را n درنظر بگیریم، باید به نحوی n-1 مهره‌ی بالایی را با استفاده از میله‌ی کمکی C به میله‌ی B منتقل کنیم. حالا بزرگترین مهره به تنهایی در میله‌ی A قرار دارد و می‌توان مانند آنچه در ابتدا گفته شد، آن را بدون هیچ حرکت اضافی و بدون نیاز به میله‌ی کمکی به میله‌ی C منتقل کنیم. حال نوبت انتقال مهره‌های میله‌ی B به میله‌ی C با استفاده از میله‌ی کمکی A است و همین روال را بصورت بازگشتی بر روی همه‌ی مهره‌ها انجام می‌دهیم.

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

1#include <iostream>
2using namespace std;
3void Move(int n, char srcPeg, char trgPeg, char tmpPeg) {
4  if (n == 1)
5    cout << "Move disk #1 from peg "
6      << srcPeg << " to " << trgPeg << endl;
7  else {
8    Move(n - 1, srcPeg, tmpPeg, trgPeg);
9    cout << "Move disk #" << n << " from peg "
10      << srcPeg << " to " << trgPeg << endl;
11    Move(n - 1, tmpPeg, trgPeg, srcPeg);
12  }
13}
14void main() {
15  int n;
16  cin >> n;
17  Move(n, 'A', 'C', 'B');
18}

خروجی آن به‌ازای مقادیر 2، 3 و 4 عبارت‌است از:

2
Move disk #1 from peg A to B
Move disk #2 from peg A to C
Move disk #1 from peg B to C

3
Move disk #1 from peg A to C
Move disk #2 from peg A to B
Move disk #1 from peg C to B
Move disk #3 from peg A to C
Move disk #1 from peg B to A
Move disk #2 from peg B to C
Move disk #1 from peg A to C

4
Move disk #1 from peg A to B
Move disk #2 from peg A to C
Move disk #1 from peg B to C
Move disk #3 from peg A to B
Move disk #1 from peg C to A
Move disk #2 from peg C to B
Move disk #1 from peg A to B
Move disk #4 from peg A to C
Move disk #1 from peg B to C
Move disk #2 from peg B to A
Move disk #1 from peg C to A
Move disk #3 from peg B to C
Move disk #1 from peg A to B
Move disk #2 from peg A to C
Move disk #1 from peg B to C

ادامه دارد...

مانند مرتب‌سازی ادغامی، ممکن است برای رسیدن به جواب نهایی، جواب زیرمسئله‌ها را درهم ادغام (Merge) کنیم. و یا اینکه مانند جستجوی دودویی، به محض یافت جواب در هریک از زیرمسئله‌ها، درواقع به جواب نهایی مسئله نیز رسیده‌ایم و نیازی به ادغام جواب‌ها نیست.