دورترین همسایه، درخت پوشای ماکسیمم و مسائل مرتبط در ابعاد بالا

Agarwal, Matousek, and Suri (1991) – rounding the directions

چکیده: الگوریتم تصادفی با زمان متوسط

O(m^2/3 n^2/3 log^4/3 m + m log^2 m + n log^2 n)

برای محاسبه ی دورترین همسایه های دو-رنگی بین n نقطه قرمز و m نقطه آبی در E^3 می دهیم. الگوریتم می تواند برای محاسبه ی دورترین همسایه ها یا دورترین همسایه های خارجی n نقطه در E^3 در زمان متوسط O(n^4/3 log^4/3 n) به کار رود. با استفاده از این رویه ها به عنوان اجزای سازنده، می توانیم درخت پوشای ماکسیمم اقلیدسی یا افراز دو مجموعه ای با کمترین قطر برای n نقطه را در E^3 در زمان متوسط O(n^4/3 log^7/3 n) به دست بیاوریم. بهترین زمان قبلی O(n^3/2 log^1/2 n) بود. الگوریتم ما می تواند به ابعاد بالا تعمیم یابد.

همچنین ما الگوریتمهای تقریبی سریع و ساده برای این مسائل ارائه می دهیم. این الگوریتم های تقریبی جوابهایی می سازند که مقدار واقعی را با دقت e تقریب می زنند و در زمان O(n e^(1-k)/2 log n) یا O(n e^(k-1)/2 log^2 n) در فضای k-بعدی حل می شوند.

مقدمه:

در این مقاله مسائل را در فضای اقلیدسی E^k برای تعداد ابعاد ثابت k حل می کنیم. الگوریتم کارایی برای مسائل زیر ارائه می دهیم:

1- همه ی دورترین همسایه ها: یک مجموعه S از n نقطه در E^k داده شده است، برای هر نقطه p عضو S نقطه ی q عضو S را طوری پیدا کنید که d(p,q) >= d(p,q') باشد (به ازای هر q' عضو S)؛ به q دورترین همسایه p می گویند.

2- دورترین همسایه های دو-رنگی: مجموعه R از n نقطه قرمز و مجموعه B از m نقطه آبی در E^k داده شده اند. برای هر نقطه r عضو R، نقطه ی b عضو B را طوری پیدا کنید که d(r,b) >= d(r,b') باشد (به ازای هر b' عضو B)؛ در این صورت به b دورترین همسایه رنگی r می گویند.

