در ، ( ) (به : ) ی مهمی بر اساس چند خطی است. یک تقسیم و حل از طریق تفکیک یک مسئله به دو یا چند زیرمسئله از یک نوع (یا انواع وابسته به هم) به صورت بازگشتی کار می‌کند. این تفکیک تا زمانی ادامه می‌یابد که زیرمسئله‌های حاصله به میزان کافی ساده شده باشند تا بتوان آن‌ها را مستقیماً حل کرد. جواب مسئلهٔ اصلی از ترکیب جواب‌های به دست آمده برای زیر مسئله‌ها به دست می‌آید.
 این تکنیک مبنای الگوریتم‌های کارآمدی برای انواع مسئله‌ها است، به عنوان مثال، الگوریتم‌های (مثل و ), (مثل ), (مثل )، و محاسبهٔ ( ) از روش تقسیم و حل استفاده می‌کنند.
 از سوی دیگر، توانایی درک و طراحیِ الگوریتم‌های حل و تقسیم هنری است که کسب مهارت در آن زمان زیادی می‌طلبد. به هنگام یک به کمک استقرا، غالباً نیازمند آنیم که به منظور دستیابی به یک روند بازگشتی، مسئلهٔ اصلی را با یک مسئلهٔ عمومی‌تر یا پیچیده‌تر جایگزین کنیم، و این در حالی است که روش منظمی برای یافتن تعمیم مناسب وجود ندارد.
 گاهی اوقات نام «تقسیم و حل» در مورد الگوریتم‌هایی که هر مسئله را تنها به یک زیرمسئله تقلیل می‌دهند نیز به کار می‌رود، مانند الگوریتم برای یافتن یک پرونده در یک لیست مرتب شده. با وجود این تعریف جامع، هر الگوریتمی که از بازگشت یا حلقه استفاده می‌کند، به نوعی می‌تواند «الگوریتم تقسیم و حل» تلقی شود. از این رو، بعضی از مؤلفان درعوض از نام «کاهش و حل» استفاده می‌کنند. این الگوریتم‌ها می‌توانند کارآمدتر از الگوریتم‌های تقسیم و حل معمولی، پیاده‌سازی شوند. به عنوان مثال، در صورت استفاده از ، این الگوریتم‌ها می‌توانند به ساده تبدیل شوند.
 معمولاً صحت یک الگوریتم تقسیم و حل به کمک اثبات، و هزینهٔ محاسباتی آن نیز معمولاً از طریق حل تعیین می‌شود.
 الگوی تقسیم و حل اغلب برای یافتن راه حل بهینه از یک مسئله استفاده می‌شود. ایده اصلی این است که یک مسئلهٔ معین را به دو یا چند زیرمجموعه مشابه، اما ساده‌تر تقسیم کنیم تا به نوبه خود آنها را حل کند و راه حل‌های خود را برای حل مسئله مورد نظر تنظیم کند. مسئله‌های بسیار ساده به‌طور مستقیم حل می‌شود. به عنوان مثال، برای مرتب کردن یک لیست معین از اعداد طبیعی، آن را به دو لیست به طول n / 2 تقسیم می‌کنیم، هر یک را به نوبه خود مرتب می‌کنیم و هر دو نتیجه را به‌طور مناسب در هم ادغام می‌کنیم تا نسخه مرتب شده لیست بدست آید (نگاه کنید به تصویر). در این مثال لیست‌های با طول یک نیاز به مرتب‌سازی (حل) ندارند. این روش به الگوریتم معروف است.
 ایدهٔ اصلی روش تقسیم و حل توسط در سال ۱۹۶۰ در قالب الگوریتمی برای ضرب کردن دو عدد n رقمی با ارائه شد. در نتیجه این الگوریتم که امروزه نامیده می‌شود، فرضیه که طبق آن سریع‌ترین الگوریتم ضرب دارای پیچیدگی است نقض شد. تلاش کولموگروف در کنار کشف کاراتسوبا، کمک شایانی به آغاز مطالعهٔ کرد.
 ، الگوریتم تقسیم و حلی که در آن مسئلهٔ اصلی متوالیاً به زیرمسئله‌هایی یکتا با اندازهٔ تقریبی نصف مسئلهٔ اصلی تفکیک می‌شود، پیشینهٔ دور و درازی دارد. ایدهٔ استفاده از یک لیست مرتب شده از عناصر به منظور سهولت بخشیدن در جستجو به ۲۰۰ سال پیش از میلاد، در بابل بازمی‌گردد، در حالی که یک توصیف واضح از الگوریتم در کامپیوتر اولین بار قرن‌ها بعد در سال ۱۹۴۶ در مقاله‌ای توسط جان مارچلی بیان شد. الگوریتم تقسیم و حلِ قدیمی دیگر در محاسبهٔ دو عدد (از طریق کاهش اعداد به زیرمسئله‌های کوچک‌تر، و کوچک‌تر یا مساوی) است، که به قرن‌ها پیش از میلاد بازمی‌گردد. یک مثال قدیمی دیگر از الگوریتم تقسیم و حل با زیرمسئله‌های چندگانه، توصیفی بود که در سال ۱۸۰۵ از چیزی که امروزه نامیده می‌شود، ارائه داد؛ هر چند او از لحاظ کمّی، این الگوریتم را تحلیل و بررسی نکرد و FFTها تا یک قرن بعد که دوباره کشف شدند فراموش شدند.
 یک الگوریتم تقسیم و حلِ دوزیرمسئله‌ایِ قدیمی که به‌طور ویژه برای کامپیوترها توسعه یافته، الگوریتم می‌باشد که توسط در سال ۱۹۵۴ ابداع شد. 
 مثال قابل توجه دیگر، ی است که توسط در سال۱۹۶۰ ابداع شده و می‌تواند دو عدد رقمی را در ضرب کند. این الگوریتم، حدس 'که در سال ۱۹۵۶ بیان شد و عمل را برای انجام ضرب مذکور لازم می‌دانست را رد کرد.
 یک مثال دیگر از یک الگوریتم تقسیم و حل که در ابتدا کامپیوترها را شامل نمی‌شد، الگوریتم ارائه شده توسط « » بود که در یک دفتر پست برای آدرس‌دهی نامه‌ها استفاده می‌شد: نامه‌ها در کیف‌های جداگانه برای مناطق مختلف جغرافیایی مرتب می‌شدند، در هر کدام از این کیف‌ها نیز نامه‌ها در دسته‌هایی مربوط به نواحی کوچک‌تر مرتب می‌شدند و به همین ترتیب؛ تا زمانی که نامه‌ها به مقصد برسند. این الگوریتم نوعی است که در سال ۱۹۲۹ برای ماشین‌های ارائه شد. 
 تقسیم و حل ابزاری قدرتمندی برای حل مسائل دشوار مفهومی، همانند معمای باستانی است. همهٔ چیزی که حل این روش نیاز دارد پیدا کردن راهی است برای شکستن مسئله به چند زیرمسئله، حل حالات جزئی و ترکیب زیرمسئله‌ها به مسئلهٔ اصلی.
 الگوی تقسیم و حل اغلب به یافتن الگوریتم‌های کارآمد کمک می‌کند. برای مثال این الگوریتم راه‌گشای روش‌های ، الگوریتم‌های مرتب‌سازی و ، و هم‌چنین بود.
 در تمام این مثال‌ها راهبردِ حل و تقسیم منجر به بهینه‌سازی راه حل می‌شود. برای مثال اگر حالت‌های پایه، اندازهٔ ثابت کران‌داری داشته‌باشند و عمل تفکیک مسئله و ترکیب جواب‌های جزئی به نسبت اندازهٔ مسئله ( باشد آنگاه یک تعداد محدود از زیرمسئله‌ها با اندازهٔ در هر مرحله وجود دارد و هزینهٔ الگوریتم تقسیم و حل خواهد بود.
 الگوریتم‌های تقسیم و حل ذاتاً برای اجرا در ماشین‌های چندپردازنده‌ای سازگارند؛ به ویژه برای سیستم‌هایی با حافظه‌اشتراکی که ارتباط داده‌ها بین پردازنده‌ها به برنامه‌ریزی پیشرفته نیازی ندارد، چرا که زیرمسئله‌های متمایز قابل اجرا بر روی پردازنده‌های مختلف می‌باشند
 الگوریتم‌های تقسیم و حل در کل به دنبال بهینه ساختن دسترسی به حافظه‌های پنهان هستند. چون زمانی که زیرمسئله به اندازهٔ کافی کوچک باشد، آن زیر مسئله و تمام زیرمسئله‌های آن می‌توانند بدون دسترسی به حافظه اصلی که کندتر است، در داخل حافظهٔ پنهان حل شوند. الگوریتمی که به منظور اینچنین دسترسی به حافظهٔ پنهان طراحی می‌شود، ، نامیده می‌شود؛ چرا که اندازهٔ حافظهٔ پنهان را به عنوان یک پارامتر آشکار، در برندارند. 
 علاوه بر این، الگوریتم‌های تقسیم و حل می‌توانند در بسیاری از الگوریتم‌های مهم مانند انواع و استفاده شوند. به طریقی مشابه، الگوریتم‌های بهینهٔ بی‌توجه به حافظهٔ پنهان)، چنان‌که می‌توان اثبات کرد، به صورت بهینه و از دید مجانبی و صرف‌نظر از اندازهٔ حافظهٔ پنهان، از الگوریتم‌های تقسیم و حل استفاده می‌کنند. در مقابل، راهبرد سنتیِ به کار بستن حافظهٔ پنهان، بلاک‌بندی می‌باشد؛ که در آن، مسئله به قطعه‌هایی از اندازه‌های مورد نیاز تقسیم می‌شود. این الگوریتم هم‌چنین می‌تواند به‌طور بهینه از استفاده کند، ولی فقط زمانی که الگوریتم، برای اندازهٔ خاصی از حافظهٔ پنهان در یک ماشین ویژه، مناسب‌سازی شده باشد.
 در سیستم‌های حافظه‌ای سلسله مراتبی مزیت مشابهی وجود دارد. همانند یا و نیز برای سطوح چندگانهٔ حافظهٔ پنهان. زمانی که یک زیرمسئله به اندازهٔ کافی کوچک باشد، می‌تواند بدون دسترسی به سطوح بالاتر (آهسته‌تر)، در داخل سطح مفروض از سلسله‌مراتب حل شود.
 این روش با تقسیم کردن مسئله به تعداد زیر مسئله و حل تک تک آن‌ها عمل می‌کند.
 در مواردی ممکن است این روش یک مسئله را تعداد دفعات زیادی حل کند و این می‌تواند به طولانی شدن زمان اجرا منجر شود (البته این موضوع بر پیچیدگی زمانی تأثیری ندارد).
 در بعضی برنامه‌ها هر بخش که با روش بازگشتی حل می‌شود در حافظه به همراه پاسخ ذخیره می‌شود تا در صورت نیاز دوباره به پاسخ آن محاسبهٔ دوباره صورت نگیرد. این روش مشکل ذکر شده را تا حدی مرتفع می‌کند
 الگوریتم‌های تقسیم و حل معمولاً به صورت پیاده‌سازی می‌شوند. در این حالت، زیرمسئله‌های جزئی براساس زیرمسئله‌ای که در حال حل شدن است، به صورت خودکار در ذخیره می‌شوند. روش تقسیم و حل یک روش بالا به پایین است.
 حل یک نمونهٔ سطح بالای مسئله با بدست آوردن حل نمونه‌های کوچکتر حاصل می‌شود.
 هنگام پی ریزی یک الگوریتم بازگشتی، باید:
 
 
 روش بازگشتی اجازه بیان راه حل یک مسئله را به‌طور مختصر و مفید می‌دهد. مسئله‌ای که به صورت بازگشتی حل می‌شود باید بتواند به مسائل کوچک‌تر تقسیم بشود و حل مسائل کوچک به همان روش مسئله بزرگ قابل انجام باشد. مسئله کوچک‌تر به مسئله کوچک‌تری شکسته می‌شود تا سرانجام یه کوچک‌ترین اندازه مسئله برسد که حالت پایه نامیده می‌شود و می‌تواند بدون استفاده از بازگشتی حل شود.
 یک مثال متعارف الگوریتم بازگشتی ضابطه تابع فاکتوریل است:
 مقدار تابع برای به صورت زیر محاسبه می‌شود:
 
 بعضی الگوریتم‌های بازگشتی توسط تابع بازگشتی پیاده‌سازی می‌شود. (recursive function) تابعی است که خودش را فراخوانی می‌کند.
 مشابه توابع دیگر کار می‌کند. برای هر فراخوانی بازگشتی یک نمونهٔ جدید از تابع در پشته ایجاد می‌شود.
 
