انفورماتیک و فروش لامپ ،ماژول و پروژکتور
یادداشت های مهندس مسعود نظامی
درباره وبلاگ


سید مسعود نظامی فارغ التحصیل مهندسی کامپیوتر - نرم افزار هستم.
هدف از راه اندازی این وبلاگ آن بود که مطالب جدید و مفید را برای دوستان در وبلاگ بگنجانم.
و فروش محصولات فوق کم مصرف لامپ ، ماژول و پروژکتور
تا چه قبول افتد و چه در نظر آید!
پنجشنبه 1387/09/21 :: 11:54 قبل از ظهر ::  نويسنده : مهندس مسعود نظامی

روش تقسیم و حل - ارائه شده توسط مهندس مسعود نظامی

 

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

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

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

 

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

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

 

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

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

 

3. ضرب استراسن

روش ضرب استراسن برای بهینه کردن عمل ضرب ماتریسها توسط شخص به نام استراسن معرفی شده است. در این روش هر کدام از ماتریسها به چهار زیر ماتریس تقسیم شده و عملیات ضرب با استفاده از آنها و رابطه هایی که استراسن عنوان کرده انجام می شود. با استفاده از این روش مرتبه اجرایی ضرب ماتریس از ( O( n3 به ( O( n2.8 کاهش پیدا می کند که در ماتریسهایی با ابعاد بزرگ افزایش سرعت چشمگیری ایجاد می کند. توضیحات بیشتر در مورد این روش را می توانید در مطلبی که قبلا ارائه شده مشاهده کنید.

 

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

با استفاده از روش تقسیم و حل می توان روشی بهینه تر از ضرب عادی چندجمله ای ها برای آن تعریف کرد. در این روش هم چند جمله ای ها به دو قسمت تقسیم شده و با استفاده از یک سری روابط، ضرب و جمع شده و نتیجه نهایی را می دهند. از همین روش با اندکی تغییر برای ضرب اعداد بسیار بزرگ هم می توان استفاده کرد که با اعمال آن، مرتبه ضرب از ( O( n2 به ( O( n1.58 کاهش پیدا می کند.

 

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

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

 

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

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

 

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

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

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

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

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

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

T( n ) = [ log2n ] + 1

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

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

 

پیاده سازی الگوریتم های Divide and Conquer:

در اکثر مواقع می توان الگوریتم های طراحی شده توسط روش تقسیم و حل را به صورت بازگشتی پیاده سازی کرد. چرا که هر کدام از زیر مساله ها یک مساله از همان نوع با پارامترهای متفاوت هستند. به عنوان مثال در مورد جستجوی دودویی، پیاده سازی بازگشتی روش به زبان C و ++C به این ترتیب است:

 

int BinarySearch ( int array [ ], int left, int right, int x )

{

  if ( left > right )

    return -1;

  int m = ( left + right ) / 2, result;

  if ( array[ m ] == x )

    result = m;

  else if ( array[ m ] > x )

    result = BinarySearch( array, left, m - 1, x );

  else

    result = BinarySearch( array, m + 1, right , x );

  return result;

}

 

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

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

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

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

 

int BinarySearch ( int array [ ], int n, int x )

{

  int left = 0, right = n - 1, m;

  while ( left <= right )

  {

    m = ( left + right ) / 2;

    if ( array[ m ] == x )

      return m;

    if ( array[ m ] > x )

      right = m - 1;

    else

      left = m + 1;

  }

  return -1;

}

 

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

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

نکته 3: زمانی که مساله را به چند زیر مساله تقسیم می کنیم، اگر تقسیم طوری باشد که هر زیر مساله خودش نزدیک به n ورودی داشته باشد الگوریتم اصلا کارا نخواهد بود.
 
 
تمامی حقوق این وبلاگ محفوظ است |طراحی : پیچک