Posted: Wed Oct 02, 2019 11:52 pm Post subject: Divide And Conquer روشهای تقسیم و غلبه
پیدا کردن نزدیکترین جفت نقاط
پیداکردن نزدیکترین جفت نقاط در مجموعه ای به اسم Q که حداقل دو نقطه یا بیشتر عضو دراد.
نزدیکترین یعنی فاصله اقلیدسی .
ساده ترین روش این است که هر جفت دو نقطه را با هم مقایسه کنیم یعنی ترکیب 2 از n که پیچیدگی الگوریتم می شود teta(n^2)
اما در روش تقسیم و غلبه بصورت بازگشتی : T(n)=T(n/2)+O(n) باید بشود...
در مدرسان این مساله را در زیر مجموعه روش های تقسیم و غلبه اورده است در کتاب مرجع زیر مجموعه محاسبات هندسی امده است.
کاربرد مساله در تشخیص کنترل ترافیک هوایی یا دریایی آمده است. اینکه با پیداکردن این جفت نقطه احتمال خطر تصادف چقدر است
در مقدمه بحث به روش تقسیم و غلبه:
هرفراخوانی تابع بازگشتی در الگوریتم زیرمجموعه P و آرایه های X و Y را بعنوان ورودی دریافت میکند، که هر کدام شامل نقاط زیرمجموعه P میباشند. نقاط آرایه X مرتب شده هستند بنابراین در مختصات x بصورت صعودی امکان جستجو مهیاست.بهمین صورت آرایه Y نیز مرتب شده در نتیجه در مختصات y نیز بصورت یکنوای صعودی ذخیره شده است.دقت کنید برای اینکه پیچیدگی ما بیشتر ازO(nlogn) نشود نباید در هر فراخوانی بازگشتی مرتب سازی را انجام دهیم.اگر این کار را کنیم زمان اجرا می شود T(n)=T(n/2)+O(nlogn) که در نتیجه میشود O(nlog^2n)که( در ادامه بحث یاد خواهیم گرفت که چگونه به روش پیشمرتب کردن می توان از مرتب سازی در فراخوانی بازگشتی جلوگیری کرد.)
منبع صفحه 981 سی ال ار اس
Posted: Thu Oct 03, 2019 7:08 am Post subject: شرط خاتمه مرحله تقسیم در نزدیکترین جفت نقاط
درفراخوانی های بازگشتی در مرحله تقسیم مساله تازمانی به تقسیم ادامه می دهیم که تعدادنقاط P کمتر یا مساوی 3 شود. وقتی به این مرحله رسیدیم به روش معمولی که در بالا گفتیم یعنی انتخاب دو نقطه از 3 نقطه که دوتاحلقه تو درتو هست حل را انجام می دهیم.
تقسیم Divide
الگوریتم یک خط عمودی به نام l پیدا میکندکه نقاط P را به دو مجموعه Pl و Pr تقسیم می کند:
Pl=[P/2] و [Pr=[P/2
تمام نقاط Pl سمت چپ خط l و تمام نقاط Pr سمت راست خط l هستند.
آرایه X هم به دو زیر آرایه Xl وXr تقسیم میشودکه شامل نقاط Pl و Pr هستند. که بر اساس مختصات x بصورت صعودی در ارایه قرار می گیرند. در ارایه Y نیز بهمین ترتیب مختصات نقاط PlوPr هستند که براساس مقدارy در انجا مرتب هستند دو ارایه X و Y یک کپی از P هستند که بصورت کمکی براساس x و y مرتب شده اند
غلبه Conquer
با تقسیم P به Pl وPr دو فراخوانی بازگشتی داریم. یکی برای پیداکردن جفت نقاط در Pl و دیگری برایPr . ورودی ها به اولین فراخوانی Pl و Xl و Yl هستند. دومین فراخوانی نیز ورودی هایش Pr Xr Yr هستند. نزدیکترین جفت نقطه برای Pl را با dl و برای Pr را با dr و همینطور مینیموم این دو را با d نمایش می دهیم d=min(dl,dr)
ترکیب Combine
نزدیکترین جفت نقطه با فاصله ای معادل مقدار d که در بالا پیدا شده است یا در Pr هست یا در Pl . الگوریتم دنبال جفت نقطه ای می گردد که از d نیز کوچک باشد. یعنی نقطه ای که در شعاع خط l بطول d یا کمتر باشد.مطابق شکل کتاب. یعنی عرض 2d یک d سمت راست l و یک d سمت چپ خط l به این روش:
[list=]
1. یک ارایه به نام Y' که شامل نقاطی از Y هست که در شعاع 2d نیستند[/list]
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum