طراحی الگوریتم روس تقسیم و حل

تعریف و نحوه عملکرد

روش تقسیم و حل، روشی در طراحی الگوریتم هاو یک تکنیک برنامه نویسی است. این روش یک روش بالا به پایین (به انگلیسی: [] Error: {{Lang}}: no text (کمک)) Top - down) است که در آن مسئله اصلی با استفاده از یک ساختار بازگشتی به زیر مسئله‌هایی تقسیم می‌شود که دقیقاً شبیه مسئله اصلی هستند با این تفاوت که از نظر اندازه کوچکتر یا ساده‌تر از مسئله اصلی هستند. این فرایند تقسیم چندان ادامه می‌یابد که حل زیر مسئله‌ها به راحتی امکان‌پذیر گردد، پس از مراحل تقسیم مسئله به زیر مسئله‌های کوچک ترو ساده‌تر با حل این زیر مسئله هاو ترکیب آن‌ها با هم می‌توان به یک جواب برای مسئله اصلی دست یافت. در هنگام تقسیم مسئله بزرگتر به مسائل کوچکتر باید تعداد تقسیمات را به گونه‌ای گرفت که کارایی بیشترین مقدار باشد، هرچه اندازه مسائل کوچک به هم نزدیک تر باشد معمولاً کارایی حاصل بیشتر است. بنابراین سعی می‌شود اندازه زیر مسائل تقریباً با هم مساوی باشد. با ذکر چند مثال طرز کار این روش در حل مسائل را بیشتر شرح می‌دهیم.

مثال

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

معایب این روش

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

۱. ↑کورمن، مقدمه‌ای بر الگوریتم‌ها.

۲. ↑نیپولیتان، طراحی الگوریتم‌ها.

منابع

نیپولیتان، ریچارد و کیومرث نعیمی پور. طراحی الگوریتم‌ها. ترجمه جعفرنژاد قمی. بابل:نشر علوم رایانه، ۱۳۹۰.

کورمن، توماس اچ. ، و دیگران. مقدمه‌ای بر الگوریتم‌ها. بابل:نشر علوم رایانه، ۱۳۸۹.