مثال تابع بازگشتی محاسبه فاکتوریل یک عدد صحیح: همان تابع به صورت غیر بازگشتی (توجه کنید که به دو متغیر موقت نیاز است): در مسئله بازگشتی نیاز داریم یک زیرساختار بازگشتی داشته باشیم. راه حل بعضی از مسائل به‌طور بازگشتی است چون احتیاج به نگهداری حالت قبلی دارند (ولی می‌دانیم که هر مسئله بازگشتی را می‌توانیم به صورت غیر بازگشتی بنویسیم) (tree traversal)، (Ackermann) و الگوریتم‌های حل و تقسیم مانند (Quicksort) همگی معمولاً صورت بازگشتی هستند. همه این الگوریتم‌ها می‌توانند به صورت غیربازگشتی با کمک هم پیاده شوند اما نیاز به مزیت راه حل غیر بازگشتی را از بین می‌برد.
 تابع غیر بازگشتی احتمالاً در عمل کمی سریعتر از نسخه بازگشتی آن اجرا می‌شود چون تابع غیر بازگشتی باراضافه فراخوانی تابع (function-call) را به اندازه تابع بازگشتی نخواهد داشت و این باراضافی در بعضی نسبتاً بالا است.
 یک دلیل دیگر برای ترجیح غیربازگشتی به بازگشتی این است که فضای قابل دسترس کمتر از فضای قابل دسترس در حافظه آزاد (heap)است؛ و الگوریتم‌های بازگشتی تمایل به فضای پشته بیشتری نسبت به غیر بازگشتی دارند.
 Dالگوریتم‌های تقسیم و حل هم‌چنین می‌توانند به واسطهٔ یک برنامهٔ غیربازگشتی که زیرمسئله‌های جزئی را در بعضی داده‌ساختارهای صریح همانند ، ، یا ، ذخیره می‌کند، پیاده‌سازی شوند. این راهبرد آزادی بیشتری در انتخاب زیرمسئله‌ای که در قرار است در مرحلهٔ بعد حل شود، می‌دهد، ویژگی ای که در بعضی از برنامه‌های کاربردی دارای اهمیت می‌باشد. همانند متد در برای بهینه‌سازی عملکرد. این راهبرد، هم‌چنین راه‌حل استاندارد زبان‌های برنامه‌نویسی‌ای می‌باشد که از روال‌های بازگشتی پشتیبانی نمی‌کنند.
 در پیاده‌سازی‌های بازگشتیِ الگوریتم‌های حل و تقسیم(D&C)، باید از وجود حافظهٔ تخصیص داده‌شدهٔ مورد نیاز برای پشتهٔ بازگشت اطمینان حاصل شود، درغیراین‌صورت ممکن است به دلیل . ، اجرا با شکست مواجه شود. خوشبختانه، الگوریتم‌های D&Cای که از لحاظ زمانی کارآمد هستند، اغلب، تا حدودی بازگشتی هستند. به عنوان مثال، سریع می‌تواند طوری پیاده‌سازی شود که هرگز به بیشتر از فراخوانی بازگشتی تودرتو برای مرتب کردن عنصر نیاز نداشته‌باشد.
 ممکن است اجتناب از سرریز شدن پشته، به هنگام استفاده از روال‌های بازگشتی دشوار باشد، چرا که بسیاری از کامپایلرها فرض می‌کنند که پشتهٔ بازگشت ناحیه‌ای است مجاور حافظه، و بعضی از آن‌ها یک مقدار ثابت از حافظه را برای آن تخصیص می‌دهند. هم‌چنین ممکن است کامپایلرها اطلاعاتی بیشتر از آنچه که واقعاً نیاز است را در پشتهٔ بازگشت ذخیره کنند، همانند آدرس برگشت، پارامترهای تغییرناپذیر، و متغیرهای درونی روال؛ بنابراین، خطر سرریز شدن پشته می‌تواند با حداقل کردن پارامترها و متغیرهای درونی روال بازگشتی، یا با استفاده از یک ساختار پشتهٔ صریح، کاهش یابد.
 در هر الگوریتم بازگشتی، آزادی قابل توجهی در انتخاب (زیرمسئله‌های کوچکی که به منظور پایان دادن به بازگشت، مستقیماً حل می‌شوند) وجود دارد.
 انتخاب کوچک‌ترین یا آسان‌ترین حالت پایهٔ ممکن، بهتر است و معمولاً منجر به مسئله‌های آسان‌تر می‌شود، چرا که حالات کمتری برای رسیدگی وجود دارند که حلشان هم ساده‌تر است. به عنوان مثال، یک الگوریتم FFT می‌تواند به بازگشت پایان دهد وقتی که ورودی یک نمونهٔ یکتا باشد، و الگورتیم مرتب‌سازی لیستِ «مرتب‌سازی سریع» زمانی پایان می‌یابد که ورودی، لیست خالی باشد؛ در هر دو مثال تنها یک برای بررسی وجود دارد، که به هیچ پردازشی هم نیاز ندارد.
 از سوی دیگر اگر بازگشت در حالات نسبتاً بزرگ متوقف شود، معمولاً کارایی بهبود می‌یابد؛ که هرکدام از این حالات به صورت غیربازگشتی حل شوند، که به یک منجر می‌شود. این روش، از فراخوانی‌های بازگشتی که کار اندکی انجام داده یا اصلاً کاری انجام نمی‌دهند، اجتناب می‌ورزد و هم‌چنین ممکن است استفاده از الگوریتم‌های غیربازگشتی خاصی که برای آن، حالات پایه کارآمدتر از بازگشتِ صِرف می‌باشند را میسر سازد. از آن جایی که یک الگوریتم تقسیم و حل، سرانجام، هر نمونه از مسئله یا زیرمسئله را به تعداد زیادی نمونهٔ پایه تقسیم می‌کند، این نمونه‌های پایه هزینهٔ کلی الگوریتم را رقم می‌زنند، علی‌الخصوص زمانی که هزینهٔ کلیِ تقسیم و ترکیب پایین باشد. توجه داشته باشید که این ملاحظات به این‌که آیا بازگشت به واسطهٔ کامپایلر پیاده‌سازی شده‌است یا به کمک یک پشتهٔ صریح، بستگی ندارد.
 بنابراین، به عنوان مثال، بسیاری از پیاده‌سازی‌های کتابخانه‌ایِ مرتب‌سازی سریع، وقتی که تعداد عناصری که قرار است مرتب شوند به اندازهٔ کافی کوچک باشد، به یک الگوریتم سادهٔ مبتنی بر حلقه (یا چیزی شبیه آن) پرش می‌کنند. توجه شود که، اگر لیست خالی تنها حالت پایه بود، مرتب‌سازی یک لیست با ورودی منجر به +۱ فراخوانی مرتب‌سازی سریع خواهدشد که کاری انجام نداده و فوراً برمی‌گردند. افزایش حالات پایه به لیست‌هایی با اندازهٔ ۲ یا کم‌تر، بیشترِ این فراخوانی‌هایی که کاری انجام نمی‌دهند را حذف خواهد کرد و به‌طور کلی به منظور کاهش زمان مصرفی برای فراخوانی‌ها یا دستکاری‌های پشته، معمولاً از حالت پایه‌ای بزرگ‌تر از ۲ استفاده می‌شود.
 هم‌چنین، می‌توان حالات پایهٔ بزرگی را به کار بست که کماکان از الگوریتم تقسیم و حل استفاده کنند. اما پیاده‌سازی الگوریتم برای مجموعه‌های از پیش تعیین‌شده با اندازهٔ ثابت می‌تواند کاملاً به کدی بدون هیچ‌گونه بازگشت، حلقه یا (بسته به روش ) تبدیل شود. به عنوان مثال، این راهبرد در بعضی از پیاده‌سازی‌های کارآمد FFT که در آن‌ها حالات پایه، پیاده‌سازی‌های تبدیل‌شدهٔ الگوریتم‌های تقسیم و حل FFT برای یک مجموعه از اندازه‌های ثابت می‌باشند، مورد استفاده قرار گرفته‌است. بعضی اوقات تعداد زیادِ حالات پایهٔ جدا از هم که درخورِ پیاده‌سازی مستقل هستند به روش‌های ایجاد می‌شوند. 
 برای بعضی مثال‌ها بازگشت انشعابی ممکن است یک مسئله را بارها ارزیابی کند. در چنین مواردی ممکن است شناسایی و ذخیرهٔ راه حل‌های این زیرمسئله‌های مشابه، خالی از لطف نباشد. این روش به « » معروف بوده و روشی معمول و شناخته‌شده می‌باشد. این شیوه به الگوریتم‌های تقسیم و حل مانند و منجر می‌شود.
{"title": "الگوریتم تقسیم و حل", "link": "https://fa.wikipedia.org//w/index.php?title=%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AA%D9%82%D8%B3%DB%8C%D9%85_%D9%88_%D8%AD%D9%84&oldid=34996258", "language": "fa"}