تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر

تقسیم و تسخیر <span dir=ltr>(Divide-and-Conquer)</span>

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

اگر تاکنون از روتینهای بازگشتی (Recursive Procedures) برای حل مسائل استفاده کرده باشید با روش کار تقسیم و تسخیر از پیش آشنایی دارید.

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

مثال 1: جستجوی دودویی (Binary Search)
در نظر بگیرید که فهرستی از اسامی و آدرسهای مرتبط به هر اسم داشته باشیم و این فهرست دارای N جفت اسم و آدرس باشد که به ترتیب حروف الفبا بر اساس اسم مرتب شده و در دو آرایه نگهداری شوند:

Names(1..N)

Numbers(1..N)

می‌خواهیم با دادن هر اسم٬ آدرس مربوط به اسم را بیابیم. در این مثال فرض می‌کنیم که هر اسم مورد پرسش حتما در آرایه وجود دارد تا الگوریتم و شرح آن را ساده‌تر کرده باشیم.

الگوریتم تقسیم و تسخیری که این مسئله را حل می‌کند٬ ساده‌ترین الگوریتم در این مدل الگوریتمی است که حاصل نگرشی بگونه زیر است:

اسم داده شده
یا
درست در وسط فهرست قرار دارد
یا
در نیمه بالایی فهرست (بالا)
یا
در نیمه پایینی فهرست (پایین)

چون فهرست مرتب شده است٬ پس شرط بالا در صورتی درست است که اسم داده شده کوچکتر از اسم قرارگرفته در قسمت میانی باشد. و شرط پایین در صورتی درست است که اسم داده شده بزرگتر از اسم قرارگرفته در قسمت میانی باشد.

این دید به مسئله٬ الگوریتم زیر را در پی خواهد داشت:

function Search(X: name;  Start, Finish: integer)  return address

  Middle: integer

begin

  Middle <- (Start + Finish) / 2

  if X = Names(Middle) then

    return Numbers(Middle)

  elseif X < Names(Middle) then

    return Search(X, Start, Middle - 1)

  else -- X > Names(Middle)

    return Search(X, Middle + 1, Finish)

  endif

end

الگوریتم بالا رو چگونه باید اصلاح کرد تا جوابگوی حالتی باشد که اسم وارد شده در فهرست موجود نیست؟ یا با عبارت متداول برای الگوریتمهای تقسیم و تسخیر، در چه مرحله‌ای این اصلاح صورت گرفته شود؟

مثال 2: بدست آوردن همه ترکیبهای مجموعه‌ای از عناصر (Permutations)
با چیدن اعداد 4 و 5 و 8 چه اعدادی می‌توان بدست آورد؟ با چیدن حروف الف و میم و لام در کنار هم چه واژه‌های می‌توان ساخت؟ شرح و الگوریتم حل این مسئله با روش تقسیم و تسخیر را قبلا در جواب پرسش یکی از دوستان در پست دیگری نوشته ام. لطفا به لینک زیر رجوع کنید:
http://www.barnamenevis.org/vi...?p=13185#13185

----------------------------------------------------------------------------------------------------------
تکنیکهای طراحی الگوریتم - مقدمه

با سلام

برای سوال اول :

function Search(X: name;  Start, Finish: integer)  return address 

  Middle: integer 

begin 



if( finish<start)or(x<start)or(x  >finish) then

return('موجود نبید')

else if



  Middle <- (Start + Finish) / 2 

  if X = Names(Middle) then 

    return Numbers(Middle) 

  elseif X < Names(Middle) then 

    return Search(X, Start, Middle - 1) 

  else -- X > Names(Middle) 

    return Search(X, Middle + 1, Finish) 

  endif 



endif

end

با تشکر از DelphiArea جهت توجه به این بخش :)

تا حدودی درسته! :wink:

دونستن اینکه پارامتر Start بزرگتر یا مساوی پارامتر Finish هست کافیه که بدونیم هنوز چیزی برای جستجو (تقسیم) داریم. بطور کلی در روش تقسیم و تسخیر وقتیکه دیگه مسئله قابل تقسیم نیست به معنی اینه که کار تموم شده و نوبت این رسیده که نتایج حاصل از حل زیر مسائل رو برای بدست آوردن نتیجه‌ی مسئله اصلی با هم ترکیب کنیم. به این مرحله مبنای بازگشت (Recursive Base) هم گفته می‌شه.

