ParsX.com
پذیرش پروژه از دانشجویی ... تا سازمانی 09376225339
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

Divide And Conquer روشهای تقسیم و غلبه

 
Post new topic   Reply to topic    ParsX.com Forum Index -> طراحي الگوريتم
View previous topic :: View next topic  
Author Message
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Wed Oct 02, 2019 11:52 pm    Post subject: Divide And Conquer روشهای تقسیم و غلبه Reply with quote

پیدا کردن نزدیکترین جفت نقاط
Arrow پیداکردن نزدیکترین جفت نقاط در مجموعه ای به اسم Q که حداقل دو نقطه یا بیشتر عضو دراد.

Ideaنزدیکترین یعنی فاصله اقلیدسی .
ساده ترین روش این است که هر جفت دو نقطه را با هم مقایسه کنیم یعنی ترکیب 2 از n که پیچیدگی الگوریتم می شود teta(n^2)
Evil or Very Mad اما در روش تقسیم و غلبه بصورت بازگشتی : T(n)=T(n/2)+O(n) باید بشود...

در مدرسان این مساله را در زیر مجموعه روش های تقسیم و غلبه اورده است در کتاب مرجع زیر مجموعه محاسبات هندسی امده است.
Idea کاربرد مساله در تشخیص کنترل ترافیک هوایی یا دریایی آمده است. اینکه با پیداکردن این جفت نقطه احتمال خطر تصادف چقدر است
در مقدمه بحث به روش تقسیم و غلبه:

هرفراخوانی تابع بازگشتی در الگوریتم زیرمجموعه P و آرایه های X و Y را بعنوان ورودی دریافت میکند، که هر کدام شامل نقاط زیرمجموعه P میباشند. نقاط آرایه X مرتب شده هستند بنابراین در مختصات x بصورت صعودی امکان جستجو مهیاست.بهمین صورت آرایه Y نیز مرتب شده در نتیجه در مختصات y نیز بصورت یکنوای صعودی ذخیره شده است.دقت کنید برای اینکه پیچیدگی ما بیشتر ازO(nlogn) نشود نباید در هر فراخوانی بازگشتی مرتب سازی را انجام دهیم.اگر این کار را کنیم زمان اجرا می شود T(n)=T(n/2)+O(nlogn) که در نتیجه میشود O(nlog^2n)که( در ادامه بحث یاد خواهیم گرفت که چگونه به روش پیشمرتب کردن می توان از مرتب سازی در فراخوانی بازگشتی جلوگیری کرد.)
منبع صفحه 981 سی ال ار اس
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Thu Oct 03, 2019 7:08 am    Post subject: شرط خاتمه مرحله تقسیم در نزدیکترین جفت نقاط Reply with quote

Shocked درفراخوانی های بازگشتی در مرحله تقسیم مساله تازمانی به تقسیم ادامه می دهیم که تعدادنقاط P کمتر یا مساوی 3 شود. وقتی به این مرحله رسیدیم به روش معمولی که در بالا گفتیم یعنی انتخاب دو نقطه از 3 نقطه که دوتاحلقه تو درتو هست حل را انجام می دهیم.

تقسیم Divide
الگوریتم یک خط عمودی به نام l پیدا میکندکه نقاط P را به دو مجموعه Pl و Pr تقسیم می کند:
Pl=[P/2] و [Pr=[P/2
Exclamation تمام نقاط Pl سمت چپ خط l و تمام نقاط Pr سمت راست خط l هستند.
آرایه X هم به دو زیر آرایه Xl وXr تقسیم میشودکه شامل نقاط Pl و Pr هستند. که بر اساس مختصات x بصورت صعودی در ارایه قرار می گیرند. در ارایه Y نیز بهمین ترتیب مختصات نقاط PlوPr هستند که براساس مقدارy در انجا مرتب هستند Arrow دو ارایه 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]
Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> طراحي الگوريتم All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
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