بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     نوشته‌های پربازدید اخیر

»    محاسبه‌ی دترمینان ماتریس

»    اشاره‌گرها در زبان ++C

»    حلقه‌های تکرار در ++C

»    معمای هشت وزیر

»    الگوریتم جستجوی اول سطح (BFS)

»    مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 406

»    درخت جستجوی دودویی

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
روش تقسیم و غلبه - الگوریتمستان
الگوریتمستان
6914.285.00
  »  

       

آشنایی با روش Divide and Conquer (تقسیم و حل / تقسیم و غلبه) و کاربردهای آن در مرتب‌سازی، جستجو و حل مسائل الگوریتمی دیگر

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «روش تقسیم و حل» تیر ماه 1387 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


یکی از روش‌های پرکاربرد و محبوب برای طراحی الگوریتم‌ها روش Divide and Conquer است که در زبان فارسی به صورت تقسیم و حل یا تقسیم و غلبه ترجمه شده است.

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

    برای آشنایی بیشتر، چند الگوریتم که با روش حل و تقسیم پیاده‌سازی شده‌اند معرفی می‌شوند.

      

مرتب‌سازی سریع (Quick Sort)

  [بازگشت به فهرست]

در روش مرتب‌سازی سریع داده‌های ورودی را بر حسب یکی از عناصر به نام محور به دو قسمت نه لزوما هم‌اندازه تقسیم کرده و هر کدام را جداگانه مرتب می‌کنیم.

      

مرتب‌سازی ادغامی (Merge Sort)

  [بازگشت به فهرست]

در این روش نیز همانند روش مرتب‌سازی سریع داده‌ها به دو قسمت تقسیم می‌شوند. اما روش تقسیم کردن داده‌ها متفاوت است. طوری که قسمت‌های به دست آمده از تقسیم تقریبا هم‌اندازه هستند. پس از مرتب کردن زیر آرایه‌ها، با ادغام آنها آرایه‌ی اصلی به صورت مرتب‌شده حاصل می‌شود.

      

ضرب استراسن

  [بازگشت به فهرست]

روش ضرب استراسن برای بهینه کردن عمل ضرب ماتریس‌ها توسط شخصی به نام استراسن معرفی شده است. در این روش هر کدام از ماتریس‌ها به چهار زیرماتریس تقسیم شده و عملیات ضرب با استفاده از آنها و رابطه‌هایی که استراسن عنوان کرده انجام می‌شود. با استفاده از این روش مرتبه‌ی اجرایی ضرب ماتریس از $ O(n^3)$ به $ O(n^{2.8}) $ کاهش پیدا می‌کند که در ماتریس‌هایی با ابعاد بزرگ منجر به افزایش سرعت چشمگیری می‌شود.

      

ضرب چندجمله‌ای‌ها و ضرب اعداد بسیار بزرگ

  [بازگشت به فهرست]

با استفاده از روش تقسیم و حل می‌توان روشی بهینه‌تر از ضرب عادی چندجمله‌ای‌ها برای آنها تعریف کرد. در این روش چند‌جمله‌ای‌ها به دو قسمت تقسیم شده و با استفاده از یک سری روابط، ضرب و جمع شده و نتیجه‌ی نهایی را می‌دهند. از همین روش با اندکی تغییر برای ضرب اعداد بسیار بزرگ هم می‌توان استفاده کرد که با اعمال آن، مرتبه‌ی ضرب از $ O(n^2)$ به $ O(n^{1.58})$ کاهش پیدا می‌کند.

      

مسأله‌ی کاشی‌کاری (فرش کردن صفحه‌ی شطرنجی با موزاییک‌های L شکل)

  [بازگشت به فهرست]

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

      

مسأله‌ی تنظیم جدول مسابقات (تورنمنت)

  [بازگشت به فهرست]

شما را مسئول تهیه‌ی جدول مسابقات تیم‌های فوتبال محله کرده‌اند! این بازی‌ها به صورت دوره‌ای بوده و هر تیمی باید با تمام تیم‌های دیگر بازی کند. در ضمن هر تیم در روز تنها می‌تواند یک بازی انجام دهد. برای تهیه‌ی جدول مسابقات به صورت بهینه - که مسابقات در کوتاهترین زمان ممکن برگزار شود - الگوریتمی ابداع شده است که از روش تقسیم و حل استفاده می‌کند.

      

جستجوی دودویی (Binary Search)

  [بازگشت به فهرست]