اما چرا گفتم که اصلاحی که انجام دادی تا حدودی درسته؟ پارامتر X که به روال فرستاده شده حاوی اسمی است که می‌خواهیم دنبالش بگردیم٬ در صورتی که پارامترهای Start و Finish عددی بوده و نشان دهنده بازه‌ای از آرایه هستند که باید جستجو در آن بازه صورت بگیرد. بنابر‌این منطقا" نمی‌توانیم X را با Start یا Finish مقایسه کنیم. جدا از اینکه نیازی هم به شروط بیشتر نیست.

function Search(X: name;  Start, Finish: integer)  return address  

  Middle: integer 

begin 

  if Start > Finish then

    return موجود نبید

  else 

    Middle <- (Start + Finish) / 2 

    if X = Names(Middle) then 

      return Numbers(Middle) 

    elseif X < Names(Middle) then 

      return Search(X, Start, Middle - 1) 

    else -- X > Names(Middle) 

      return Search(X, Middle + 1, Finish) 

    endif 

  endif 

end 

نقل قول:

---

نوشته شده توسط (امید)

با تشکر از DelphiArea جهت توجه به این بخش :)

---

خواهش می‌کنم٬ فقط دارم دست و پا شکسته انجام وظیفه می‌کنم.

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

در الگوریتم جستجوی بالا٬ ما در هربار نیمی از فهرست را که امکان وجود مورد جستجو در آن نبود، از رده خارج کردیم و جستجو را در نیمه دیگر ادامه دادیم.

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

و اما پرسش: آیا با افزایش تقسیمات زمان رسیدن به نتیجه کم می‌شود؟

----------------------------------------------------------------------------------------------------------

لطفا تنها خواننده مطالب نباشید و سعی کنید چیزی در پاسخ به این پرسش بنویسید. درست یا نادرست بودن جواب اصلا" مهم نیست٬ مهم درگیر شدن با مسئله و شنیدن همه نقطه نظرات هست.

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

درخت اقتباص شده بصورت ساختار گراف با n نود در میاد یه چیزی تو مایه ها ی ایندکس.

با سلام

فکر کنم با زیاد کردن تقسیمات تعداد دستورات IF هم بیشتر شود که در این صورت احتمالا سرعت تفاوت چندانی نخواهد کرد . ( دستور IF دستور سنگین و زمانبری می باشد ).
برای مثال در تقسیم به 3 قسمت ما 2 IF دیگر هم خواهیم داشت.یعنی در این صورت فرض کنید middle1,middle2 را داریم برای حالت اول که ببینیم x مساوی با middle1 است یا کوچکتر یا مساوی که 2 if داریم و اگر بزرگتر بود همین کار برای middle2 .

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

قبل از ادامه دادن بحث لازم بود که توضیحی رو در خصوص مقدمات تحلیل یک الگوریتم بگم. پس قبل از خواندن ادامه صحبتم لطفا "تحلیل مقدماتی الگوریتمها" رو بخوانید.

در مثال جستجوی دودویی، ظاهر امر اینجور نشون می‌ده که هر چی تعداد تقسیمها بیشتر باشه٬ در هر بار تلاش ناموفق٬ ما حجم بیشتری از فهرست رو کنار می‌گذاریم.

ببینیم اگر تعداد تقسیمات رو به اندازه طول فهرست (N) برسونیم چه حاصلی در بر داره. در این حالت در اولین ورود به روال باید جستجو رو تو یکی از N قسمت انجام بدیم و اگر این قسمت٬ قسمت مورد نظرمون نبود٬ باید جستجو رو در یک قسمت دیگه دنبال کنیم. خوب با این حساب در هر بار ما فقط یک قسمت از N قسمت رو کنار می‌گذاریم در صورتیکه وقتی تعداد تقسیمات کمتر بود قسمت کنار گذاشته شده بزرگتر بود.

در حقیقت با داشتن N قسمت جستجوی دودویی ما تبدیل میشه به یک جستجوی متوالی به صورت زیر:

function Search(X: name; N: Integer) return address is

begin

  for i := 1 to N loop

    if Names(i) = X then

      return Address(i)

   endif

end

همانطور که گفتید، تعداد تقسیمات و اندازه مسئله با هم در ارتباط هستند و برای داشتن یک الگوریتم تقسیم و تسخیر بهینه باید تعداد تقسیمات مناسب رو داشته باشیم.

خوب فعلا"مثال جستجوی دودوئی رو بگذارید کنار تا با مثالی یک کم کلی‌تر رابطه بین تعداد تقسیمات و اندازه‌ی مسئله رو دنبال کنیم تا ببینیم در چه شرایطی به الگوریتم سریعتری خواهیم رسید.

پرسش:

