پروژه هندسه محاسباتی پیشرفته

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

هنوز با این لاتکس؟ فارسی درگیری دارم. تازه هر نسخه ای از نرم افزارهاش هم با اون یکی فرق داره.

باید ارائه ی این را هم آماده کنم. (این داستان ادامه دارد..)

پوشش مجموعه ای - مرجع: motwani

یک ابرگراف فرض کنید که هر راس آن یکی از مجموعه ها است (هزینه ی آن مجموعه) و هر یال یک عضو از مجموعه مرجع است که می تواند در چندین راس وجود داشته باشد.

الگوریتم: هر بار راس با بیشترین درجه را بردارید و همه ی یالهای متصل به آن را حذف کنید.

صفحه ی وزیرانی

http://www.cc.gatech.edu/~vazirani

ادامه ی تمرین های فصل 2 وزیرانی

6- گراف بدون جهت G داده شده، راسهای آن را با کمترین تعداد رنگ طوری رنگ کنید که دو سر یک یال رنگ متمایز داشته باشند.

الف) حریصانه و با delta+1 رنگ (delta ماکسیمم درجه)

از یک راس شروع می کنیم و آنرا رنگ می کنیم و همه ی همسایه های آن را با رنگ دیگری رنگ می کنیم. این کار را برای همسایه های آن راس هم انجام می دهیم. اگر دو سر یک یال همرنگ بود، رنگ یک سر آن را عوض می کنیم: چون هر راس حداکثر delta همسایه دارد و ما delta+1 رنگ داریم این کار همیشه امکان پذیر است.

ب) یک الگوریتم برای رنگ آمیزی گراف 3-رنگ پذیر با O(sqrt(n)) رنگ بدهید.

راهنمایی: یک راس و همسایه های آن یک گراف دوبخشی (زیرگراف G) است پس می تواند به صورت بهینه رنگ آمیزی شود. راسهایی که درجه ی بیشتر از sqrt(n) دارند با سه رنگ، رنگ کنید بعد الگوریتم قسمت الف را اجرا کنید.

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

7- ثابت کنید پوشش راسی حالت خاص پوشش مجموعه ای است.

پوشش مجموعه ای می گوید مجموعه ها اجتماعشان مجموعه مرجع شود و تعداد مجموعه های انتخاب شده کمینه باشد.

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

پس هر راس را مجموعه ی یالهای مجاور آن می گیریم. حالا اگر پوشش مجموعه ای این مجموعه ها را پیدا کنیم (مجموعه مرجع مجموعه ی همه ی یالها است) یک پوشش راسی برای یالهاست، چون مجموعه ی مرجع (همه ی یالها) را پوشش می دهد. دلیل کمینه بودن آن هم این است که اگر راسی اضافه انتخاب شده باشد، مجموعه ی متناظر آن را می توان حذف کرد و به پوشش مجموعه ای کمینه رسید، که با فرض کمینه بودن پوشش مجموعه ای تناقض دارد.

8- ثابت کنید پوشش مجموعه ای حریصانه ضریب تقریب H(k) دارد. (k=تعداد اعضای بزرگترین زیرمجموعه ی U)

(انتخاب حریصانه: cost(S)/(|S-C|) ماکسیمم شود.)

توی پستهای قبلی هست.

9- یک الگوریتم حریصانه بدهید که ضریب تقریب H(n) را برای پوشش چندگانه مجموعه ای تضمین کند. پوشش چندگانه مجموعه ای یک تعمیم از پوشش مجموعه ای است که (فکر کنم!) در آن هر عنصر باید حداقل به تعداد گفته شده ای برداشته بشه. فرض کنید هزینه ی برداشتن a کپی از مجموعه Si برابر a.cost(Si) است.

پردازش موازی -صفحه قدیمی درس

http://mehr.sharif.edu/~ce647/materials.html

http://mehr.sharif.edu/~ce647/links.html

ادامه ی تمرینهای فصل 1 وزیرانی (الگوریتم تقریبی)

