الگوریتمستان

یادداشت‌های یک معلم علاقه‌مند به نوشتن از آنچه آموخته و یاد می‌دهد
 

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

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

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

  

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

  [برگرد بالا]

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

  

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

  [برگرد بالا]

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

  

الگوریتم ضرب استراسن

  [برگرد بالا]

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

  

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

  [برگرد بالا]

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

  

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

  [برگرد بالا]

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

  

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

  [برگرد بالا]

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

  

جستجوی دودویی

  [برگرد بالا]

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

  

جستجوی دودویی

  

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

برای یافتن مرتبه اجرایی الگوریتم به این صورت عمل می‌کنیم: فرض کنید $ 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;

  }

  else if(arr[m] > x){

    result = BinarySearch_1(arr, left, m - 1, x);

  }

  else{

    result = BinarySearch_1(arr, m + 1, right , x);

  }

  return result;

}

  

تابع فوق چهار پارامتر 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){

      right = m - 1;

    }

    else{

      left = m + 1;

    }

  }

  return -1;

}

  

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

  

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

  

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

مسعود اقدسی فام

مسعود اقدسی فام هستم.

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

algs.ir/spa6si5     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
نوشته‌ها از این دست
آخرین نوشته‌ها
       ✦   الگوریتم آنلاین
نوشته‌های پرمخاطب
       ✦   برج هانوی
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک (محرمانه):

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• آرزو
۳۰ تیر ۱۳۸۷، ساعت ۱۲:۲۲

آره من خودم با همین روش برنامه می نویسم.... خیلی خوبه...

مرسی

• محسن
۵ مرداد ۱۳۸۷، ساعت ۱۴:۵۰

زمان اجری جستجوی خطی و دودیی را در یک آرایه 100000 عنصری بدست آورید... ممنون می شم کمکم کنید   mohsen_cool2005@yahoo.com

مسعود اقدسی فام
۵ مرداد ۱۳۸۷، ساعت ۱۶:۲۷

محسن جان مطمئنی مطلب رو با دقت خوندی؟؟؟

• رز
۲۰ فروردین ۱۳۸۸، ساعت ۰۹:۲۹

سلام من دانشجویی مهندسی کامپیوتر دانشگاه پیام نور زنجان هستم شما حتما می دونید دانشگاه پیام نور برخلاف دانشگاه های دیگه واقعا محروم هست من نمی دونم برای اینکه یک وضعیت خوبی برای مهندسی کامپیوتر داشته باشم چی کار باید بکنم؟ لطفا به من در این مورد که چه چیزهای رو باید بخونم کمک کنید. سایت شما به من خیلی کمک کرد ممنونم

• یاسی
۲۶ فروردین ۱۳۸۸، ساعت ۲۲:۱۴

SALAM LOTFAN ALGORITM KASHI KARI RO VASAM SEND KONID

MAMNON

• زهرا
۱۳ اردیبهشت ۱۳۸۸، ساعت ۱۵:۳۰

با سلام و خسته نباشید

اگه ممکن همین مسله n وزیر رو به دو روش تقسیم وحل و برنامه نویسی بویا توضیح بدید

با تشکر

• مهسا
۱۴ اردیبهشت ۱۳۸۸، ساعت ۱۳:۳۵

سلام من بايد برنامه بازي هاي دوره اي رو به زبان سي شارپ بنويسم ميتونيد كمكم كنين؟ممنون ميشم.اخه خيلي حياتي.

• آزاده برزگر
۱۹ اردیبهشت ۱۳۸۸، ساعت ۱۹:۲۳

مرتبه زمانی الگوریتم های زیر راه به چه روشی می توان حل نمود؟

              T(n) = T(n/5)  +T(n/2) +n

T(n) = T(n/2)  +T(n/3) +n      

T(n) =4 T(n/2)  + (n^2)/log (10)n

اگر می توانید در حل این مساله ها به من کمکی کنید لطفا تا دوشنبه برای من جواب را ارسال نمایید .

                                                                                                                                         با کمال تشکر

• غلامرضا
۲۱ اردیبهشت ۱۳۸۸، ساعت ۱۸:۰۱

با عرض سلام و خسته نباشید

لطفا درباره شیوه حل مساله کاشی کاری توضیح دهید . متشکرم.

