الگوریتم تقسیم و غلبه، یک استراتژی برای حل یک مسئله بازگشتی بزرگ با مراحل زیر است:
- شکستن مسئله به مسائل فرعی کوچک‌تر
- حل مسائل فرعی
- رسیدن به خروجی مورد نظر با ترکیب مسائل فرعی
در این مقاله، نحوه عملکرد الگوریتم تقسیم و غلبه را خواهید آموخت، ما همچنین رویکرد تقسیم و غلبه را با سایر رویکردها و الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوان
در این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد‌ها برای حل یک مسئله بازگشتی مقایسه خواهیم کرد.
نحوه کار الگوریتم تقسیم و غلبه با مثال
مراحل کار الگوریتم تقسیم و غلبه به‌ترتیب عبارتند از:
- تقسیم: مسئله داده شده را با استفاده از روش بازگشتی به مسائل فرعی تقسیم کنید.
- غلبه: مسائل فرعی کوچک‌تر را به صورت بازگشتی حل کنید. اگر مسئله فرعی به اندازه کافی کوچک است، آن را مستقیماً حل کنید.
- ترکیب: راه‌حل‌های مسائل فرعی را که بخشی از فرآیند بازگشتی هستند، برای حل مسئله واقعی ترکیب کنید.
اجازه دهید این مفهوم را با کمک یک مثال درک کنیم:
در این مثال، یک آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100
در این مقاله موارد زیر بررسی شده است : 1- آرایه چیست 2- انواع اندیس گذاری در آرایه 3- انواع آرایه 4- محاسبه آدرس در آرایه 5- محاسبه شماره در آرایه 6- آرایه در برنامه نویسی 7- مزایای استفاده از آرایه را با استفاده از رویکرد تقسیم و غلبه مرتب می‌کنیم. فرض کنید آرایه داده شده، به شکل زیر باشد:
آرایه را به دو قسمت تقسیم می‌کنیم:
مجدداً، هر قسمت فرعی را به صورت بازگشتی به دو نیمه تقسیم می‌کنیم تا زمانی که عناصر جداگانه به دست آیند.
اکنون عناصر جداگانه را به‌صورت مرتب، ترکیب می‌کنیم. در این مرحله، غلبه و ترکیب را انجام دادیم. در مثال فوق توانستیم با استفاده از الگوریتم تقسیم و غلبه، یک آرایه با 6 عنصر را مرتب کنیم.
پیچیدگی زمانی
پیچیدگی زمانی الگوریتم تقسیم و غلبه با استفاده از قضیه مستر محاسبه می‌شود. فرم بازگشتی الگوریتم تقسیم و غلبه به شکل زیر است:
$\mathrm{T}\left(\mathrm{n}\right)\mathrm{=aT}\left(\frac{\mathrm{n}}{\mathrm{b}}\right)\mathrm{+f}\left(\mathrm{n}\right)$
به‌طوری که:
$\mathrm{n}$ = اندازه ورودی
$\mathrm{a}$ = تعداد زیرمسائل در بخش بازگشتی
$\frac{\mathrm{n}}{\mathrm{b}}$ = اندازه هر زیرمسئله، فرض بر این است که همه مسائل فرعی دارای اندازه یکسانی هستند.
$\mathrm{f}\left(\mathrm{n}\right)$ = هزینه کار انجام شده خارج از فراخوان بازگشتی، که شامل هزینه تقسیم مسئله و هزینه ادغام راه‌حل‌ها می‌شود.
نحوه حل این گونه مسائل به‌طور مفصل در مقاله قضیه مستر بررسی شده است و ما در این مقاله از این بحث صرف‌نظر می‌کنیم.
مقایسه تقسیم و غلبه با برنامه نویسی پویا
هم الگوریتم تقسیم و غلبه و هم برنامه نویسی پویا از بازگشت برای یافتن راه‌حل برای یک مسئله استفاده می‌کنند، اما هر دو ویژگی‌های متفاوتی دارند و در نتیجه مجموعه‌ای از مسائل متفاوت دارند. رویکرد تقسیم و غلبه یک مسئله را به زیر مسائل کوچک‌تر تقسیم می‌کند. این زیرمسائل بیشتر به صورت بازگشتی حل می‌شوند. در نتیجه هر زیرمسئله‌ای برای ارجاعات آینده ذخیره نمی‌شود، در حالی که در رویکرد برنامه نویسی پویا، نتیجه هر زیرمسئله برای ارجاعات آینده ذخیره می‌شود. زمانی که یک زیرمسئله یکسان چندین بار حل نشد از رویکرد تقسیم و غلبه استفاده کنید. از رویکرد پویا زمانی استفاده کنید که نتیجه یک زیرمسئله چندین بار در آینده مورد استفاده قرار گیرد. اجازه دهید این توضیحات را با یک مثال درک کنیم. فرض کنید می‌خواهیم سری فیبوناچیدنباله فیبوناچی یا سری فیبوناچی چیه؟ – آموزش اعداد فیبوناچی
این مقاله عالی دنباله فیبوناچی یا سری فیبوناچی را آموزش داده، سپس الگوریتم فیبوناچی و برنامه بازگشتی محاسبه nامین عدد فیبوناچی در پایتون و C را آورده است
را پیدا کنیم.
روش تقسیم و غلبه
fib(n)
If n 2, return 1
Else , return f(n - 1) + f(n - 2)روش پویا:
mem = []
fib(n)
If n in mem: return mem[n]
else,
If n 2, f = 1
else , f = f(n - 1) + f(n - 2)
mem[n] = f
return fدر روش برنامه نویسی پویا، mem نتیجه هر زیرمسئله را ذخیره می‌کند.
کاربردهای تقسیم و غلبه
از کاربردهای تقسیم و غلبه می‌توان به موارد زیر اشاره کرد:
- جستجوی دودویی: الگوریتم جستجوی دودویی یک الگوریتم جستجو است که با مقایسه مقدار هدف با عنصر میانی موجود در یک آرایه مرتب شده کار می‌کند. پس از انجام مقایسه، اگر مقدار متفاوت باشد، نیمه‌ای که نمی‌تواند هدف را داشته باشد در نهایت حذف می‌شود و به دنبال آن جستجو در نیمه دیگر ادامه می‌یابد. ما دوباره عنصر میانی در آرایه جدید را در نظر می‌گیریم و آن را با مقدار هدف مقایسه می‌کنیم. این فرآیند تا رسیدن به مقدار هدف تکرار می‌شود. اگر بعد از پایان جستجو متوجه شدیم که نیمه بعدی خالی است، می‌توان نتیجه گرفت که هدف در آرایه وجود ندارد.
- کارآمدترین الگوریتم مرتب سازی است: این الگوریتم مرتب سازی با انتخاب یک مقدار محوری از یک آرایه و سپس تقسیم بقیه عناصر آرایه به دو آرایه فرعی شروع می‌شود. پارتیشن با مقایسه هر یک از عناصر با مقدار محوری ساخته می‌شود و آن را مقایسه می‌کند که آیا عنصر دارای مقدار بیشتر یا کمتر از Pivot است و سپس آرایه‌ها را به صورت بازگشتی مرتب می‌کند.
- یک الگوریتم مرتب سازی است که یک آرایه را با مقایسه مرتب می کند: با تقسیم یک آرایه به آرایه فرعی شروع می‌شود و سپس به صورت بازگشتی هر یک از آنها را مرتب می‌کند. پس از انجام مرتب‌سازی، آنها را دوباره ادغام می‌کند.
- نزدیکترین جفت نقطه: مسئله هندسه محاسباتی است. این الگوریتم بر یافتن نزدیکترین جفت نقطه در یک فضای متریک، با توجه به n نقطه تأکید دارد، به طوری که فاصله بین جفت نقطه باید حداقل باشد.
- الگوریتم استراسن: این الگوریتم، الگوریتمی برای ضرب ماتریسماتریس در ساختمان داده⚡️معرفی انواع ماتریس (خلوت،قطری)
این مقاله عالی گفته ماتریس چیست و به آموزش ماتریس پرداخته، همچنین انواع ماتریس از جمله ماتریس خلوت، ماترس قطری و ماتریس های بالا و پایین مثلثی را معرفی کرده
است که به نام Volker Strassen نام‌گذاری شده است. زمانی که روی ماتریس‌های بزرگ کار می‌کند، ثابت شده است که بسیار سریع‌تر از الگوریتم سنتی است. - برج هانوی: برج هانوی یکی از بزرگ‌ترین معماهای ریاضی بود. اما الگوریتم تقسیم و غلبه با موفقیت توانسته آن را به صورت بازگشتی حل کند.
- الگوریتم تبدیل فوریه سریع کولی-توکی (FFT): الگوریتم تبدیل فوریه سریع به نام J. W. Cooley و John Turkey نام‌گذاری شده است. از رویکرد تقسیم و غلبه پیروی می‌کند و دارای پیچیدگی زمانی O(n Log n) است.
- الگوریتم کاراتسوبا برای ضرب سریع: یکی از سریع‌ترین الگوریتم‌های ضرب است که توسط آناتولی کاراتسوبا در اواخر سال 1960 اختراع شد و در سال 1962 منتشر شد. این الگوریتم دو عدد n رقمی را با کاهش آنها به اعداد 1 رقمی حل می‌کند.
مزایا و معایب تقسیم و غلبه
از مزایای الگوریتم تقسیم و غلبه می‌توان به موارد زیر اشاره کرد:
- پیاده‌سازی و درک آن آسان است.
- پیچیدگی زمانی الگوریتم را با تقسیم کردن مسئله به زیر مسائل کوچک‌تر کاهش می‌دهد.
- می‌توان از آن برای حل طیف گسترده‌ای از مسائل، از جمله مرتب‌سازی، جستجو و بهینه‌سازی استفاده کرد.
- می‌توان از آن در محاسبات موازی برای بهبود عملکرد استفاده کرد.
از معایب الگوریتم تقسیم و غلبه می‌توان به موارد زیر اشاره کرد:
- تعیین حالت پایه یا شرط توقف برای فراخوانی‌های بازگشتی می‌تواند دشوار باشد.
- ممکن است کارآمدترین الگوریتم برای همه مسائل نباشد.
- ممکن است به حافظهحافظه در کامپیوتر، همه چیز در مورد حافظه در معماری کامپیوتر
در این مقاله به بررسی کامل حافظه در کامپیوتر، انواع حافظه در کامپیوتر، کش، روش‌های آدرس دهی کش، نگاشت آدرس و موارد دیگر می‌پردازیم بیشتری نسبت به سایر الگوریتم‌ها نیاز داشته باشد زیرا شامل ذخیره‌سازی نتایج میانی است.
جمع‌بندی
در این مقاله نحوه کارکرد الگوریتم تقسیم و غلبه را توضیح دادیم و برخی کاربردهای آن‌را بررسی کردیم. همین‌طور درباره نحوه نمایش فرمول بازگشتی برای مسائلی که توسط الگوریتم تقسیم و غلبه حل می‌شوند، صحبت کردیم. در ادامه به کاربردهای این الگوریتم اشاره کردیم و آنها را به‌طور خلاصه شرح دادیم. و در نهایت به بررسی مزایا و معایب این الگوریتم پرداختیم.
الگوریتم تقسیم و غلبه چیست؟
الگوریتم تقسیم و غلبه، استراتژی حل یک مسئله بزرگ با شکستن مسئله به زیرمسائل کوچک‌تر، حل زیرمسائل و ترکیب آنها برای به دست آوردن خروجی مورد نظر است.
تفاوت الگوریتم تقسیم و غلبه با برنامه نویسی پویا چیست؟
تفاوت اصلی این است که در تقسیم و غلبه، مسئله را به قطعات کوچک‌تر تقسیم می‌کنید و سپس هرکدام را جداگانه حل می‌کنید، در حالی که در برنامه نویسی پویا، مسئله را به قطعات کوچک‌تر تقسیم می‌کنید و سپس هرکدام را با هم حل می‌کنید.
اصلی‌ترین مشکل الگوریتم تقسیم و غلبه چیست؟
زیرمسائل بازگشتی بخش اصلی الگوریتم‌های تقسیم و غلبه است. از این رو به مدیریت حافظه فشرده نیاز دارد. این فضا ممکن است توسط یک پشته بیش از حد مورد استفاده قرار گیرد. اگر فراخوانی بازگشتی به شدت فراتر از پشته CPU انجام شود، سیستم حتی ممکن است از کار بیفتد.
چرا الگوریتم تقسیم و غلبه از بقیه الگوریتم ها سریع‌تر است؟
روش تقسیم و غلبه، درجه پیچیدگی زمانی را کاهش می‌دهد، زیرا مسئله را به زیرمسائلی تقسیم می‌کند که به راحتی قابل حل هستند و معمولاً سریع‌تر از سایر الگوریتم‌ها اجرا می‌شوند.
کاربردهای الگوریتم تقسیم و غلبه چیست؟
از کاربردهای الگوریتم تقسیم و غلبه می‌توان به این موارد اشاره کرد: جستجوی دودویی، مرتب‌سازی سریع، مرتب‌سازی ادغامی، پیدا کردن نزدیکترین جفت نقطه‌ها، الگوریتم استراسن و برج هانوی