برای یافتن عنصری در یک آرایه‌ی نامرتب چاره‌ای نداریم جز این که از روش جستجوی خطی استفاده کنیم. در این روش از ابتدای آرایه شروع کرده و تک‌تک عناصر را بررسی می‌کنیم، تا زمانی که به عنصر دلخواه برسیم. بنابراین اگر آرایه‌ی مورد نظر $n$ عنصر داشته باشد، مرتبه‌ی اجرایی روش جستجوی خطی $ O(n) $ خواهد بود. اما در مورد آرایه‌ی مرتب روش دیگری نیز وجود دارد: روش جستجوی دودویی.

    در جستجوی دودویی عنصر وسط آرایه را بررسی می‌کنیم. در صورتی که این عنصر همان عنصر مورد نظر باشد، جستجو تمام می‌شود. اگر نه، باید قسمت‌های راست و چپ عنصر وسط را که تقریبا به یک اندازه هستند مورد جستجو قرار دهیم. اما آیا لازم است هر دو سمت جستجو شود؟ چون آرایه مرتب شده است، عناصر کوچکتر از عنصر مرکز همگی در سمت چپ و عناصر بزرگتر در سمت راست آن قرار دارند (آرایه را مرتب شده‌ی صعودی در نظر گرفته‌ام). با توجه به این مسأله که عنصر مورد نظر ما کوچکتر از عنصر مرکزی آرایه است یا بزرگتر، تنها یکی از دو زیر آرایه را بررسی می‌کنیم. در نتیجه در هر مرحله بازه‌ی مورد جستجو نصف می‌شود.

    برای یافتن مرتبه‌ی اجرایی الگوریتم به این صورت عمل می‌کنیم: فرض کنید $ T(n)$ حداکثر تعداد مقایسه‌های لازم برای یافتن عنصر مورد نظرمان در میان n داده باشد. در روش جستجوی خطی $T(n) = n$ بود. در روش جستجوی دودویی ابتدا عنصر وسط را با عنصر مورد نظرمان مقایسه می‌کنیم. اگر عنصر یافت نشود، در مرحله‌ی بعد تنها یکی از دو زیر آرایه بررسی می‌شود که نصف کل عناصر را دارد. پس می‌توان نوشت:

      

\[T(n) = T (\frac{n}{2}) + 1 \]

  

    با حل این رابطه‌ی بازگشتی به عبارت زیر می‌رسیم:

  

\[T(n) = [log_2n] + 1 \]

  

    که در آن منظور از [] علامت جزء صحیح است. مرتبه‌ی اجرایی این الگوریتم $ O(log \; n) $ است که در مقایسه با $ O(n) $ در جستجوی خطی بسیار کارآمد است. به عنوان نمونه، برای یافتن عنصری در یک آرایه به طول یک میلیون، در بدترین حالت با استفاده از جستجوی خطی یک میلیون مقایسه و در جستجوی دودویی تنها بیست مقایسه نیاز است.

    نکته 1: ممکن است این سوال مطرح شود که هزینه‌ی مرتب کردن یک آرایه به مراتب بیشتر از هزینه‌ی جستجوی خطی است. چه لزومی به انجام این کار است؟ لیست قبول‌شدگان کنکور را در نظر بگیرید. این لیست پس از آماده شدن تنها یک بار بر اساس شماره‌ی داوطلبی مرتب شده و در سایت سازمان سنجش قرار می‌گیرد. پس از آن، طی چند روز میلیون‌ها مراجعه و جستجو در لیست برای مشاهده‌ی نتیجه صورت می‌گیرد. در این حالت مطمئنا هزینه‌ی چند میلیون جستجویی که انجام می‌شود، بسیار مهم‌تر از هزینه‌ی یک بار مرتب‌سازی آن است. بیشتر کاربردهای این روش جستجو هم در همین نوع داده‌ها است.

      

پیاده‌سازی الگوریتم‌های تقسیم و حل

  [بازگشت به فهرست]

در اکثر مواقع می‌توان الگوریتم‌های طراحی شده توسط روش تقسیم و حل را به صورت بازگشتی پیاده‌سازی کرد. چرا که هر کدام از زیرمسأله‌ها یک مسأله از همان نوع با پارامترهای متفاوت هستند.

    در مورد جستجوی دودویی، پیاده‌سازی بازگشتی روش به زبان برنامه‌نویسی ++C به این ترتیب است:

      

