بخشی از پاورپوینت
اسلاید 1 :
یکی از روش های حل مسئله ، تقسیم و حل است . اساس این روش به صورت حل بالا به پایین ( Top down ) است .در این روش مسئله ای با سایز بزرگ را آن قدر کوچک می کنیم که حل آن مقدور یا بدیهی شود . سپس از ترکیب زیر مسائل حل شده به حل مسئله اصلی می رسیم.
استفاده از این روش در طراحی الگوریتم ممکن است به یکی از دلایل زیر باشد :
.1حل مسئله با روش دیگری امکان پذیر نباشد
.2الگوریتم آن نسبت به روش های دیگر کارا تر باشد.
اما قبل از اعمال این روش باید به چند سوال پاسخ دهیم:
.1مسئله اصلی را به چند زیر مسئله تقسیم کنیم ؟
.2هر زیر مسئله چه سایزی داشته باشد؟ ( زیر مسائل هم اندازه باشند یا خیر؟ )
.3نوع شکستن (از بالا به پایین مسئله شکسته شود یا از پایین به بالا زیر مسائل کوچکتر ترکیب شوند.)
اسلاید 2 :
الگوريتم كلي تقسيم و حل :
الگوريتم DandC در آغاز به صورت DandC (P) فراخواني مي شود . كه در آن P مسئله اصلي است كه مي بايست حل شود . Small(P) بررسي مي كند كه مسئله به اندازه كافي كوچك است كه بتوان آنرا مستقيماً حل كرد يا خير . اگر نتيجه كار مثبت باشد زير مسئله P محاسبه مي شود .) مثلاً توسط تابعي به نام S(P) ) .
در غير اين صورت مسئله P به زيز مسئله هاي كوچكتر تقسيم مي شود . حاصل اينكار توليد زير مسئله هاي , P2 , P1 ... , Pk مي باشد كه حاصل بازگشت هاي پي در پي مي باشد . در نهايت تابع Combine براي تركيب راه حل هاي زير مسئله براي محاسبه راه حل مسئله اصلي به كار مي رود .
اسلاید 3 :
جست و جوی دودویی
هدف این مسئله جست و جوی کلید در یک آرایه مرتب است .
در حل این مسئله از روش تقسیم و حل استفاده می شود به صورتی که ابتدا یک آرایه n عنصری رابه دو قسمت مساوی تقسیم کرده و کلیدرابا عنصر وسط آرایه مقایسه می کنیم اگر مساوی بود که مسئله حل شده است در غیر این صورت با توجه به کوچک تر یا بزرگ تر بودن کلید این روند را در یکی از نیم آرایه های چپ یا راست ادامه می دهیم.
الگوریتم جست و جوی دودویی به روش بازگشتی را در ادامه پس از مثال مشاهده می کنید .
اسلاید 4 :
بررسی مرتبه زمانی الگوریتم جست و جوی دودویی
در این مسئله ،یک آرایه n عنصری را با انجام یک مقایسه به دو زیر مسئله دیگر تقسیم می کنیم اما فقط یکی از این زیر مسائل را حل می کنیم بنابراین داریم
- T) n ( = T ) n /2 ( +1 O ) logn (
اسلاید 5 :
مسئله 1
اگر در مسئله جست وجوی کلید ، آرایه را به k قسمت تقسیم کنیم مقدار k را برای بهینه شدن مرتبه زمانی به دست آورید؟
اسلاید 6 :
حل
اگر مسئله را به k قسمت مساوی تقسیم کنیم داریم :
- T) n ( = T) n/k ( + k-1
- O) lognk (
اما ضریب log nk در مرتبه زمانی برای ما اهمیت دارد. با توجه به اینکه در هر سطح از درخت جست و جو در بدترین حالت نیاز به k-1 مقایسه داریم در نتیجه ضریب مرتبه زمانی برابر k-1 است .
- T) n ( = ) k-1( lognk = ) k-1(
با توجه به اینکه k یک عدد طبیعی است و با افزایش آن میزان رشد k-1 بیشتر از log k است در نتیجه هر چه k کوچک تر باشد مرتبه زمانی کمتر خواهد بود . پس با توجه به اینکه 2≤k≤n ، k بهینه برابر 2 است.
اسلاید 7 :
مسئله 2
آیا برابر بودن سایز زیر مسائل در کمتر شدن مرتبه زمانی مسئله جست و جوی کلید مفید است یا خیر؟
اسلاید 8 :
حل
اگر آرایه را به دو قسمت با سایز های مختلف تقسیم کنیم احتمال اینکه کلید مورد نظر در قسمت بزرگ تر قرار بگیرد بیشتر است. در نتیجه ما مجبوریم در اکثر مراحل آرایه ای با سایز مثلا 70% ورودی را جستجو کنیم که این مناسب نیست زیرا در مسئله جست و جوی دودویی کلید ، در هر مرحله تنها 50% آرایه جستجو می شود .
اسلاید 9 :
مرتب سازی به روش D & C :
می خواهیم مسئله مرتب سازی را با استفاده از روش تقسیم و حل ، حل کنیم. به نحوی که در هر مرحله مسئله را به دو زیر مسئله دیگر تقسیم می کنیم .دراین مرتب سازی ابتدا عنصری را به عنوان محور در نظر گرفته سپس دو زیر مسئله تشکیل می دهیم به نحوی که یکی از این زیر مسائل حاوی عناصر کوچک تر از محور و دیگری حاوی عناصر بزرگ تر از محور با شد. زیر مسائل تشکیل شده را به روش مشابه حل می کنیم.
این روش مرتب سازی را مرتب سازی quick sort گویند .
اسلاید 10 :
مثال
در آرایه A عنصر10 را به عنوان عنصر محوری انتخاب می کنیم. با فراخوانی تابع Quick Sort تمام اعداد کوچکتر از عنصر محور (10) سمت چپ آن و اعداد بزرگتر از آن در سمت راست قرار می گیرند. سپس در آرایه سمت چپ و راست عناصر محوری انتخاب شده و برای هر کدام تابع Quick Sort فراخوانی می شود.