4- مساله پوشش راسی را حریصانه حل کنید: راس با بیشترین درجه را بردارید و همسایه های آن را حذف کنید. نشان دهید ضریب تقریب این الگوریتم O(log n) است و یک مثال tight برای آن بدهید.

راهنمایی: تحلیل شبیه قضیه 2.4 (اثبات set cover) است.

OPT <= ALG <= O(log n) OPT

اجزای مهم این مساله یالها هستند. (چون یک سر هر یال باید در پوشش راسی باشد.)

انتخاب یال i-ام (حریصانه): سود / هزینه

ALG(ei) = delta(i) <= OPT(n-i)/(n-i) <= OPT/(n-i)

ALG <= OPT*sum_i_1_n(1/(n-i)) <= OPT*O(log n)

 مثال tight: می خواهیم یک گراف دوبخشی بسازیم، چون انتخاب یک بخش آن جواب VC است.

از یک گراف ستاره شروع می کنیم و مرکز آن را در بخش اول(جواب بهینه) می گذاریم و بقیه ی راسهای آن را در بخش دیگر. می خواهیم طوری درجه ی راسهای بخش دیگر (که الآن 1 هستند) را زیاد کنیم که قبل از راس اول (مرکز ستاره) انتخاب شوند. 

تمرین های فصل 2 الگوریتم تقریبی -وزیرانی

1- یک گراف بدون جهت داده شده است، برش با بیشترین تعداد یال را پیدا کنید. الگوریتم حریصانه ی زیر را در نظر بگیرید: در هر مجموعه دو راس دلخواه قرار می دهیم، راسهای بعدی را به مجموعه ای اضافه می کنیم که تعداد یالهای بیشتری بین این راس و اعضای آن مجموعه است. نشان دهید الگوریتم 1/2 تقریبی است و برای آن یک مثال tight بدهید. از چه کران بالایی برای جواب بهینه استفاده کردید؟ دو مثال از گرافهایی بدهید که به ازای آنها این کران بالا دو برابر بدتر از جواب بهینه باشد. مساله و الگوریتم را به حالت وزندار تعمیم دهید.

?) 1/2 OPT <= ALG <= OPT

deg(Vi) >= deg_A(Vi)+deg_B(Vi)

ALG(Vi) = max( deg_A(Vi), deg_B(Vi) )

max(x,y) >= 1/2(x+y)

ALG(Vi) >= 1/2 ( deg_A(Vi)+deg_B(Vi) ) >= 1/2 deg(Vi)

OPT(Vi) = deg_A*(Vi) <= deg(Vi)

ALG = sum(ALG(Vi)) >= 1/2 sum(deg(Vi)) >= 1/2 OPT

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

(ایده: اجرای الگوریتم و انتخاب بدترین حالت ممکن در هر مرحله)

کران بالا:

مثال کرانها:

2- سوال قبل را با الگوریتم جستجوی محلی (local search) حل کنید: از دو مجموعه ی دلخواه شروع کنید، اگر با عوض کردن جای یک راس جواب بهتر شد این کار را انجام دهید. تا وقتی که دیگر نشود این کار را ادامه داد. ثابت کنید در زمان چندجمله ای الگوریتم تمام می شود (تعداد مراحل چندجمله ای است) و ضریب تقریب 1/2 است.

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

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

3- در یک گراف وزن دار برش با وزن بیشینه که گراف را k قسمت کند پیدا کنید. الگوریتم حریصانه با ضریب (1-1/k) بدهید. آیا این جواب tight است؟

انتخاب حریصانه: سود برداشتن / هزینه ی برداشتن

اگر یال برداریم قدرت انتخابمان کم می شود: بعد از برداشتن k یال سنگینتر ممکن است قسمتها مشخص شده باشند در حالی که بهترین جواب نباشد.

الگوریتم: اضافه کردن یک راس به یک مجموعه: وزن یالهای بین آن راس و راسهای مجموعه های دیگر / وزن یالهای بین آن راس و اعضای مجموعه خودش