int BinarySearch_1(int arr[], int left, int right, int x){
  if(left > right){
    return -1;
  }
  int m = (left + right) / 2, result;
  if(arr[m] == x)
  {
    result = m;
  }
10   else if(arr[m] > x){
11     result = BinarySearch_1(arr, left, m - 1, x);
12   }
13   else{
14     result = BinarySearch_1(arr, m + 1, right , x);
15   }
16   return result;
17 }

  

    تابع فوق چهار پارامتر arr (آرایه‌ای که جستجو در آن انجام می‌شود)، left و right (مرزهای محدوده‌ای که جستجو باید در آن انجام شود) و x (عنصری که باید پیدا کنیم) را دریافت کرده و اندیس محلی که عنصر مورد نظر یافت شده بر می‌گرداند. به عنوان مثال اگر به دنبال عدد 78 در آرایه‌ی arr به طول هزار هستیم، باید تابع را به صورت زیر فراخوانی کنیم:

      

i = BinarySearch_1(arr, 0, 999, 78);

  

    مقدار i پس از بازگشت از تابع برابر اندیس محل عنصر 78 در آرایه خواهد بود. اگر این عنصر یافت نشود مقدار 1- بازگشت داده می‌شود.

    روش جستجوی دودویی پیاده‌سازی غیربازگشتی ساده‌تری هم دارد:

      

int BinarySearch_2(int arr[], int n, int x)
{
  int left = 0, right = n - 1, m;
  while(left <= right){
    m = (left + right) / 2;
    if (arr[m] == x){
      return m;
    }
    if(arr[m] > x){
10       right = m - 1;
11     }
12     else{
13       left = m + 1;
14     }
15   }
16   return -1;
17 }

  

    که در آن n تعداد عناصر آرایه است. مسلما سرعت اجرای این روش بیشتر از روش بازگشتی آن است. اما همیشه اینگونه نیست که پیاده‌سازی غیربازگشتی یک تابع سریعتر از پیاده‌سازی بازگشتی آن باشد.

      

    نکته 2: در معرفی روش تقسیم و حل عنوان کردم که اگر زیرمسأله به اندازه‌ی کافی کوچک باشد از این روش برای حل آن استفاده نمی‌کنیم. تعیین این اندازه - که به آن مقدار آستانه گویند - بر اساس روش طراحی الگوریتم و همینطور روش‌های دیگر موجود صورت می‌گیرد که بحث مفصلی را می‌طلبد.

      

    نکته 3: زمانی که مسأله را به چند زیرمسأله تقسیم می‌کنیم، اگر تقسیم طوری باشد که هر زیرمسأله خودش نزدیک به n ورودی داشته باشد، الگوریتم کارا نخواهد بود. نمونه‌ی چنین مسائلی محاسبه‌ی بازگشتی جمله‌ی nام دنباله‌ی فیبوناتچی است.


این نوشته آخرین بار در تاریخ دوشنبه، ۴ مرداد ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها
        بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه‌ی دترمینان ماتریس مربعی و پیچیده‌گی زمانی آنها
        معرفی کتاب Introduction to Algorithms: A Creative Approach
        آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C
        معرفی کتاب Introduction to Algorithms (ویراست سوم) به عنوان مرجع مباحث طراحی الگوریتم‌ها و ساختمان داده‌ها
        آشنایی با روش حریصانه و کاربردهای آن مانند مسأله‌ی خرد کردن پول
        معرفی کتاب Programming Challenges برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی یا معرفی پیوند دانلود فایل‌های صوتی، تصویری و اسلایدهای کلاس درس نویسنده
        آشنایی با روش مرتب‌سازی سریع، همراه با قطعه کدهای نمونه به زبان برنامه‌نویسی ++C
        معرفی کتاب Art of Programming Contest برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود نسخه‌ی الکترونیکی
        آشنایی با دنباله‌ی عددی کاتالان، کاربردها و روش پیاده‌سازی آن به زبان برنامه‌نویسی ++C
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» hediyeh

دوشنبه، ۲۷ دی ماه ۱۳۹۵، ساعت ۱۶:۲۹
salam lotf mikonid algoritme hesab kardane  miyangine n adad ro be raveshe taghsimo hal bezarid??

» علی اکبر

پنجشنبه، ۱۲ فروردین ماه ۱۳۹۵، ساعت ۰۴:۴۱
سلام
میشه لطف کنید مسئله کوله پشتی و همچنین مسئله تلسکوپ را به روش تقسیم و حل بذارید؟؟؟خیلی ممنون بابت سایت جامع شما

