گاهی اوقات، با مسئله ای روبرو میشویم که به قدری پیچیده به نظر میرسد که هیچ راه حلی برای آن به ذهن مان نمیرسد. در اینچنین موقعیت هایی معمولا باید از استراتژی تقسیم و حل استفاده کنیم. استراتژی تقسیم و حل به ما کمک میکند که مسائل بزرگ را تبدیل به مسائل کوچک تر کنیم و بعد آنها را حل کنیم.
استراتژی تقسیم و حل، یک الگوریتم نیست که بتوانیم آن را برای حل مسئله مان، پیاده سازی کنیم، تقسیم و حل یک طرز فکر است که ما کمک میکند مسائل پیچیده را بهتر تحلیل کنیم. اگر بخواهیم به طور خلاصه بگوییم استراتژی تقسیم و حل، از دو مرحله تشکیل شده است، در مرحله اول باید بفهمیم که ساده ترین حالت مسئله چیست؟ فرض کنید میخواهیم الگوریتمی بنویسیم که یک لیست از اعداد بگیرد و حاصل ضرب آنها را برای ما حساب کند. ساده ترین حالت این مسئله چیست؟ ساده ترین حالت این است که لیست ما فقط یک عدد داشته باشد. در این صورت همان عدد، جواب مسئله خواهد بود.
مرحله دوم این است که بفهمیم چطور مسئله را خرد کنیم تا جایی که یه ساده ترین حالت برسیم؟ برگردیم به مثال قبلی. اگر لیست ما بیشتر از یک عدد داشت چطور آن را خرد کنیم؟ کافیست یک عدد از مجموعه برداریم و آن را در حاصل ضرب بقیه اعداد ضرب کنیم. مسئله ما یک مرحله ساده تر شد، حالا کافیست حاصل ضرب مجموعه کوچک تر را حساب کنیم. و همین روش را ادامه میدهیم تا جایی که به ساده ترین حالت مسئله برسیم یعنی جایی که لیست ما فقط یک عدد داشته باشد.
در ادامه مطلب، مثال های کاربردی تری از استراتژی تقسیم و حل را بررسی میکنیم.
روش تقسیم و حل به ما این امکان را میدهد که مسائل پیچیده را به ریزمسئله های کوچک تر تقسیم کنیم و سپس آنها را حل کنیم، این روش مزایای زیادی برای ما دارد که در ادامه به آنها اشاره میکنیم.
مهم ترین ویژگی این روش، این است که میتواند مسائل پیچیده را ساده تر کند، در نتیجه طراحی الگوریتم و پیاده سازی آن الگوریتم در کد، به مراتب ساده تر خواهد شد.
با تقسیم مسئله به مسائل کوچک تر، کد برنامه قابل فهم تر و خوانا تر خواهد شد، به دلیل اینکه هر بخشی از کد، در واقع یک مسئله کوچک را حل میکند و به سادگی قابل پیاده سازی است. خوانایی کد باعث میشود که اگر برنامه نویس دیگری بخواهد کدهای ما را بخواند، به راحتی متوجه آن شود.
با تقسیم کردن مسئله به بخش های کوچک، میتوانیم بخش های کوچک مسئله را به طور موازی اجرا کنیم، این کار باعث میشود که بتوانیم از تمام ظرفیت سیستم به صورت بهینه استفاده کنیم، در نتیجه الگوریتم با سرعت بیشتری اجرا خواهد شد.
در ابتدای مقاله توضیح دادیم که روش تقسیم و حل از دو مرحله تشکیل شده است، پیدا کردن ساده ترین حالت و خرد کردن مسئله تا جایی که به ساده ترین حالت برسد. در این قسمت میخواهیم با بررسی دو مثال کاربردی، این مطلب را بهتر درک کنیم.
فرض کنیم که میخواهیم الگوریتمی بنویسیم تا برج هانوی را، با هر تعداد دیسکی حل کند، به نظر میرسد که این مسئله کمی پیچیده است، پس بهتر است که از استراتژی تقسیم و حل، استفاده کنیم. ساده ترین حالت برج هانوی چیست؟ ساده ترین حالت این است که ما فقط بخواهیم یک دیسک را جابجا کنیم، در این صورت مستقیما آن را به ستون هدف میبریم.
مرحله دوم این است که بفهمیم چطور حالت های پیچیده تر را خرد کنیم تا به حالت پایه برسیم؟ فرض کنیم بخواهیم 5 دیسک را جابجا کنیم، در این صورت ابتدا باید چهار دیسک بالایی را، به ستون وسط بیاوریم، دیسک پنجم را به ستون هدف بیاوریم و بعد از آن مجددا چهار دیسک دیگر را به ستون هدف بیاوریم. در واقع با این کار ما مسئله را یک مرحله کوچک تر کردیم و الان کافیست بدانیم که چطور 4 دیسک را جابجا کنیم، همین کار را باید تکرار کنیم تا جایی که به ساده ترین حالت برسیم. کد این الگوریتم در زبان C# به صورت زیر خواهد بود.
یکی از الگوریتم های معروف مرتب سازی، Quick Sort است که از استراتژی تقسیم و حل استفاده میکند. برای اینکه یک آرایه را از روش تقسیم و حل مرتب کنیم، اول باید بدانیم که ساده ترین حالت آن چیست؟ ساده ترین حالت برای مرتب سازی یک آرایه، این است که فقط یک عضو داشته باشد، اگر تعداد اعضای آرایه، بیشتر باشد باید مسئله را ساده تر کنیم. روش ساده کردن، به این صورت است که یکی از اعضا را به صورت اتفاقی انتخاب میکنیم، سپس اعضای کوچک تر آن را در یک آرایه و اعضای بزرگتر را در یک آرایه دیگر قرار میدهیم و دو آرایه کوچکتر را مرتب میکنیم. بعد از این که دو آرایه کوچکتر را مرتب کردیم، آن عضو انتخاب شده را بین آن دو قرار میدهیم. این روش مرتب سازی در حالت میانگین از بقیه الگوریتم های مرتب سازی سریع تر خواهد بود.
استراتژی تقسیم و حل، یک ابزار قدرتمند برای تجزیه و تحلیل کردن مسائل پیچیده است که میتوانیم به وسیله آن الگوریتم های بهتری طراحی کنیم. استراتژی تقسیم و حل، سرعت الگوریتم ما را هم بالاتر خواهد برد، به دلیل اینکه به ما امکان اجرای موازی بخش های نرم افزار را میدهد.
در این مقاله ما با استراتژی تقسیم و حل، آشنا شدیم اما باید بدانیم که استفاده کردن از آن در حل مسائل نیاز به تمرین و کسب مهارت دارد.
خیلی ممنون از اینکه وقت گذاشتید و این مقاله رو مطالعه کردید، ممنون میشم نظرتون رو بهم بگید.
اگر این مطلب برایتان مفید بود، پیشنهاد میکنم سری مقالات الگوریتم و ساختمان داده را دنبال کنید.
منبع : سری مقالات الگوریتم و ساختمان داده در سایت خودم
