الگوریتم جویبار داده بهینه از نظر فضا برای هسته ها در صفحه

http://www.cs.duke.edu/~pankaj/publications/slides/core-stream.ppt

تقریب هندسی با کمک هسته ها

http://www.cs.duke.edu/~pankaj/publications/slides/core-set.pdf

نمونه گیری تصادفی تقریبی از ورودی را به ما می دهد و ممکن است گاهی به ما تقریب ویژگی که لازم داریم را هم بدهد اما وقتی این طور نباشد، می توانیم از مفهومی به نام هسته (coreset) استفاده کنیم که به طور خاص برای این تعریف شده است که تقریب یک ویژگی خاص را به ما بدهد.

اپسیلون کرنل: اگر به جای فضای دکارتی از فضای قطبی (مجموعه ای از جهت ها) استفاده کنیم به هسته ی به دست آمده اپسیلون کرنل می گویند.

مجموعه چاق خاصیت اپسیلون کرنل را حفظ می کند.

برای ساخت اپسیلون کرنل یک مجموعه نقطه، فاز اول به دست آوردن مجموعه چاق آنها و به دست آوردن اپسیلون کرنل آن و فاز بعد ساخت یک توری و رند کردن نقاط به مجموعه اولیه است.

مقیاسهای گستره نقاط قابل اعتماد: توابعی هستند که هر ضریب دلخواهی از ضریب تقریب اولیه را برای هر اپسیلون کرنل بدهند.

مثال از مقیاس های قابل اعتماد: طول، عرض و ...

مثال از مقیاس های غیرقابل اعتماد: عرض کوچکترین زوج ابرکره شامل همه ی نقاط

به دست آوردن مقیاس های قابل اعتماد: ضریب تقریب را به ضریب داده شده تقسیم کرده و برای ضریب تقریب جدید جواب را به دست می آوریم!

به دست آوردن مقیاسهای غیر قابل اعتماد: می توانیم با خطی سازی بسیاری از توابع را به توابع خطی تصویر کنیم و ارتباط بین توابع خطی و نقاط را به دست بیاوریم.

برای مساله ها و کاربردها به اسلاید مراجعه کنید.

آلفا دیدپذیری

(اول بابت اختراع یک کلمه ی جدید به خودم تبریک میگم! alpha visibility)

http://sharif.edu/~zarrabi/papers/swat-12/alpha-visibility.pdf

تعریف دیدپذیری:

در شکل بالا بعد از این از نقطه p زاویه هایی با فاصله 2pi/alpha رسم می شوند. و ...

پیدا کردن نقطه ای که بیشترین زاویه دید نسبت به یک پاره خط را دارد و از دو نقطه می گذرد = تقاطع کوچکترین دایره ی گذرنده از دو نقطه و پاره خط

...

گستره نقاط

http://graphics.stanford.edu/courses/cs468-06-winter/Slides/nikola_approx_extent_measures_winter.pdf

*مجموعه آلفا-چاق!

* گام اول: تبدیل مجموعه نقاط با یک تبدیل خطی به یک مجموعه آلفا-چاق

* تقریب در عمل چاق کردن حفظ می شود: (گام دوم)

* ضریب تقریب فقط به تعداد ابعاد وابسته است. تعریف فاصله hausdorff

* الگوریتم ساختن مجموعه آلفا چاق با استفاده از توری

* الگوریتم دوم ساخت مجموعه آلفا چاق: رند کردن در جهت های مختلف (چندوجهی)

* الگوریتم سوم ساختن مجموعه آلفا چاق: سطح توری

* توضیح روش آخر

* تقریب توابع d-1 متغیره

* دوگان ابرصفحه و نقطه

* تبدیل به روابط خطی که مساله را تبدیل به محاسبه اپسیلون-تقریب ریشه چندجمله ای های متناظر می کنند. (مثال)

تقریب قطر با استفاده از جعبه محیطی با کمترین حجم در سه بعد

http://graphics.stanford.edu/courses/cs468-06-winter/Slides/an_bounding_box_fall.pdf

تعریف ریاضی توری و یک خانه از آن

محاسبه ی قطر با استفاده از توری

الگوریتم جستجو روی توری با استفاده از جهت ها

جلسه ششم

الگوریتم 2: برای عرض در 2 بعد با تقریب ثابت (chan 2004)

ایده: تکنیک دوبرابر کردن

مقدار دهی اولیه: s: نقطه ی اول؛ t: نقطه دوم؛ width=0

اضافه کردن نقطه p:

w = max( w, width(triangle(s,t,p)) )

if ||s-p|| > 2.||s-t|| then t = p

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

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

تحلیل:

قسمت اول الگوریتم تا قبل از اولین به روز رسانی تقریب زیر برقرار است:

dist(p, line(s,ti)) <= 3w

اثبات:

area of triangle(s,p,ti) = dist(p, line(s,ti) ) * ||s-ti|| = dist(s, line(p,ti)) * ||p-ti|| (1)

line 1 alg'm ==> dist(s, line(p,ti)) <= w (2)

(1),(2) ==> dist(p, line(s,ti) ) * ||s-ti|| <= w*||p-ti|| (6)

triangle inequality ==> ||p-ti|| <= ||p-s||+||s-ti|| (3)

line 2 alg'm ==> ||s-p|| <= 2*||s-ti|| (4)

(3),(4)==> ||p-ti|| <= 3*||s-ti|| (5)

(6),(5) ==> dist(s,line(p,ti)) *||s-ti|| <= w*3*||s-ti||

==> dist(s,line(p,ti)) <= 3*w

(

* اثبات عرض مثلث

تقریب هسته ای که قبلا حساب کرده بودیم، سه حالت دارد که هر بار نسبت دو ضلع را بررسی می کنیم و در بین همه ی این حالت ها نسبت عرض محاسبه شده و جواب حداکثر 3 برابر است.

)

محاسبه تقریب بعد از به روز رسانی

dist(p, line(s,t(i+1)) ) <= dist(p, line(s,ti) ) + dist( p^, line(s,t(i+1)) )

چون خط عمود از p^ (که تصویر p روی line(s,ti) است)  به line(s,t(i+1)) با خط عمود از ti به این خط موازی است، طبق تالس داریم:

<= dist(p,line(s,ti))+||s-p^||/||s-ti|| * dist(ti, line(s,t(i+1))

line 1 alg'm ==>

<= dist( p,line(s,ti) ) + ||s-p^||/||s-ti|| *3*w_opt_i

فاصله ی عمودی از هر فاصله ی دیگری کمتر است

<= dist( p, line(s,ti) ) + ||s-p||/||s-ti|| *3w_opt_i (1)

line 2 alg'm ==> ||s-p|| > 2*||s-ti|| ==> ||s-t(i+1)|| > 2*||s-ti|| (2)

(1),(2) ==> dist(p, line(s,t(i+1)) ) <= dist(p, line(s,ti)) + 2*3*w_opt_i

==> w_alg_(i+1) <= w_alg_i+6*w_opt_i

==> w_alg_(i+1)  <= w_alg_0 + 2*3*w_opt_1+...+2*3*w_opt_i

proof of part 1 (w_alg_0 <= 3w_opt) ==> w_alg <= 3w_opt+2*3*w_opt_1+...+2*3*w_opt

line 2 alg'm (update) ==> 2*w_opt_i <= w_opt_(i+1)

==> w_alg <= 3w_opt+(..+1/4+1/2+1+2)*3w_opt <= 15w_opt

مقدار درست آن 18 است که با تحلیل بهتر به دست می آید اما تا همینجا به تقریب 30 می رسیم. (؟؟)

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

الگوریتم 3: تقریب عرض نقاط در مدل جویبار با استفاده از هسته ی گستره نقاط در دو بعد

ایده: تکنیک دو برابر کردن

s=نقطه اول، t=نقطه دوم

اضافه کردن نقطه p:

0- خطوط توری عمود بر st را با فاصله ی epsilon*||s-t|| رسم کن.

1- نقطه p را به نزدیک ترین خط توری رند کن.

2- تنها نقاط مینیمم و ماکسیمم را روی هر خط نگه دار.

3- اگر ||s-p|| >= 2||s-t است آنگاه t=p و خطوط توری را دوباره رسم کن و نقاط فعلی را دوباره رند کن.

تحلیل:

فضای حافظه : O(1/epsilon)

ضریب تقریب:

هر قدم رند کردن a.p را به اندازه epsilon*w_s{s,ti} <= epsilon*w_a(P_ تغییر می دهد.

بعد از log(1/eplsilon) گام رند کردن،

||s-p|| < epsilon* ||s-ti||

پس p روی خط توری گذرنده از s می افتد. (اولین خط توری)

هر قدم رند کردن a.p را به مقدار زیر تغییر می دهد:

<= L / ||s-ti|| * w_a(s,ti) <= ||s-p||/||s-ti|| w_a(P)

که L فاصله ی بین خط توری گذرنده از s و خط گذرنده از sp است.

{فکر کنم خط توری مرحله جدید و قبلی}

total error <= O(epsilon lg 1/epsilon)*w_a(P)+w_a(P)*epsilon*(1+1/2+...) <= O(epsilon lg 1/epsilon) w_a(P)

space: O(1/epsilon lg 1/epsilon)

بهبود این زمان ها موجود است.

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

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 مگابایت