» nika

سه‌شنبه، ۱۹ فروردین ماه ۱۳۹۳، ساعت ۱۸:۴۷
سلام. اگه میشه برنامه کاشیکاری رو به زبان c++ بذارید. با تشکر

» مریم

جمعه، ۱ آذر ماه ۱۳۹۲، ساعت ۲۰:۳۰
سلام دوستان من جزوه کامل طراحی الگوریتم به روش پویا و ضرب زنجیره ای ماتریس ها رو  واسه این ترمم  لازم دارم  اگر سایتی رو میشناسید لطفا راهنمایی کنید
ممنونم

» فرزانه

شنبه، ۲۷ مهر ماه ۱۳۹۲، ساعت ۱۷:۳۴
سلام من سه تا سوال دارم:
1-چرا در جستجوی باینری آرایه رو به دو قسمت تقسیم میکنه در هر مرحله.چرا به سه قسمت تقسیم نمیکنه؟؟
2-چرا جستجوی باینری روی لیست نیمه مرتب هم جواب می دهد؟؟
3-چرا برای به دست آوردن خانه وسط آرایه وقتی شماره خانه ابتدا و انتها جمع میشود و بر 2 تقسیم میشود حد بالای عدد به دست آمده را در نظر گرفته و خانه وسط را پیدا میکنیم مثلا آرایه 5 عنصری
2.5= 2/(1+5)
و خانه 3 میشود خانه وسط چرا حد پایین را نمیگیریم یعنی 2 ؟؟؟

» فانوس

سه‌شنبه، ۲۳ مهر ماه ۱۳۹۲، ساعت ۱۹:۵۴
سلام
میشه در مورد مسئله تنظیم جدول مسابقات اطلاعات بیشتری بدید؟
ممنون

» يگانه

چهارشنبه، ۱۶ اسفند ماه ۱۳۹۱، ساعت ۲۳:۲۴
مطالبتان عاليه دستون درد نكنه06

» سیما

یکشنبه، ۳ دی ماه ۱۳۹۱، ساعت ۲۱:۳۲
سلام
من دنبال یه سوال با جواب هستم که این سوال بتونه به سه روش حریصانه ،داینامیک پروگرامینگ و تقسم و غلبه حل بشه . اگه می تونید کمکم کنید لطفا بهم ایمیل بدین .ممنون

» مریم

سه‌شنبه، ۳۰ آبان ماه ۱۳۹۱، ساعت ۱۲:۳۸
سلام استادمون 1پروژه بهم داده لطفا در حلش بهم کمک کنید.
دو الگوریتم مرتب سازی به روش ادغام و سریع با استفاده از تقسیم و غلبه رابه زبان دلخواه پیاده سازی کنید به هر کدام از این الگوریتم ها یک شمارنده برای شمارش تعداد تکرار عمل غالب و یک تایمر برای محاسبه زمان اجرای الگوریتم اضافه کنید.
پرکردن آرایه به صورت تصادفی و مرتب باشد.
نظر:
سایت خوبی دارید.

» az

یکشنبه، ۳۰ بهمن ماه ۱۳۹۰، ساعت ۱۲:۳۶
لطفا مسائل بیشتری را مورد بررسی قرار دهید ومطالب را زودتر بهن روزرسانی کنید

» sima

یکشنبه، ۲۷ آذر ماه ۱۳۹۰، ساعت ۱۷:۰۵
08ناز نفس08

» xman

جمعه، ۴ آذر ماه ۱۳۹۰، ساعت ۱۳:۳۰
با سلام و خسته نباشید
درخواست برنامه مجموعه اعداد صحیح  در ++c را دارم می خواستم می نواتید این برنامه را بنویسید

» میثم

سه‌شنبه، ۱۹ مهر ماه ۱۳۹۰، ساعت ۲۱:۳۱
سلام سری فیبوناچی و جستجوی ترتیبی را به روش تقسیم و غلبه می خواستم

» امل

پنجشنبه، ۱۵ اردیبهشت ماه ۱۳۹۰، ساعت ۱۷:۴۷
سلام
خیلی  مطالبتون به دردم خورد ازت متشکرم
میشه بیشتر در مورد حل معادلات بازگشتی اعم از همگن و نا همگن و با استفاده از متغیر مثال بگید و تو ضیح بدید ممنوناز لطفتون0606