در نظر بگیرید که الگوریتمی داریم به نام A که می‌دانیم قادر است مسئله‌ای به اندازه‌ی N را در c N^2 مرحله حل کند (c ضرب در N به توان 2 و c عددی است ثابت). بعدا" الگوریتمی پیدا می‌کنیم به نام B که همان مسئله را بصورت زیر حل می‌کند:

1. هر مورد از مسئله را به 3 قسمت هر یک به اندازه N / 2 تقسیم می‌کند
2. 3 قسمت را حل می کند
3. نتایج حاصل را در d N مرحله ترکیب می‌کند (d ضرب در N و d عددی است ثابت)

فرض کنید که الگوریتم A برای حل زیر مسائل در مرحله 2 بکار می‌رود.

با استفاده از رابطه‌ی الگوریتمهای A و B ببینید کدام الگوریتم سریعتر است. و آیا سریعتر بودن یک الگوریتم نسبت به دیگری با اندازه‌ی مسئله رابطه دارد؟

مسئله‌ای که در پرسش پست قبلیم مطرح کردم الگوریتم محاسبه‌ی حاصل ضرب دو عدد n رقمی است.

ورودیها دو عدد N رقمی مثبت می‌باشند که به صورت زیر نمایش داده می‌شوند:
http://delphiarea.com/external/karatsuba/xy.gif
و خروجی یک عدد 2N رقمی خواهد بود که به صورت زیر نمایش داده می‌شود:
http://delphiarea.com/external/karatsuba/z.gif

طبق الگوریتمی که در مدرسه ابتدایی آموخته‌ایم برای برای بدست آوردن حاصل ضرب دو عدد، تک تک ارقام یک عدد را در عدد دیگر ضرب کرده و حاصلها را با هم جمع می‌کنیم تا حاصل ضرب نهایی دو عدد را بیابیم. این الگوریتم به <span dir=ltr>O(N^2)</span> مرحله برای ضرب دو عدد N رقمی نیاز دارد.

منظور از مرحله در عبارت بالا عملیات پایه‌‌ی ریاضی است که بر روی دو رقم (عدد تک رقمی) صورت می‌گیرد. مانند 3+4 یا 5*6.

در سال 1992 فردی به نام <span dir=ltr>A.A. Karatsuba</span> الگوریتم ضرب سریعتری به روش تقسیم و تسخیر یافت که به نام او الگوریتم ضرب کاراتسوبا <span dir=ltr>Karatsuba Multiplication</span> نامیده می‌شود. تعداد مراحل مورد نیاز این الگوریتم <span dir=ltr>O(N^(log 3))</span> یا به عبارتی <span dir=ltr>O(N^1.59)</span> است. الگوریتم کاراتسوبا برای تمام مبناهای عددی معتبر است.

حالا ببینیم این الگوریتم بر چه اساسی بدست آمده است. اعداد ورودی x و y را در نظر بگیرید:
http://delphiarea.com/external/karatsuba/xy.gif
واضح است که این دو عدد را می‌توان بصورت زیر هم نمایش داد:
http://delphiarea.com/external/karatsuba/xysum.gif
و نتیجه حاصل ضرب <span dir=ltr>z = x * y</span> را بصورت زیر بیان کرد:
http://delphiarea.com/external/karatsuba/zsum.gif

به عنوان مثال:
http://delphiarea.com/external/karatsuba/ex3.gif

حال فرض کنید که ما ارقام اعداد x و y را به دو قسمت تقسیم کنیم:
http://delphiarea.com/external/karatsuba/abcd.gif
اکنون می‌توانیم اعداد x و y را با استفاده از اعداد a و b و c و d به صورت زیر بیان کنیم:
http://delphiarea.com/external/karatsuba/xyabcd.gif

با این نگرش به اعداد x و y حاصل ضرب آنها را می‌توانیم به صورت زیر بدست آوریم:
http://delphiarea.com/external/karatsuba/xyzabcd.gif
که در آن عبارتهای (a*c) و (a*d) و (b*c) و (b*d) حاصل ضرب دو عدد N/2 رقمی می‌باشند.

بدین ترتیب حاصل ضرب دو عدد x و y با استفاده از ترمهای a و b و c و d بدین صورت بیان می‌شود که:

1. دو عدد تک رقمی بی‌درنگ با هم ضرب می‌شوند. (مبنای بازگشت)
2. اگر <span dir=ltr>N > 1</span> بود در اینصورت حاصل ضرب دو عدد N رقمی می‌تواند بصورت ترمهایی از 4 عمل ضرب بر روی دو عدد N/2 رقمی بیان شود. (مرحله تقسیم و تسخیر)
3. برای محاسبه نتیجه حاصل ضرب اعداد x و y داده شده٬ تنها نیاز به جمع 4 حاصل ضرب بدست آمده در مرحله قبل (که در <span dir=ltr>O(N)</span> مرحله صورت می‌گیرد) و ضرب کردن در توانی از 10 هست (که این هم می‌تواند در <span dir=ltr>O(N)</span> مرحله صورت بگیرد٬ زیرا که تنها نیاز است به تعداد لازم صفر در انتهای عدد قرار گیرد). (مرحله ترکیب)