3- دورترین همسایه خارجی: مجموعه S از n نقطه در E^k و افرازهای آن S1,S2,...,Sm داده شده است، برای هر p عضو S اگر p عضو Si است، نقطه ی q عضو S-Si را که d(p,q) >= d(p,q') برای همه ی q' عضو S-Si برقرار باشد؛ q را دورترین همسایه خارجی p می نامیم.

4- درخت پوشای ماکسیمم اقلیدسی (EMXST): مجموعه S از n نقطه در ٍE^k داده شده است، درخت پوشای S که یالهای آن ماکسیمم فاصله بین همه ی درخت های پوشا را دارند، که طول هر یال فاصله ی اقلیدسی بین نقاط دو سر آن است را محاسبه کنید.

5- افراز دو مجموعه ای با مینیمم قطر: مجموعه S از n نقطه در E^k داده شده است، S را به دو مجموعه افراز کنید طوری که ماکسیمم بین قطر این دو مجموعه نقطه مینیمم شود.

مساله محاسبه همسایه (دورترین، نزدیک ترین، یا میانی) یک مساله اصلی در هندسه محاسباتی است که کاربردهای زیادی دارد. اما مساله ی همه ی نزدیک ترین همسایه در E^k می تواند به صورت بهینه در O(n log n) حل شود، هیچ الگوریتمی با چنین کارایی برای دورترین همسایه به ازای k>= 3 نیست. کاربردهای زیادی به نسخه های دو-رنگی و خارجی هم نیاز دارند. برای این دو مساله هم در k>=3 جواب بهینه نداریم. برای زوج قطر مساله در O(n^ (2-2/(k/2+1+gamma)) برای n نقطه در k بعد حل شده است، اما الگوریتم داده شده قابل تعمیم به دورترین/نزدیک ترین همسایه نیست. بهترین الگوریتم فعلی برای دورترین همسایه در سه بعد در زمان O(n^3/2 log^1/2 n) کار می کند. در این مقاله یک الگوریتم بهتر ولی تصادفی برای دورترین همسایه ها و مسائل مربوط به آن برای سه بعد و ابعاد بالا می دهیم.

...

2- محاسبه دورترین همسایه

یک الگوریتم تصادفی برای محاسبه دورترین همسایه دو-رنگی می دهیم و آن را برای به دست آوردن دورترین همسایه کلی و خارجی به کار می بریم. ساختار الگوریتم از نمونه گیری تصادفی الگوریتم های هندسی استفاده می کند. ابتدا برای حالت نامتوازن یک الگوریتم کارا می دهیم که تعداد نقاط آبی خیلی از نقاط قرمز بیشتر است. بعد از تقسیم و حل تصادفی برای تبدیل مساله متوازن به چند نمونه از مساله نامتوازن استفاده می کنیم.

2-1- الگوریتم برای حالت نقاط آبی زیاد و نقاط قرمز کم

به صورت تصادفی زیرمجموعه ای m/4 عضوی از نقاط آبی انتخاب می کنیم و مجموعه نقاط قرمز را به دو مجموعه n/2 عضوی افراز می کنیم و مساله را برای این زیرمساله ها حل می کنیم. به ازای نقطه قرمز iام و دورترین همسایه آبی آن b'i تعریف می کنیم: Si را توپ به مرکز نقطه قرمز و شعاع فاصله قرمز و آبی می نامیم و S'_i را خارج این توپ تعریف می کنیم. چون b'i دورترین همسایه ri بوده است، پس B' درون همه ی توپ های به مرکز نقاط قرمز می افتد و دورترین همسایه ri در B یا b'i است یا در S'i می افتد. پس نقاط اشتراک Si ها جواب ما نیستند.

...

--------------

تقسیم بندی همان تقسیم بندی است که در پست مربوط به جزوه ی این جلسه گفته بودم اما برای به دست آوردن حداکثر فاصله از دورترین همسایه استفاده کرده است که جهت های انتخابی را نقاط آبی و نقاط را قرمز گرفته است. بعد ثابت کرده است که ضریب تقریب حفظ می شود.

حل 2_15 وزیرانی

البته اصل حل مربوط به یک سوال دیگر در کتاب WS بود اما فکر کنم این سوال هم همین طوری حل می شود. (حداقل می دانم سوالهایی که حل آنها در این دو کتاب نیامده در امتحان هم نمی آید!)

تمرین های فصل 2 WS (زمانبندی کارها) 2.1,2.3

2- فرض مساله را به صورت زیر می نویسیم

OPT/3 < w_1 <= w_2 <=...<=w_m

الگوریتم LPT هم کارها را به ترتیب از زمان اجرای زیاد به کم انجام می دهد. می خواهیم ثابت کنیم این کار به جواب بهینه می رسد.

از فرض داده شده می فهمیم به هر پردازنده حداکثر 2 کار می رسد. جواب بهینه جوابی است که زوج کارهایی که به یک پردازنده داده می شوند، جمعشان مینیمم شود. اگر تعداد پردازنده ها از نصف کارها بیشتر باشد که کارهای با زمان طولانی تر به تنهایی روی یک پردازنده اجرا می شوند و کارهای با زمان کمتر هر دو تا روی یک پردازنده اجرا می شوند. پردازنده هایی که به آنها دو کار داده شده است، باید طوری باشند که جمع این دو کار مینیمم شود. برای این کار بهترین کار این است که کار با بیشترین زمان و کمترین زمان را با هم به یک پردازنده بدهیم.

3- الگوریتم زمانبندی لیست کارها را به ترتیبی دلخواه در یک لیست می گذارد و کار بالای لیست را به اولین پردازنده ای که بیکار شد می دهد. اثبات آن به اثبات جستجوی محلی ارجاع داده شده بود.

بر خلاف اثبات سوال بدون اولویت نمی توانیم از میانگین به عنوان کران پایین استفاده کنیم. 

حل المسائل وست

کتاب نظریه گراف است ولی من تا همین الآن که اتفاقی حل المسائلش را دیدم نمی دانستم حل المسائل دارد.

دریافت
حجم: 3.35 مگابایت

استفاده از تجانس برای پیدا کردن نزدیک ترین همسایه در ابعاد بالا

http://aidblab.cse.iitm.ac.in/cs625/6.FastMap.pdf

البته این کار را با روش دیگری امتحان کرده است، شاید با روشی که من می خواهم انجام بدهم کار کند.

مقاله پردازش موازی

مطمئن نیستم ارائه داشته باشیم اما یک مقاله در مورد موضوع مورد علاقه ام پیدا کردم. چون هنوز استاد درس نخواسته اند که موضوع ارائه را مشخص کنیم نمی توانم اینجا چیز بیشتری بنویسم (چون ممکن است یک نفر دیگر این موضوع را انتخاب کند).

یادآوری

به من یادآوری کنید که به استادم یادآوری کنم که به بچه ها یادآوری کنند که سر ارائه ی من بیایند.

به نظرم قسمت های زیادی از موضوع را اشتباه فهمیدم و هر چه بیشتر می خوانم بیشتر گیج می شوم و کمتر می فهمم.

min-wise independent hashing

http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/BroderCFM-minwise.pdf

مرجع هندسه محاسباتی پیشرفته

خودم این را پیدا کرده بودم اما نمی دانم چرا قبلا نگذاشته بودمش.

دریافت
حجم: 409 کیلوبایت

انتشار (broadcast) - موازی

در پست قبل گفتیم که:

راهنمایی حل سوال:

فرض کنید می خواهیم از host داده ای را برای همه ی پردازنده ها broadcast کنیم. با یک bfs از host روی گراف (فعلا یالهای را بدون جهت در نظر می گیریم) می زنیم و یال با وزن 0 اضافه می کنیم. از آنجایی که گراف اولیه systolic بوده است و درخت (bfs) دور ندارد، پس دور با وزن 0 نداریم و گراف جدید semi-systolic است و با روش گفته شده می توانیم آن را systolic کنیم.

ثابت می کنیم که با 2 برابر کردن وزن یالها حتما می توانیم این گراف را systolic کنیم. برای این کار کافی است نشان دهیم که حداکثر نصف یالهای هر دور وزن 0 دارند. = حداکثر نصف یالهای هر دور از درخت bfs آمده اند. هر یال bfs عمق را یکی زیاد می کند و هر یال غیر bfs عمق را حداکثر یکی کم می کند. چون یک دور است باید از همان راسی که شروع کرده به همان برگردد پس تعداد یالهای bfs از غیر bfs کمتر مساوی است.

(تا آخر 1.4.5)