• 3پیده
۱۹ آبان ۱۳۸۸، ساعت ۱۵:۱۱

سلام ، با تشکر از مطالب جالب شما،اگر امکان دارد الگوریتم شماره 5 را قرار دهید.   با تشکر

۱۹ آبان ۱۳۸۸، ساعت ۱۵:۲۵
• مسعود اقدسی فام

اگه فرصت مناسبی داشته باشم، حتما در مورد الگوریتم کاشی کاری مطلبی خواهم نوشت.

• mina
۲۳ آبان ۱۳۸۸، ساعت ۲۲:۳۵

استادمون ازمون خواسته واسه فرش کردن صفحه شطرنج با vbبرنامه بنویسیم(بدون اینکه توضیحی بدن!!!!)

لطفا راهنمائیم کنید .ممنون!07

• شراره
۱۹ آذر ۱۳۸۸، ساعت ۱۰:۴۶

سلام به همگی

خواهش میکنم اگه کسی طریقه ی پیدا کردن آستانه مناسب برای ماتریس استراسن رو بلده خیلی فوری برام میل کنه

مرسی

فقط سریع

• شراره
۱۹ آذر ۱۳۸۸، ساعت ۱۰:۴۹

در حد راهنمایی باشه بسه

• هانیه
۳۰ دی ۱۳۸۸، ساعت ۱۵:۳۴

کسی میتونه الگوریتمی بنویسه یک عنصر تویه یک آرایه n*n پیدا کنه و مرتبه زمانیش کمتر از خطی باشه؟؟؟؟؟؟؟06

۳۰ دی ۱۳۸۸، ساعت ۱۵:۵۱
• مسعود اقدسی فام

ترتیب چینش عناصر در آرایه شرط خاصی نداره؟

• پژمان
۱۸ اسفند ۱۳۸۸، ساعت ۲۰:۲۷

با سلام. من روشي رو ابداع كردم كه ركورد استراسن رو تا 1 پايين مياره. سال 89 صداش در مياد.

۳ فروردین ۱۳۸۹، ساعت ۲۲:۵۳
• مسعود اقدسی فام

سال 89 شروع شده ها پژمان جان. بی صبرانه منتظر خبرش هستیم. 03

• ش.ف
۸ فروردین ۱۳۸۹، ساعت ۲۰:۴۶

سلام دوست عزیز

اگر امکان داره در مورد الگوریتمی که بتونه حداقل فاصله بین دو نقطه از میان n نقطه رو پیدا کنه (به روش تقسیم و حل) کمی راهنمایی کنید.

(فقط خواهش می کنم یه کم سریع)

• همتا
۱۷ فروردین ۱۳۸۹، ساعت ۱۵:۱۰

سلام دوست عزیز

میشه یک راهنمایی در مورد اینکه چطور میشه توی ضرب استراسن  طول آرایه رو بصورت بازگشتی توی هر مرحله تعیین کرد بکنی؟ یعنی دست کاربر برای تعیین n در اول برنامه باز باشه؟ آخه من هرجا این ماتریسو دیدم 2*2 یا 4*4 نوشته شده بود1110

۱۸ فروردین ۱۳۸۹، ساعت ۱۹:۳۸
• مسعود اقدسی فام