به عنوان مثال اگر داشته باشیم:

n = 4

x = 1026

y = 7329

در اینصورت خواهیم داشت:

a = 10

b = 26

c = 73

d = 29

پس اعداد x و y بصورت زیر قابل نمایش خواهند بود:
http://delphiarea.com/external/karatsuba/ex1.gif
و در نتیجه حاصل ضرب x و y بصورت زیر محاسبه خواهد شد:
http://delphiarea.com/external/karatsuba/ex2.gif

کاراتسوبا فهمید که می‌توان 4 عمل ضرب موجود در مرحله‌ی تقسیم و تسخیر الگوریتم ساده‌ی بالا را به 3 عمل ضرب کاهش داد. البته کاهش یک عمل ضرب در مرحله تقسیم و تسخیر باعث افزایش جزئی تعداد عملیات پایه در مرحله ترکیب می‌شود (هرچند باز به <span dir=ltr>O(N)</span> مرحله نیاز خواهد داشت).

چگونه 4 عمل ضرب می‌تواند به 3 عمل ضرب تبدیل شود؟ یک جایگزینی ساده. :idea:

U = a * c

V = b * d

W = (a + b) * (c + d)

با استفاده از U و V و W خواهیم داشت:

a * d + b * c = W - U - V

به همین سادگی 4 عمل ضرب به 3 عمل ضرب تبدیل شد و اکنون می‌توانیم حاصل ضرب دو عدد N رقمی x و y را بصورت زیر بیان کنیم:
http://delphiarea.com/external/karatsuba/xyzabcduvw.gif

الگوریتم ضرب کاراتسوبا بطور کامل:

function Karatsuba  (xunder, yunder : n-digit integer;   

                     n : integer)  

                     return (2n)-digit integer



a, b, c, d : (n/2)-digit integer

U, V, W : n-digit integer

begin

   if n = 1 then

      return x(0) * y(0)

   else

      a := x(n-1) ... x(n/2)

      b := x(n/2-1) ... x(0)

      c := y(n-1) ... y(n/2)

      d := y(n/2-1) ... y(0)

      U := Karatsuba ( a, c, n/2 )

      V := Karatsuba ( b, d, n/2 )

      W := Karatsuba ( a+b, c+d, n/2 )

      return U * 10^n + (W-U-V) * 10^(n/2) + V

   end if

end Karatsuba

خوب برگردیم سر پرسش بی‌جوابی که داریم:

در نظر بگیرید که الگوریتمی داریم به نام A که می‌دانیم قادر است مسئله‌ای به اندازه‌ی N را در c N^2 مرحله حل کند (c ضرب در N به توان 2 و c عددی است ثابت). بعدا" الگوریتمی پیدا می‌کنیم به نام B که همان مسئله را بصورت زیر حل می‌کند:

1. هر مورد از مسئله را به 3 قسمت هر یک به اندازه N / 2 تقسیم می‌کند
2. 3 قسمت را حل می کند
3. نتایج حاصل را در d N مرحله ترکیب می‌کند (d ضرب در N و d عددی است ثابت)

فرض کنید که در مرحله ٬2 از الگوریتم A برای حل زیر مسائل استفاده می‌شود.

می‌خواهیم با استفاده از رابطه‌ی الگوریتمهای A و B ببینیم کدام الگوریتم سریعتر است٬ و آیا سریعتر بودن یک الگوریتم نسبت به دیگری به اندازه‌ی مسئله رابطه‌ای دارد یا نه.

با استفاده از فرضیات بالا داریم:

T(A)(n) = c * (n^2)        طبق تعریف





T(B)(n) = 3 * T(A)(n/2) + d * n



        = 3 * (c * (n/2)^2) + d * n



        = (3/4) * (c * (n^2)) + d * n



        = (3/4) * T(A)(n) + d * n

با این حساب برای اینکه زمان اجرای B زمان اجرای A کمتر باشد، باید شرط زیر برقرار باشد:

d * n  <  (1/4) * T(A)(n)

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

d * n  <  (1/4) * (c * (n^2))



    d  <  (c * n) / 4



یا به عبارتی



    n  >  (4 * d) / c