cost(Vi, Sj) = sum_u_in_Sj( cost(u,Vi) ) / sum_u_not_in_Sj( cost(u,Vi) )

ALG(Vi) = max_Sj ( cost(Vi, Sj) ) <= 1/k sum_j (cost(Vi,Sj) )

W(Vi) = sum of weights of incident edges of Vi

sum_j(cost(Vi,Sj)) <= k*W(Vi)-W(Vi) = (k-1)W(Vi)

OPT(Vi) < W(Vi)

==> ALG < (k-1)/k OPT

مثال:

4- برش با وزن بیشینه جهت دار. الگوریتم با ضریب تقریب 1/4 بدهید.

انتخاب حریصانه: جمع وزن یالهای راس Vi به راسهای مجموعه ی دیگر ماکسیمم شود.

(راه حل 2: local search)

ALG(Vi) = max( sum_u_S' (cost(Vi,u) , sum_u_S (cost(Vi,u)) )

ALG(Vi) >= 1/2 sum_u (cost(Vi,u))

ALG >= 1/2 sum_Vi sum_u(cost(Vi,u))

OPT <= sum_Vi sum_u( cost(Vi,u) )

ALG >= 1/4 OPT

5- با کمک سوال 2 (local search) و این حقیقت که برای گرافهای دوبخشی مساله پوشش راسی در زمان چندجمله ای حل می شود، یک الگوریتم تقریبی با ضریب lg delta بدهید که delta بیشترین درجه ی راسهای گراف است.

راهنمایی: زیرگراف به دست آمده برای سوال برش بیشینه را در نظر بگیرید (H). می دانیم H دوبخشی است و درجه ی هر راس آن از نصف درجه ی آن راس در G (گراف اصلی) بیشتر مساوی است.

می توانیم از تکنیک لایه ای استفاده کنیم و گراف H را هر بار بسازیم و یالهایی که تصمیم گرفتیم براشون رو حذف کنیم. هر بار نصف درجه ی راسها را بر می داریم حداقل، پس تقریب حداکثر log delta می شود.

6- رنگ آمیزی رئوس: گراف بدون جهت G داده شده، راسهای آن را طوری رنگ کنید که حداقل تعداد رنگ به کار برود و دو سر هر یال رنگ متمایز داشته باشند.

الف) یک الگوریتم حریصانه بدهید که G را با delta+1 رنگ، رنگ کند. (delta ماکسیمم درجه)

ب) یک الگوریتم برای گرافهای سه رنگ پذیر بدهید که O(sqrt(n)) رنگ بخواهد.

راهنمایی: برای هر راس، گراف القایی روی همسایه های آن، N(v)، دوبخشی است پس به صورت بهینه قابل رنگ کردن است. اگر v درجه ی بیشتر از sqrt(n) داشته باشد، v و همسایه هایش را با سه رنگ متمایز رنگ کنید. این کار را ادامه دهید تا هر راس درجه ی کمتر از sqrt(n) داشته باشد. بعد از الگوریتم بخش اول استفاده کنید.

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

روش locality sensitive hasing

MIT

Piotr Indyk

Slides

ویکیپدیا

Stanford

(آدرس سایت اصلی الگوریتم های هندسی تقریبی http://graphics.stanford.edu/courses/cs468-06-fall/)

سوال

من سر این خیلی سوتی دادم. یکی حلش کنه:

یک نقطه q داریم دورترین نقطه از بین نقاط مجموعه به اون p است. خط L از نقطه q می گذرد. از p یک صفحه به خط L عمود می کنیم و محل تقاطع این دو تا رو q^ می نامیم. ثابت کنید p دورترین نقطه به q^ در این صفحه است.

حل شد! :)

فیثاغورت نوشتم. اشکال حلم این بود که از عمود بودنش استفاده نمی کردم.

مرتب کردن آرایه خطی به صورت موازی

http://www.cs.utah.edu/~rajeev/cs7820/pres/08-7820-24.pdf