ما تعدای نقطه در فضا داریم میخواهیم نقاط زوجی که بهم نزدیک هستند و رو پیدا کنیم - یعنی نقاط نزدیک به همو دو به دو مرتب کرده و در خروجی تحویل دهد - اسمش هم closet pair هست - با روش تقسیم و حل - کسی میتونه واسم انجام بده ؟ خیلی ممنون میشم
ما تعدای نقطه در فضا داریم میخواهیم نقاط زوجی که بهم نزدیک هستند و رو پیدا کنیم - یعنی نقاط نزدیک به همو دو به دو مرتب کرده و در خروجی تحویل دهد - اسمش هم closet pair هست - با روش تقسیم و حل - کسی میتونه واسم انجام بده ؟ خیلی ممنون میشم
Closest Pair ای که مد نظر شما است تمامی نقاط نزدیک به هم رو بدست میاره؟ مطمئن هستید؟ از این جهت می پرسم که اون Closest Pair ای که باهاش آشنایی دارم در بین مجموعه
صرفا یک جفت نقطه ای رو پیدا می کنه که کمترین فاصله رو از هم دارند. به روش تقسیم و غلبه هم قابل حل ئه. نمونه کد ++C اش هم اینجا هست : Divide and Conquer | Set 2 (Closest Pair of Points)
روش کارش اینطوری یه :
اگر تعداد نقاط مجموعه کمتر از 2 باشه که هیچ انتخابی انجام نمیشه.
اگر تعداد نقاط مجموعه برابر 2 باشه، دو نقطه مجموعه به عنوان پاسخ انتخاب می شوند.
اگر تعداد نقاط مجموعه برابر 3 باشه، روش تقسیم و غلبه کاربردی نداره و باید فاصله بین تمامی نقاط بدست بیاد و بر اساس فاصله شون انتخاب انجام بشه.
وگرنه مجموعه نقاط رو بر حسب مقدار x شون مرتب می کنه. سپس یک موقعیت x0 روی محور x در نظر می گیره و بر اساس این موقعیت x0 مجموعه نقاط رو به
دو مجموعه L و R تقسیم می کنه که نقاط L سمت چپ اون موقعیت x0 قرار دارند و نقاط R سمت راست x0 قرار دارند.
بعد بصورت بازگشتی و با همین روش که در ادامه تکمیل میشه جفت نقاطی که کمترین فاصله رو دارند در L و R جداگانه بدست می آورد، فرضا
در مجموعه L دو نقطه p1 و p2 و در مجموعه R نقاط p3 و p4 کمترین فاصله رو از هم دارند.
فاصله p1 تا p2 را از هم بدست آورده (مقدار Lmin) و فاصله p3 تا p4 را بدست آورده (مقدار Rmin) و سپس مقدار Lmin و Rmin را با هم مقایسه کرده و مقدار کوچکتر را به عنوان d بدست می آوریم.
هر نقطه ای که فاصله افقی اش از x0 بیشتر از d نباشد را در مجموعه ای به نام M قرار می دهیم.
نقاط مجموعه M را بر حسب مقدار y شان مرتب می کنیم.
در مجموعه M دو نقطه ای را پیدا می کنیم که کمترین فاصله رو از هم دارند، فرضا p5 و p6
بین جفت نقاط p1 و p2 در L و جفت نقاط p3 و p4 در R و جفت نقاط p5 و p6 در M جفت نقاط منتخب را انتخاب می کنیم.
به ما گفتن که تعدادی نفطه داریم - جفت نقطه های نزدیک به همو (کمترین فاصله باهم داشته باشند )پیدا کرده در خروجی تحویل دهید -بعد به روش تقسیم و حل گفتن - همینی هست که شما میگید ؟
به ما گفتن که تعدادی نفطه داریم - جفت نقطه های نزدیک به همو (کمترین فاصله باهم داشته باشند )پیدا کرده در خروجی تحویل دهید -بعد به روش تقسیم و حل گفتن - همینی هست که شما میگید ؟
به احتمال خیلی زیاد همونه، جفت نقطه هایی که از بقیه به هم نزدیک تر اند رو پیدا می کنه، یک جفت نقطه.
چون اگه قرار باشه همه جفت نقاط نزدیک هم پیدا بشه، پیچیدگی الگوریتم (O(n² است و روش تقسیم و حل
هم نه تنها کمکی به کاهش پیچیدگی الگوریتم نمی کنه، بلکه پیچیدگی اش رو افزایش هم میده.
اونم با روش تقسیم و غلبه؟ با مقایسه عادی ساده است، چون فاصله همه نقاط رو با هم سنجیده و پیدا کردن کمترین فاصله برای الگوریتم اش آسونه اما به روش تقسیم و غلبه روش
مشخصی نمی شناسم که بتونه برای تمامی جفت نقاط یکجا به نتیجه برسه.
اون الگوریتمی که باهاش آشنایی دارم و در اینترنت هست (منظورم با شیوه تقسیم و غلبه است) عملا نقاط رو به سه مجموعه l و r و m تقسیم می کنه و
هر کدوم رو جداگانه بررسی می کنه. وقتی به جواب می رسه، جواب یک جفت نقطه بیشتر نیست که اونم در یکی از این سه مجموعه است. یعنی وقتی به جواب می رسه نمی دونه
که بجز این جفت نقطه بقیه کدوم هاشون به هم نزدیک تره. فقط دنبال یک جفت نقطه است و اطلاعاتش از بقیه نقاط ناقصه.
حالا اگه قرار باشه تمامی نقاط نزدیک رو دو به دو بررسی کنیم، باید اول اون جفت نقاط پیدا شده (جواب قبلی) رو از مجموعه حذف کنیم تا در جستجوی بعدی موثر نباشند و
بعد مجددا مجموعه رو از سر بررسی کنیم ( الگوریتم از نو اجرا بشه) . حالا این الگوریتم تقسیم و غلبه است اما به مراتب از جستجوی عادی که همه نقاط رو دو دونه با هم می سنجید
پیچیده تر و طبعا کند تر میشه.
نمایندگیهای رسمی موبایل سامسونگ در تهران + مزایای استفاده از خدمات آنها