پس برای مقادیری از N (اندازه مسئله) که N از 4d/c (که عددی است ثابت) بزرگتر است٬ الگوریتم B از الگوریتم A سریعتر خواهد بود.

با توجه به رابطه‌ی الگوریتم A و B براساس فقط مقدار ثابت 4d/c ٬ می‌توانیم بگوییم که اگر اندازه‌‌ی مسئله (N) به اندازه‌ی بزرگ بود که داشته باشیم:

n      >  4d/c

n/2    >  4d/c

n/4    >  4d/c



     . . .



n/i^2  >  4d/c

پیشنهاد می‌شود که از الگوریتم B بجای الگوریتم A استفاده شود و با تکرار الگوریتم B در این مرحله، هر زیر مسئله را به زیر مسائل کوچکتر تقسیم کرده و هرگاه اندازه‌ی زیر مسئله‌ای به مقدار N0 که مساوی یا کوچکتر از 4d/c است رسید٬ ادامه حل آن را با الگوریتم A دنبال کنیم.

شکل کامل یک الگوریتم تقسیم و تسخیر به صورت زیر نوشته می‌شود:

• اندازه‌ی مسئله (N)
• مقدار بحرانی اندازه‌ی مسئله که برای کمتر از آن تقسیمی صورت نمی‌گیرد. مقدار بحرانی را مقدار مبنا یا مبنای بازگشت هم میگویند. (N0)
• اندازه هر زیرمسئله که از تقسیم مسئلهی اصلی حاصل شده است. معمول این است که این اندازه بصورت نسبتی از اندازه‌ی‌ مسئله‌ اصلی به اندازه‌ی زیرمسائل بیان شود. (M)
• تعداد تقسیمات مسئله‌ی اصلی به زیرمسائل. (R)

procedure D-and-C (N : input size)

begin

  if N <= N0 then

    Solve problem without further sub-division

  else

    Split into R sub-instances each of size N/M

    for each of the R sub-instances do

      D-and-C (N/M)

    end for

    Combine the R resulting sub-solutions 

    to produce the solution to the original problem

  end if

end D-and-C

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

• تعداد زیرمسائلی که یک مسئله به آنها تقسیم شده تا بطور مجزا حل شوند. (a)
• نسبت اندازه‌ی مسئله اصلی به اندازه زیرمسائل. (b)
• تعداد مراحل مورد نیاز برای تقسیم مسئله اصلی و ترکیب نتایج حاصل از حل هر یک از زیرمسائل٬ که بصورت تابعی از n بیان شدنی است.

از آنجا که جواب مسئله اصلی از ترکیب جوابهای مسائل کوچکتر حاصل می‌شود و زمان اجرای این فرآیند به نوع مسئله مربوط است، زمان اجرا را بصورت یک چند جمله‌ای بصورت <span dir=ltr>O(n^k)</span> فرض می‌کنیم که در آن k مقداری بزرگتر یا مساوی صفر دارد. با این فرض و همچنین در حالتی که a و b هر دو ثابت باشند (همانند مثالهایی که در بالا داشتیم)، می‌توان زمان اجرای یک الگوریتم تقسیم و تسخیر را بصورت زیر بیان کرد:

       O(1)	               n <= n0

T(n) = 

       a . T(n/b) + O(n^k)   n > n0

با حل معادله بالا، زمان اجرای الگوریتم با تقریبی اندک (asymptotically) توسط فرمول زیر قابل محاسبه خواهد بود (*):

       O(n^k)                if  a < b^k



T(n) = O((n^k).(log[b]n)&#4  1;    if  a = b^k



       O(n^(log[b]a)))       if  a > b^k

اگر به چگونگی رسیدن به فرمول بالا علاقمندید، جزئیات آن در Running Time of Divide-and-Conquer Algorithms بیان شده است.

------------------
* عبارت <span dir=ltr>log[x]y</span> به معنی لگاریتم y در مبنای x است.

Kambiz عالی بود
خیلی ممنون از زحمتتان

با سلام
مي‌دانيد كه الگوريتم فيبوناچي يك الگوريتم تقسيم و حل محسوب مي‌شود و پيچدگي آن 2 به توان n/2 مي‌باشد خيلي سعي كردم با روش‌هايي به اين پيچيدگي برسم اما به بن بست رسيدم لطفا بدون استفاده از روش استقراء اين كار را برايم انجام دهيد.
با تشكر

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

1.برای اینکه دیگه اسمش باینری نمیشه.برای ۳ قسمت جست و جو کنید ternary search
2.جواب نمیده.
۳.چون اونطوری خانه وسط از قلم میافته.