Y@SiN
10-06-2009, 11:48 PM
طراحی الگوریتم در این روش بدین صورت حاصل می‌شود که:
مورد اصلی مسئله‌ی داده شده برای حل را به چندین مورد کوچکتر (از همان نوع مورد اصلی) تقسیم می‌کنیم٬ سپس موارد کوچکتر را بطور مجزا حل و نتیجه حاصل از هر زیر مورد را با هم ترکیب کرده تا نتیجه مورد اصلی مسئله را بیابیم.
اگر تاکنون از روتینهای بازگشتی (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
الگوریتم بالا رو چگونه باید اصلاح کرد تا جوابگوی حالتی باشد که اسم وارد شده در فهرست موجود نیست؟ یا با عبارت متداول برای الگوریتمهای تقسیم و تسخیر، در چه مرحله‌ای این اصلاح صورت گرفته شود؟
مورد اصلی مسئله‌ی داده شده برای حل را به چندین مورد کوچکتر (از همان نوع مورد اصلی) تقسیم می‌کنیم٬ سپس موارد کوچکتر را بطور مجزا حل و نتیجه حاصل از هر زیر مورد را با هم ترکیب کرده تا نتیجه مورد اصلی مسئله را بیابیم.
اگر تاکنون از روتینهای بازگشتی (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
الگوریتم بالا رو چگونه باید اصلاح کرد تا جوابگوی حالتی باشد که اسم وارد شده در فهرست موجود نیست؟ یا با عبارت متداول برای الگوریتمهای تقسیم و تسخیر، در چه مرحله‌ای این اصلاح صورت گرفته شود؟