» ali

جمعه، ۱۰ اردیبهشت ماه ۱۳۸۹، ساعت ۲۲:۰۹
سلام اگه حل المسائل طراحی دارید برام ارسال کنید یا ادرس بدید تا دانلود کنم با تشکر

» همتا

سه‌شنبه، ۱۷ فروردین ماه ۱۳۸۹، ساعت ۱۵:۱۰
سلام دوست عزیز
میشه یک راهنمایی در مورد اینکه چطور میشه توی ضرب استراسن  طول آرایه رو بصورت بازگشتی توی هر مرحله تعیین کرد بکنی؟ یعنی دست کاربر برای تعیین n در اول برنامه باز باشه؟ آخه من هرجا این ماتریسو دیدم 2*2 یا 4*4 نوشته شده بود1110


چهارشنبه، ۱۸ فروردین ماه ۱۳۸۹، ساعت ۱۹:۳۸
مسعود:
در زبان ++C می شه تابع رو با آرگومانی از نوع آرایه بدون طول - با طول نامشخص - تعریف کرد. کافیه یه آرگومان دیگه هم تعریف کنید که طول آرایه رو نگه داره. مثل ( int func( int arr[], int n
در حالتی که آرایه دو بعدی باشه، باید تعداد سطرها مشخص باشه. در این حالت می شه یه حداکثر برای تعداد سطرهای ماتریسهامون در نظر بگیریم، و اون عدد رو به عنوان تعداد سطر ماتریس ارسالی به تابع استفاده کنیم.

» ش.ف

یکشنبه، ۸ فروردین ماه ۱۳۸۹، ساعت ۲۰:۴۶
سلام دوست عزیز
اگر امکان داره در مورد الگوریتمی که بتونه حداقل فاصله بین دو نقطه از میان n نقطه رو پیدا کنه (به روش تقسیم و حل) کمی راهنمایی کنید.
(فقط خواهش می کنم یه کم سریع)

» پژمان

سه‌شنبه، ۱۸ اسفند ماه ۱۳۸۸، ساعت ۲۰:۲۷
با سلام. من روشي رو ابداع كردم كه ركورد استراسن رو تا 1 پايين مياره. سال 89 صداش در مياد.


سه‌شنبه، ۳ فروردین ماه ۱۳۸۹، ساعت ۲۲:۵۳
مسعود:
سال 89 شروع شده ها پژمان جان. بی صبرانه منتظر خبرش هستیم. 01

» هانیه

چهارشنبه، ۳۰ دی ماه ۱۳۸۸، ساعت ۱۵:۳۴
کسی میتونه الگوریتمی بنویسه یک عنصر تویه یک آرایه n*n پیدا کنه و مرتبه زمانیش کمتر از خطی باشه؟؟؟؟؟؟؟06


چهارشنبه، ۳۰ دی ماه ۱۳۸۸، ساعت ۱۵:۵۱
مسعود:
ترتیب چینش عناصر در آرایه شرط خاصی نداره؟

» شراره

پنجشنبه، ۱۹ آذر ماه ۱۳۸۸، ساعت ۱۰:۴۹
در حد راهنمایی باشه بسه

» شراره

پنجشنبه، ۱۹ آذر ماه ۱۳۸۸، ساعت ۱۰:۴۶
سلام به همگی
خواهش میکنم اگه کسی طریقه ی پیدا کردن آستانه مناسب برای ماتریس استراسن رو بلده خیلی فوری برام میل کنه
مرسی
فقط سریع

» mina

شنبه، ۲۳ آبان ماه ۱۳۸۸، ساعت ۲۲:۳۵
استادمون ازمون خواسته واسه فرش کردن صفحه شطرنج با vbبرنامه بنویسیم(بدون اینکه توضیحی بدن!!!!)
لطفا راهنمائیم کنید .ممنون!07

» 3پیده

سه‌شنبه، ۱۹ آبان ماه ۱۳۸۸، ساعت ۱۵:۱۱
سلام ، با تشکر از مطالب جالب شما،اگر امکان دارد الگوریتم شماره 5 را قرار دهید.   با تشکر


سه‌شنبه، ۱۹ آبان ماه ۱۳۸۸، ساعت ۱۵:۲۵
مسعود:
اگه فرصت مناسبی داشته باشم، حتما در مورد الگوریتم کاشی کاری مطلبی خواهم نوشت.