در زبان ++C می شه تابع رو با آرگومانی از نوع آرایه بدون طول - با طول نامشخص - تعریف کرد. کافیه یه آرگومان دیگه هم تعریف کنید که طول آرایه رو نگه داره. مثل ( int func( int arr[], int n

در حالتی که آرایه دو بعدی باشه، باید تعداد سطرها مشخص باشه. در این حالت می شه یه حداکثر برای تعداد سطرهای ماتریسهامون در نظر بگیریم، و اون عدد رو به عنوان تعداد سطر ماتریس ارسالی به تابع استفاده کنیم.

• ali
۱۰ اردیبهشت ۱۳۸۹، ساعت ۲۲:۰۹

سلام اگه حل المسائل طراحی دارید برام ارسال کنید یا ادرس بدید تا دانلود کنم با تشکر

• امل
۱۵ اردیبهشت ۱۳۹۰، ساعت ۱۷:۴۷

سلام

خیلی  مطالبتون به دردم خورد ازت متشکرم

میشه بیشتر در مورد حل معادلات بازگشتی اعم از همگن و نا همگن و با استفاده از متغیر مثال بگید و تو ضیح بدید ممنوناز لطفتون0606

• میثم
۱۹ مهر ۱۳۹۰، ساعت ۲۱:۳۱

سلام سری فیبوناچی و جستجوی ترتیبی را به روش تقسیم و غلبه می خواستم

• xman
۴ آذر ۱۳۹۰، ساعت ۱۳:۳۰

با سلام و خسته نباشید

درخواست برنامه مجموعه اعداد صحیح  در ++c را دارم می خواستم می نواتید این برنامه را بنویسید

• sima
۲۷ آذر ۱۳۹۰، ساعت ۱۷:۰۵

08ناز نفس08

• az
۳۰ بهمن ۱۳۹۰، ساعت ۱۲:۳۶

لطفا مسائل بیشتری را مورد بررسی قرار دهید ومطالب را زودتر بهن روزرسانی کنید

• مریم
۳۰ آبان ۱۳۹۱، ساعت ۱۲:۳۸

سلام استادمون 1پروژه بهم داده لطفا در حلش بهم کمک کنید.

دو الگوریتم مرتب سازی به روش ادغام و سریع با استفاده از تقسیم و غلبه رابه زبان دلخواه پیاده سازی کنید به هر کدام از این الگوریتم ها یک شمارنده برای شمارش تعداد تکرار عمل غالب و یک تایمر برای محاسبه زمان اجرای الگوریتم اضافه کنید.

پرکردن آرایه به صورت تصادفی و مرتب باشد.

نظر:

سایت خوبی دارید.

• سیما
۳ دی ۱۳۹۱، ساعت ۲۱:۳۲

سلام

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

• يگانه
۱۶ اسفند ۱۳۹۱، ساعت ۲۳:۲۴

مطالبتان عاليه دستون درد نكنه06

• فانوس
۲۳ مهر ۱۳۹۲، ساعت ۱۹:۵۴

سلام

میشه در مورد مسئله تنظیم جدول مسابقات اطلاعات بیشتری بدید؟

ممنون

• فرزانه
۲۷ مهر ۱۳۹۲، ساعت ۱۷:۳۴

سلام من سه تا سوال دارم:

1-چرا در جستجوی باینری آرایه رو به دو قسمت تقسیم میکنه در هر مرحله.چرا به سه قسمت تقسیم نمیکنه؟؟

2-چرا جستجوی باینری روی لیست نیمه مرتب هم جواب می دهد؟؟

3-چرا برای به دست آوردن خانه وسط آرایه وقتی شماره خانه ابتدا و انتها جمع میشود و بر 2 تقسیم میشود حد بالای عدد به دست آمده را در نظر گرفته و خانه وسط را پیدا میکنیم مثلا آرایه 5 عنصری

2.5= 2/(1+5)

و خانه 3 میشود خانه وسط چرا حد پایین را نمیگیریم یعنی 2 ؟؟؟

• مریم
۱ آذر ۱۳۹۲، ساعت ۲۰:۳۰

سلام دوستان من جزوه کامل طراحی الگوریتم به روش پویا و ضرب زنجیره ای ماتریس ها رو  واسه این ترمم  لازم دارم  اگر سایتی رو میشناسید لطفا راهنمایی کنید

ممنونم

• nika
۱۹ فروردین ۱۳۹۳، ساعت ۱۸:۴۷

سلام. اگه میشه برنامه کاشیکاری رو به زبان c++ بذارید. با تشکر

• علی اکبر
۱۲ فروردین ۱۳۹۵، ساعت ۰۴:۴۱

سلام

میشه لطف کنید مسئله کوله پشتی و همچنین مسئله تلسکوپ را به روش تقسیم و حل بذارید؟؟؟خیلی ممنون بابت سایت جامع شما

• hediyeh
۲۷ دی ۱۳۹۵، ساعت ۱۶:۲۹

salam lotf mikonid algoritme hesab kardane  miyangine n adad ro be raveshe taghsimo hal bezarid??

• آندیا
۲۶ مهر ۱۳۹۷، ساعت ۱۰:۴۰

سلام لطفا اگه میشه برنامه الگوریتم تقسیم بندی و غلبه حل کرده رو بذارید ممنونم