الگوریتم تقسیم و حل: تفاوت میان نسخه‌ها

هنگام پی ریزی یک الگوریتم بازگشتی، باید:

 

بازگشتی اجازه بیان راه حل یک مسئله را به‌طور مختصر و مفید می‌دهد. مسئله‌ای که به صورت بازگشتی حل می‌شود باید بتواند به مسائل کوچک‌تر تقسیم بشود و حل مسائل کوچک به همان روش مسئله بزرگ قابل انجام باشد. مسئله کوچک‌تر به مسئله کوچک‌تری شکسته می‌شود تا سرانجام یه کوچک‌ترین اندازه مسئله برسد که base case نامیده می‌شود که می‌تواند بدون استفاده از بازگشتی حل شود.

 

۱- تقسیم آرایه به دو زیر آرایه، هر یک با n/2 عنصر.

 

=== پشته کردن صریح ===

Dالگوریتم‌های تقسیم و حل هم‌چنین می‌توانند به واسطهٔ یک برنامهٔ غیربازگشتی که زیرمسئله‌های جزیی را در بعضی داده‌ساختارهای صریح همانند [[پشته]]، [[صف]]، یا [[صف اولویت‌دار]]، ذخیره می‌کند، پیاده‌سازی شوند. این راهبرد آزادی بیشتری در انتخاب زیرمسئله‌ای که در قرار است در مرحلهٔ بعد حل شود، می‌دهد، ویژگی ای که در بعضی از برنامه‌های کاربردی دارای اهمیت می‌باشد. همانند متد [[رابطه بازگشتی ابتدا در عرض|رابطهٔ بازگشتی ابتدا در عرض]] در [[انشعاب و تحدید]] برای بهینه‌سازی عملکرد. این راهبرد، هم‌چنین راه‌حل استاندارد زبان‌های برنامه‌نویسی‌ای می‌باشد که از روال‌های بازگشتی پشتیبانی نمی‌کنند.

=== به اشتراک گذاری زیرمسئله‌های تکراری ===

در بعضی مسائل، بازگشت انشعابی، ممکن است به ارزیابی یک زیرمسئله در دفعات زیاد، پایان دهد. در چنین مواردی ممکن است شناسایی و ذخیرهٔ راه حل‌های این زیرمسئله‌های مشابه، خالی از لطف نباشد، که این روش به «[[به خاطرسپاری]]» معروف بوده و روشی معمول و شناخته‌شده می‌باشد. این شیوه به الگوریتم‌های تقسیم و حل [[از پایین به بالا]] مانند [[برنامه‌نویسی پویا]] و [[تجزیه و تحلیل نمودار]] منجر می‌شود.

* [[تفرقه بینداز و حکومت کن]]

== منابع ==

{{پانویس|۲}}