درس الگوریتم تقریبی در دانشگاه های دیگر

تمرین با جواب

http://www.math.mcgill.ca/~vetta/CS692.dir/homework.html

http://www.public.asu.edu/~ccolbou/src/cse552f13.html

https://www.mpi-inf.mpg.de/departments/d1/teaching/ws13/Approx

http://www.cs.cornell.edu/courses/cs783/2003fa

جلسه چهارم

هسته های هندسی

*هسته ی گستره ی نقاط (extent)

الگوریتم دقیق: O(n^c) که c ثابت است. {سه نقطه داشته باشیم به دست میاد پس n^3 تا برای ساختن دو خط موازی n تا برای چک کردن اینکه همه نقاط بین انها هستند پس c از 4 کمتر است.}

الگوریتم تقریبی: (با استفاده از هسته گستره نقاط)

محاسبه ی هسته O(n) {پیدا کردن دور ترین نقطه از یک نقطه و دورترین نقطه از یک خط}

محاسبه ی جواب دقیق مساله برای هسته: ( O( ((1/epsilon)^c')^c {اینجا c' احتمالا همان d یا d-1 و مثل آن است و یک بر اپسیلون هم تعداد نقاط هر بعد است پس کلا همان اندازه ی هسته به دست می آید.}

زمان کل: O(n+(1/epsilon)^c'c)

* تعمیم به ابعاد بالاتر (هسته ی گستره نقاط)

فرض کنید مبدا جزو نقاط باشد.

1) به ازای ابعاد از 1 تا d بعد:

2) دورترین نقطه را به ابرصفحه ی (j-1) بعدی ( j-1)-flat) ) گذرنده از مبدا و نقاط قبلی پیدا کنید.

3) عرض مجموعه نقاط به دست آمده در مرحله 2 الگوریتم را به دست آورید.

زمان الگوریتم:

d*O(nd) = O(nd^2) ==> O(n)

ضریب تقریب الگوریتم:

تصویر بردار متناظر نقاط قبل روی ابرصفحه های (j-1) بعدی تشکیل یک پایه (نه لزوما متعامد) می دهد. می دانیم هر کدام از نقاط را می توان به صورت ترکیب خطی از بردارهای این پایه نوشت که ضرایب آنها قدر مطلقشان از 1 کمتر مساوی است (چون دورترین نقطه را هر بار انتخاب کرده ایم.)

قضیه: اگر بردار پایه بعد j-ام u_j باشد و مجموعه نقاط مرحله 2 (شامل مبدا مختصات) را S بنامیم و a هر بردار جهت دلخواه باشد، داریم:

|a.u_j| <= 2^(j-1) * width_a (S)

اثبات: استقرا روی تعداد ابعاد

پایه استقرا: یک بعد

a.u_1=a.v_1 <= width_a (S)

فرض استقرا: برای بعدهای 1 تا j-1 درست است.

حکم استقرا: برای بعد j ام:

u_j = v_j+sum_k_1_(j-1) (b_k*u_k) , |b_k| <= 1

(یعنی اگر از بردار v_j تصویر آن را در راستای بردارهای ابعاد قبل کم کنیم، تصویر آن روی ابرصفحه ی بردارهای قبلی به دست می آید.)

|a.u_j| <= |a.v_j|+sum_k_1_(j-1) (|a.u_k|)

(بردار a را در تساوی قبلی ضرب کرده ایم و از b_k <=1 استفاده کرده ایم.)

<= width_a (S)+sum_k_1_(j-1) (2^(k-1)*width_a(S) ) = 2^(j-1)*width_a(S)

(چون بردار a یکه است، ضرب داخلی آن در هر برداری تصویر آن بردار را در جهت a می دهد. که عرض نقاط از تصویر بردار در آن راستا بیشتر است.

از جلسه قبل داشتیم که دو برابر عرض نقاط از تصویر هر برداری در هر راستایی بیشتر است و تصویر بردار از عرض نقاط بیشتر است؛ که این دلیل نامساوی دومی است.)

نتیجه: به ازای هر نقطه p از مجموعه نقاط ورودی داریم:

|a.p| <= sum_j_1_d (|a.u_j|) <= sum_i_1_d ( 2^(j-1)*width_a(S) ) <= 2^d*width_a(S)

از اینجا ضریب تقریب الگوریتم را به دست می آوریم: (p و q دو نقطه از نقاط ورودی هستند)

|a.(p-q)| = |a.p-a.q| <= |a.p|+|a.q| <= 2* 2^(d) * width_a(S) =2^(d+1) * width_a(S)

==> width_a(S) <= width_a(P) <= 2^(d+1) * width_a(S)

factor = 2^(d+1)

*بهبود: 

قضیه: می توانیم تبدیل آفینی پیدا کنیم که به ازای هر بردار جهت، عرض نقاط بین دو مقدار ثابت باشد.

(تبدیل آفین: هر تبدیلی که نقطه و خط و صفحه را حفظ کند. همه ی تبدیل های هندسی متداول آفین اند. خطوط موازی بعد از تبدیل آفین باز هم موازی خواهند بود.)

اثبات:

نقاط را در جهت بردارهای پایه (u_i) تجانس ( کلی فکر کردم یادم اومد چند برابر کردن اسمش چیه! :)) ) بدهیم طوری که اندازه ی آنها 1 بشه. (به ترتیب از بعد 1 تا d)

بعد از تبدیل:

c/2^(d+1) <= width_a(P) <= 2*sqrt(d)

چون همه ی نقاط بعدهایی بین 1 و -1 دارند، یعنی در ابرمکعب dبعدی قرار می گیرند، حداکثر فاصله شان 2 رادیکال d است. (نامساوی سمت راست)

نامساوی سمت چپ ؟؟

* هسته مجموعه نقاط P

1) تبدیل را روی P انجام بده.

2) یک توری به طول اپسیلون روی آن بساز.

3) به ازای هر خانه توری، یک نقطه از آن را در S نگه دار.

تحلیل:

به ازای هر بردار جهت a داریم:

|width_a(S) - width_a(P)| = O(epsilon) = O(epsilon*width_a(P))

تساوی آخر به دلیل داشتن مقدار حداکثر عرض نقاط است. (به دلیل تبدیلی که انجام دادیم و نامساوی قبل)

width_a(S) / width_a(P) = 1-O(epsilon)

==> O(epsilon)-coreset

اندازه هسته:

#grid cells = O(1/epsilon^d)

*مساله عرض نقاط:

O(n+(1/epsilon^d)^ceil(d/2) ) {using exact algorithm}

O(n+1/epsilon^((d-1)/2)*1/epsilon^((d-1)/2) ) = O(n+1/epsilon^(3/2(d-1)) ) {using algorithm 1: dir. rounding+skewed width}

d-1 برای این است که می توان با پیدا کردن دورترین نقطه در یک بعد مساله را حل کرد.

نکته: بعد از تبدیل گرفتن جهت ها را رند کنیم.

نکته: می توانیم از نوعی دیاگرام ورونوی گسسته استفاده کنیم. {نزدیک ترین نقطه به جای دورترین نقطه که در قطر استفاده کردیم.} که این کار زمان زیر را می دهد:

O(n+1/epsilon^(d-1))

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

O(1/epsilon^((d-1)/2) ) {by Agrawal}

نکته: هسته گستره نقاط برای پوسته محدب کار می کند.

نکته: هسته گستره نقاط برای مسائل دیگری مثل پیدا کردن دو دایره هم مرکز با کمترین فاصله که همه ی نقاط را بپوشانند؛ هم کار می کند.

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

4- نسخه ای از فروشنده دوره گرد متریک را در نظر بگیرید که در آن هدف پیدا کردن مسیر ساده شامل همه ی راسهای گراف است. سه مساله مختلف بر حسب تعداد سرهای مسیر که داده شده اند (0، 1، 2) وجود دارد. الگوریتم های تقریبی زیر را به دست آورید:

- اگر 0 یا 1 سر داده شده، الگوریتم با ضریب تقریب 3/2 بدهید.

- اگر هر دو سر مشخص شده اند، الگوریتم با ضریب 5/3 بدهید.

راهنمایی: از ایده الگوریتم 3.10 استفاده کنید. (الگوریتم 3.10 فروشنده دوره گرد متریک با ضریب 3/2 است که فقط راسهای درجه فرد را اصلاح می کرد.)

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

الف)

همان الگوریتم 3.10 را اجرا می کنیم، فقط به جای اینکه در آخر یک دور بسازیم، یک مسیر می سازیم:

در حالت 1 سر داده شده: یال ورودی به راس داده شده را حذف می کنیم.

در حالت 0 سر داده شده: یال با بیشترین وزن در دور را حذف می کنیم.

اثبات: یک تطابق کامل با کمترین وزن هزینه ای کمتر از نصف هزینه ی مسیر گذرنده از تمام رئوس دارد: چون اگر یالهای مسیر را یکی در میان حذف کنیم یک تطابق کامل می شود.

هزینه ی درخت هم از هزینه ی جواب بهینه کمتر است. پس کل هزینه از 3/2 جواب بهینه کمتر است. پس ضریب تقریب الگوریتم 3/2 است.

ب)

همان الگوریتم 3.10 را اجرا می کنیم، فقط به جای گراف اویلری، گراف نیمه اویلری می سازیم که درجه ی دو راس داده شده در آن فرد باشد. برای این کار می توانیم اگر درجه آنها فرد بود آن را تغییر ندهیم، در غیر این صورت در تطابقمان این راسها را هم در نظر بگیریم. در حالت اول جوابی که به دست می آید 3/2 جواب بهینه است. در حالت دوم جوابی که به دست می آید از هزینه MST +  دو سوم هزینه مسیر TSP کمتر است.

5- فرض کنید گراف کامل بدون جهت داده شده که طول یالهای آن 1 یا 2 است (بدیهی است که در نامساوی مثلث صدق می کند). یک الگوریتم با ضریب تقریب 4/3 برای فروشنده دوره گرد در این گرافها بدهید.

راهنمایی: از پیدا کردن 2-تطابق مینیمم شروع کنید. یک 2-تطابق زیرمجموعه ای از یالهاست که هر راس دقیقا دو یال مجاور دارد.

حل: یک تطابق کامل مینیمم پیدا می کنیم و یالهای آن را حذف می کنیم، بعد یک تطابق کامل مینیمم دیگر پیدا می کنیم و یالهای این تطابق و تطابق قبلی را به عنوان 2-تطابق مینیمم در نظر می گیریم.

به MST در راسهایی که درجه فرد دارند از 2-تطابق کمینه یال اضافه می کنیم. می دانیم هزینه ی جواب بهینه از هزینه ی یالهای 2-تطابق کمینه بیشتر است. وزن 2-تطابق کمینه از وزن جواب بهینه مساله کمتر مساوی است. (چون در جواب بهینه یک دور داریم اما اینجا یک یا چند دور داریم.)

جلسه سوم

عرض نقاط

مجموعه P از n نقطه در فضای d بعدی داده شده است، کمترین فاصله بین دو ابرصفحه موازی را پیدا کنید که همه ی نقاط بین دو ابر صفحه بیفتند.

= پیدا کردن ابرصفحه ای که فاصله ی دورترین نقطه از آن مینیمم شود. (صفحه ی بین دو ابرصفحه ی موازی قبل این صفحه است.)

الگوریتم های دقیق:

2بعد: anti-podal pair و پوسته محدب O(nlogn)

3بعد: تصادفی Agrawal,Sharir 1995 زمان ((O(n^(3/2+epsilon

4 بعد و بیشتر: O(n^ceil(d/2))

تعریف ریاضی مساله:

w* = min (1/ sqrt(n1^2+n2^2+...+nd^2) )

s.t. h <= x1*n1+...+xd*nd <= h+1

(parallel planes: x1*n1+...+xd*nd=h, x1*n1+...+xd*nd=h+1)

(variables: (n1,...,nd,h) )

این یک LP نیست چون تابع آن خطی نیست، اما برنامه نویسی محدب است.

زمان حل: O(n^ceil((d+1)/2))

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

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

1- الگوریتم Duncan, Goodrich, Ramus 1997

ایده: رند کردن نقاط با استفاده از جهت و محاسبه عرض کج؟ (skewed width)

1) مجموعه جهت ها را بساز. O(1/epsilon^(d-1)) جهت برای حفظ حداکثر زاویه بردار دلخواه با این جهات.

2) در هر کدام از جهت های قسمت 1، عرض کج را در آن جهت حساب کن. (عرض کج = عرض نقاط در آن جهت)

نحوه ی محاسبه ی عرض کج: یک LP با d+1 متغیر است که d تای آن مربوط به ابرصفحه ی وسط دو صفحه (به تعریف مساله نگاه کنید) هستند و متغیر دیگر مربوط به حداکثر فاصله یک نقطه از این ابرصفحه است که هدف LP هم مینیمم کردن آن است.

با توجه به اینکه نرمال صفحه بردار a (بردار جهت) است که در مرحله ی اول الگوریتم به دست آمده است، نمی دانم چرا در جزوه d+1 متغیر در نظر گرفته شده، باید همان 1 متغیره باشد!

*زمان الگوریتم:

#directions * LP(#points)

O(1/delta^(d-1) * n)

*ضریب تقریب:

width_OPT <= width_ALG <= width_OPT/cos(delta)

factor = 1/cos(delta)

1/(1-x) = 1+x+x^2+... >= 1+x

cos(delta) = 1-2*sin^2(delta/2) = 1-2(delta-delta^3/3+...)^2 <= 1-2*delta^2

x=2*delta^2

1/cos(delta) >= 1+2*delta^2

epsilon = 2*delta^2

factor = 1+epsilon

2- الگوریتم Agarwal, Har-peled, vardarajan 2004

ایده: رند کردن نقاط با توری غیر یکنواخت + دوران یافته + مقیاس شده (scaling)

*مساله کلی تر: برای همه ی جهت ها تقریب را به دست بیاوریم: با کمک یک زیر مجموعه از نقاط:

زیر مجموعه ای از نقاط را پیدا کنید که به ازای هر بردار یکه a داشته باشیم:

width_a (all points) >= width_a (subset) >= width_a(all points) *(1-epsilon)

width_a (points) = max_p,q_points (a.(p-q))

به این یک extent (گستره) از نقاط می گویند و یک اپسیلون-هسته است. (epsilon-coreset)

*پیدا کردن هسته با اندازه ی ثابت

الگوریتم تقریبی برای دو بعد با ضریب ثابت:

s: هر نقطه ی دلخواه از مجموعه نقاط ورودی (P)

t: دورترین همسایه s

u: دورترین نقطه از پاره خط st

عرض نقاط: عرض سه نقطه ی قبل

زمان الگوریتم: O(n) که n تعداد نقاط است.

ضریب تقریب الگوریتم:

چون در طرف دیگر خط st هم می تواند نقطه باشد، جواب الگوریتم را دو برابر عرض نقاط هسته می دهیم.

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

الآن باید تقریب هسته را در بیاوریم و در تقریب الگوریتم (=2، چون جواب حداکثر دو برابر عرض نقاط است: همه یک طرف خط st باشند) ضرب کنیم.

تقریب هسته:

هسته ی فعلی ما دو خط موازی اند که یکی از آنها امتداد st است و دیگری خط موازی آن است که از u می گذرد. چون همه ی نقاط باید در فاصله بین این دو خط باشند، مثلث ust در همه ی این هسته ها وجود دارد. 

||u-t|| <=||s-t||+||s-u|| (triangle inequality) <= 2.||s-t|| (t = farthest point from s)

width_ALG*||s-t|| = width_coreset*||u-t|| <=2.||s-t||.width_coreset

==> width_ALG <= 2.width_coreset

پس تقریب الگوریتم 4 است.

جلسه دوم

ادامه ی الگوریتم های محاسبه قطر نقاط

3- الگوریتم تقریبی agrawal, matousek, suri 1992

ایده: رند کردن جهت ها (به جای اینکه نقاط ورودی را رند کنیم، نقاط خروجی را رند می کنیم.)

1- مجموعه ای از جهت ها به دست بیاور. (هر جهت a)

2- نقاط مرزی p_a و q_a را در جهت a به دست بیاور.

3- ماکسیمم فاصله نقاط مرزی را به ازای همه ی جهت ها برگردان:

diameter = max_a ( ||p_a - q_a|| )

سوال: اگر جهت هایی که در نظر می گیریم بردارهایی باشند که با هم زاویه مساوی می سازند (یکنواخت باشند)، به چندتا از آنها نیاز داریم تا فاصله ی هر بردار دلخواه تا آنها فاصله ی حداکثر delta داشته باشد؟ (در فضای d-بعدی)

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

3D:

a=(teta_i, teta_j,teta_k)

v=(a_i,a_j,a_k)

a-v =(teta_i-a_i, teta_j-a_j, teta_k-a_k)

||a-v|| = sqrt( (teta_i-a_i)^2+(teta_j-a_j)^2+(teta_k-a_k)^2) = delta

d-dimensions:

delta_teta = sqrt(1/d)*delta

که delta_teta زاویه بین دو بردار متوالی در هر بعد است. پس تعداد کل بردارهای لازم:

#vectors in 2-d = 2*pi/delta_teta = 2*pi*sqrt(d)/delta

#vectors in d-dimensional space = (#angles in each plane from each base vector)^(d-1)

= (2*pi*sqrt(d)/delta)^(d-1)

= O( 1/delta^(d-1) )

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

*محاسبه ضریب تقریب الگوریتم

فرض کنید قطر بهینه بین نقاط p و q باشد.

تصویر بردار p به q را روی بردار a می خواهیم به دست بیاوریم. (برای این کار می توانیم ضرب داخلی دو بردار را حساب کنیم چون بردار a یکه است.)

|q_a-p_a| >= (q-p).a = |q-p|.|a|.cos (teta) = |q-p|.cos(teta)

(0<= teta <= delta ==> cos(delta) <= cos(teta) <= 1 )

projection >= |q-p|.cos(teta) >= |q-p|.cos(delta)

ALG >= OPT.cos(delta)

( cos(delta) > 1-(delta^2)/2 )

OPT >= ALG >= OPT.(1-(delta^2)/2)

factor: 1-epsilon

(epsilon = (delta^2)/2)

*زمان اجرا

=هزینه ی تصویر کردن نقاط در این بعدها

#points * #directions = n*1/O(epsilon^((d-1)/2)) = O( n/epsilon^*(d-1)/2) )

4-بهبود الگوریتم قبل

ایده: ترکیب الگوریتم های 2 و 3 برای به دست آوردن تقریب بهتر

الگوریتم:

1) رند کردن نقاط به نقاط توری (الگوریتم 2)

2) رند کردن نقاط جدید در جهت های مختلف (الگوریتم 3)

*ضریب تقریب الگوریتم

ضریب تقریب آنها در هم ضرب می شود:

(1-epsilon)(1-epsilon)=1-2epsilon=1-epsilon'

*زمان اجرای الگوریتم:

step1: O( n+1/epsilon^(d-1) ), n'=#grid_pts = 1/epsilon^(d-1)

step2: O(n'*1/epsilon^(d-1)/2)

O( n+1/epsilon^(d-1)+1/epsilon^(d-1)*1/epsilon^(d-1)/2) = O(n+1/epsilon^(3(d-1)/2) )

5-الگوریتم چان

ایده:

-قدم آخر الگوریتم 2 را به صورت بازگشتی روی d حل کنیم.

-زیرمساله کلی تری را حل کنیم: دیاگرام ورونوی گسسته (DVD)

**دیاگرام ورونوی گسسته

تعریف مساله: مجموعه ای P از n نقطه از رئوس توری d بعدی u x u داده شده است، به ازای هر نقطه q کوئری (dبعدی) دورترین همسایه از q را از بین نقاط P پیدا کنید.

راه حل معمولی: امتحان کردن همه ی حالت ها:

O(n^2)

#points = n <= #grid points = u^d

O( u^(2d) )

مشاهده: دورترین همسایه نسبت به نقطه = دورترین همسایه نسبت به راس توری متناظر آن نقطه

اثبات:

نقطه q، دورترین همسایه p، راس توری متناظر نقطه q^

اثبات با شکل: فرض کنید وسط لابی دانشکده ایستاده اید، سر شما نقطه q است و دورترین نقطه در صفحه ی کف دانشکده (که توری هم هست!) نقطه ی p است و پای شما نقطه ی q است. هر نقطه ای که در صفحه ی کف دانشکده نسبت به سر شما دورترین باشد، نسبت به پای شما هم دورترین است.

(فرض کنید روی یکی از راسهای توری ایستاده اید چون کلا مساله گسسته است)

الگوریتم دیاگرام ورونوی گسسته: (d بعد، مجموعه نقاط P)

1) دیاگرام ورونوی گسسته را برای صفحه های توری عمود بر محور d به دست بیاورید. (همین تابع را با d-1 صدا کنید.)

2) برای هر خط عمودی توری L، دورترین همسایه هایی که در مرحله ی 1 نسبت به این خط پیدا کرده اید (چون در مرحله قبل برای همه ی خطوط توری حساب کرده بودیم)، S_L بنامید.

3) برای هر نقطه توری q روی خط L، دورترین همسایه ی q از اعضای S_L را گزارش کنید.

تحلیل:

زمان الگوریتم:

u^(d-1) = #grid cells in (d-1) dimensions (u x u grid)

u = #points in current dimension

u = finding the farthest point in u (d-1)-hyper-plane (grid)

==> T(d,u) = u*T(d-1,u)+O(u^(d-1)*u*u)

T(1,u) = O(u^2)

T(d,u) = O(u^(d+1))

*زمان الگوریتم قطر 4 (چان)

(در مرحله ی آخر الگوریتم 2(توری) از دیاگرام ورونوی گسسته استفاده کرد.)

u=1/epsilon d'=d-1==>d'+1=d

O(n+1/epsilon^d)

*ضریب تقریب مثل قبل.

*بهترین الگوریتم فعلی:

O( n+1/epsilon^(d-3/2) )

Open problem: O( n+1/epsilon^((d-1)/2) )

نمونه گیری تصادفی و رند کردن تصادفی LPها (فصل 5 WS)

تضمین عملکرد الگوریتم تقریبی که انتخاب تصادفی می کند، امیدریاضی (expected value) جواب به دست آمده نسبت به {بر حسب} جواب بهینه است، وقتی روی همه ی انتخاب های تصادفی حساب شود.

در اکثر موارد می توانیم نشان دهیم الگوریتم های تقریبی تصادفی می توانند غیرتصادفی (derandomized) بشوند: یعنی می توانیم از روشهای ریاضی شناخته شده مانند امیدریاضی شرطی برای تولید یک نسخه قطعی از الگوریتم است که همان تضمین عملکرد را دارد. پس فایده ی تصادفی بودن چیست؟ معمولا همیشه بیان و تحلیل نسخه تصادفی الگوریتم از نسخه قطعی حاصل از غیرتصادفی کردن آن ساده تر است. پس تصادفی کردن سادگی در طراحی و تحلیل الگوریتم را می دهد، اما غیرتصادفی کردن تضمین عملکرد قطی می دهد.

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

همچنین گاهی می توانیم با احتمال بالا تضمین عملکرد الگوریتم تقریبی تصادفی را بدهیم. یعنی احتمال اینکه تضمین عملکرد نادرست باشد یک بر چندجمله ای بر حسب اندازه ورودی است. معمولا می توانیم این چندجمله ای را هرقدر می خواهیم بزرگ کنیم (و در نتیجه هر چقدر می خواهیم احتمال را کم کنیم) که تضمین عملکرد را با یک ضریب ثابت بدتر می کند. اینجا غیرتصادفی کردن کمتر لازم است، هر چند گاهی با روشهای پیچیده تری امکان پذیر است.
دو الگوریتم تصادفی برای مسائل maximum satisfiability و maximum cut می دهیم. نشان می دهیم که جوابی که به صورت تصادفی یکنواخت از مجموعه جوابها انتخاب شده باشد، یک الگوریتم تقریبی تصادفی خوب می دهد. برای مساله تصدیق بیشینه می توانیم از این هم جلوتر برویم و نشان دهیم انتخاب غیریکنواخت (بایاس شده) به تضمین عملکرد بهتری می رسد.

سپس کرانهای چرنف را می دهیم که به ما امکان می دهند که احتمال خیلی دور بودن مجموع متغیرهای تصادفی از امیدریاضی آنها را به کرانهایی محدود کنیم.

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

یک الگوریتم ساده برای تصدیق بیشینه (MAX SAT) و برش بیشینه (MAX CUT)

برای هر کدام از این دو مساله یک الگوریتم تصادفی 1/2-تقریبی می دهیم.

در مساله MAX SAT، ورودی شامل n متغیر x_1 و ... و x_n است که true یا false هستند؛ m عبارت C_1 و ... و C_m که یای منطقی متغیرها و نقیض آنها هستند؛ وزن های نامنفی w_j برای C_j. هدف مساله پیدا کردن تخصیصی از true/false به x_i ها است که وزن عبارتهای صادق را بیشینه کند. یک عبارت صادق است، اگر یکی از متغیرهای نقیض نشده ی آن true شود، یا یکی از متغیرهای نقیض شده آن false شود.

تعاریف:

literal: به x_i و نقیض آن x'_i می گویند.

positive literal: خود x_i

negative literal: نقیض متغیر = x'_i

اندازه یا طول: تعداد literal های یک عبارت: L_j برای C_j

عبارت یکه: عبارت با طول 1

بدون از دست رفتن عمومیت مساله فرض کنید هیچ literal ای در یک عبارت تکرار نشده باشد. فرض کنید هر دوی x_i و x'_i هم در یک عبارت نباشند. فرض کنید عبارتها متمایز هستند (چون اگر مشابه باشند یکی از آنها را نگه می داریم و وزن مجموع آنها را به آن اختصاص می دهیم.).

الگوریتم تصادفی:

با احتمال 1/2 هر متغیر x_i را true می گذاریم. دید دیگر به این حل برای مساله انتخاب تصادفی یکنواخت مقادیر متغیرها از بین همه ی حالتها است. این الگوریتم تقریب خوبی از مساله به ما می دهد.

قضیه: ثابت کنید ضریب تقریب الگوریتم بالا 1/2 است.

اثبات: متناظر هر عبارت یک متغیر Y_j در نظر بگیرید که اگر آن عبارت صادق باشد 1 و در غیر این صورت 0 باشد. در این صورت مجموع وزن عبارتهای صادق به صورت زیر است:

w = sum_j_1_m (Y_j*w_j)

فرض کنید OPT جواب بهینه برای این نمونه از مساله MAX SAT باشد. طبق خطی بودن امید ریاضی داریم:

E(w) = sum_j_1_m (w_j*E(Y_j)) = sum_j_1_m (w_j*pr(C_j=true))

برای هر عبارت C_j که j =1...m، احتمال صادق نبودن آن احتمال این است که هیچ کدام از متغیرهای درون آن درست نباشند (نقیض آنها نادرست). پس چون احتمال درست/نادرست بودن 1/2 است:

pr(C_j = true) = (1-1/2^L_j) >= 1/2

که این نامساوی به دلیل L_j >=1 بودن درست است. پس:

E(w) <= sum_j_1_m(w_j*1/2) = 1/2 sum_j_1_m(w_j) >= 1/2 OPT

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

(پایان اثبات)

دقت کنید که اگر L_j >= k باشد (برای همه عبارتها)، آنگاه الگوریتم ما 

1-1/2^k

تقریبی است. پس عملکرد آن روی MAS SAT ای که عبارتهای طولانی داشته باشد بهتر است.

مثال tight: حالتی که L_j = 3 باشد را MAX E3SAT می نامند. تقریب آن با این روش 7/8 به دست می آید که در صورتی که P=NP نباشد جواب بهتری برای آن نیست.

(اثبات: فصل 16.3 کتاب!)

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

در مساله برش بیشینه ورودی یک گراف بدون جهت است که یالهای وزندار نامنفی دارد. هدف افراز راسها به دو مجموعه U و V است که وزن یالهای بین این دو قسمت ماکسیمم شود که به آن برش می گوییم. در حالتی که وزن یالها 1 باشد، به آن مساله برش بیشینه بدون وزن می گویند.

الگوریتم با ضریب تقریب 1/2 و تصادفی:

هر راس را با احتمال 1/2 در یکی از مجموعه ها می گذاریم. (مشابه سوال قبلی). این کار در واقع نمونه گیری یک جواب به صورت یکنواخت از فضای همه ی جوابها (حالتهای مساله) است.

اثبات ضریب تقریب: متغیر X_ij را 1 بگیرید اگر یال (i,j) در برش بود و 0 در غیر این صورت. Z را متغیر تصادفی بگیرید که جمع وزن یالهای برش است. پس:

Z = sum_(i,j) (w_ij*X_ij)

E(Z) = sum_(i_j) (w_ij*E(X_ij)) = sum_(i,j) (w_ij*pr( (i,j) in cut) )

OPT را هم جواب بهینه این مساله بگیرید. (برای این ورودی).

احتمال حضور یال (i,j) در برش به اندازه ی احتمال حضور هر سر آن در هر کدام از این مجموعه هاست که 2/4=1/2 است، پس:

E(Z) = 1/2 sum_(i,j) (w_ij) >= 1/2 OPT

چون وزنها نامنفی هستند، جواب بهینه کمتر مساوی جمع وزن ها است.

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

غیر تصادفی کردن

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

برای مساله تصدیق بیشینه (MAX SAT)، به جای انتخاب تصادفی مقدار درست یا نادرست برای متغیر، یک روش دیگر به کار می بریم که همان مقدار امیدریاضی آن را بدهد. مقادیر متغیرهای یکی بعد از دیگری تعیین می شود.

اول فرض کنید ما فقط مقدار x_1 را قطعی تعیین می کنیم و بقیه با همان احتمال 1/2 تعیین می شوند. پس بهترین راه مقداردهی آن این است که امیدریاضی جواب را بیشینه کنیم. یعنی امیدریاضی w (وزن عبارتهای درست) را به شرط درست بودن x_1 و امیدریاضی w را به شرط نادرست بودن x_1 به دست بیاوریم و هر کدام مقدار x_1 را بیشتر کرد، آن را به عنوان مقدار x_1 در نظر می گیریم. این از نظر شهودی منطقی است، چون ماکسیمم از میانگین بیشتر است و امید ریاضی W میانگین آن روی دو مقدار ممکن x_1 است. در این حالت، یک نسخه ی الگوریتمی از امید ریاضی که حداقل نصف بهینه است به دست می آوریم که تعداد متغیرهای تصادفی را کمتر می کند.

به صورت ریاضی:

if E(W|x_1=true) >= E(W|x_1=false) ==> x_1 = true, else x_1 = false

(conditional probability) ==>

E(W) = E(W|x_1=true)Pr(x_1=true)+E(W|x_1=false)Pr(x_1=false) = 1/2 (E(W|x_1=true)+E(W|x_1=false)

b1=arg max( E(W|x_1=b1) ) ==> E(W|x_1=b1) > E(W)

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

با استقرا برای حالتی که مقدار متغیرهای قبلی مشخص شده باشد برای متغیر x_i به همین صورت مقدار انتخاب می کنیم. بعد از تعیین آخرین متغیر، وزن به دست آمده از الگوریتم ما بیشتر مساوی مقدار به دست آمده از الگوریتم تصادفی است که آن هم از نصف بهینه بیشتر است. پس الگوریتم 1/2-تقریبی است.

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

(پایان اثبات)

تکنیک غیرتصادفی کردن برای انواع زیادی از الگوریتم های تصادفی کار می کند که در آنها متغیرها به صورت مستقل مقداردهی می شوند و احتمالات شرطی در زمان چندجمله ای قابل محاسبه هستند. این کار گاهی روش امیدریاضی شرطی (method of conditional expectation) هم نامیده می شود، چون از امید ریاضی شرطی استفاده می کند. برای برش بیشینه هم با استدلالی دقیقا مثل سوال قبل می توان به نسخه ی غیرتصادفی 1/2-تقریبی برای آن رسید.

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

پرتاب سکه نامتقارن

چطور می توانیم الگوریتم تصادفی تصدیق بیشینه (MAX SAT) را بهبود دهیم؟ نشان می دهیم که با نامتقارن کردن احتمال مقادیر x_i یعنی با احتمالی به غیر از 1/2 می توانیم آن را بهبود دهیم. برای این کار ساده تر است MAX SAT هایی را در نظر بگیریم که هیچ عبارت یکه (با یک متغیر) x'_i ندارند، یعنی هیچ پرانتری ندارند که درون آن فقط نقیض یک متغیر باشد). بعدا نشان می دهیم که می توانیم این فرض را حذف کنیم. فرض کنید مقدار x_i را با احتمال p>1/2 درست (true) بگذاریم. مشابه قبل باید احتمال صادق بودن هر عبارت را به دست بیاوریم.

لم: با فرض درست بودن مقدار x_i با احتمال p>1/2 به صورت مستقل، احتمال اینکه هر عبارتی صادق باشد حداقل به اندازه ی مینیمم p و 1-p^2 است.

اثبات: اگر فقط یک متغیر داشته باشد احتمال p است. اگر عبارت طول حداقل 2 داشته باشد، احتمال درست بودن آن 

1-p^a*(1-p)^b

که در آن a تعداد متغیرهای نقیض شده و b تعداد متغیرهای معمولی در این عبارت است که a+b=L_j>=2 است. داریم:

1-p < 1/2 < p ==> pr( clause = true ) >= 1-p^(a+b) = 1-p^L_j >= 1-p^2

(پایان اثبات).

بهترین تضمین جواب را وقتی به دست می آوریم که p=1-p^2 باشد که نتیجه می دهد: p=1/2(sqrt(5)-1)=0.618

از این لم قضیه زیر نتیجه می شود:

قضیه: با کاری که گفته شد به الگوریتم تصادفی min(p,1-p^2)-تقریبی می رسیم، برای مساله تصدیق بیشینه که پرانتر فقط دارای یک متغیر نقیض شده نداشته باشد.

اثبات:

E(W) = sum_j_1_m (w_j*Pr(C_j=true) ) >= min(p,1-p^2)*sum_j_1_m( w_j ) >= min(p,1-p^2)*OPT

(پایان اثبات).

می خواهیم این را به تصدیق بیشینه تعمیم بدهیم، پس از کرانی بهتر از جمع وزن عبارتها استفاده می کنیم. فرض کنید برای هر i وزن عبارت فقط شامل این متغیر حداقل به اندازه وزن عبارت شامل فقط نقیض آن باشد؛ این بدون از دست رفتن عمومیت مساله برقرار است، چون در غیر این صورت تغییر متغیر می دهیم و نقیض آن را به عنوان متغیر می گیریم. v_i را وزن پرانتز شامل فقط نقیض x_i بگیرید و اگر وجود نداشت آن را 0 بگذارید.

لم: جواب بهینه کمتر مساوی مجموع وزن عبارتها منهای مجموع وزن پرانتزهای شامل فقط نقیض متغیرها است.

اثبات:

برای هر i جواب بهینه یا x_i را درست می گذارد یا نقیض آن را. پس وزن جواب بهینه نمی تواند شامل هر دوی عبارت های تک متغیری خود متغیر و نقیض آن باشد و وزن نقیض هر متغیر را کمتر از خودش گرفتیم پس لم درست است.

قضیه: می توانیم الگوریتم تقریبی تصادفی با ضریب 1/2(sqrt(5)-1) به دست بیاوریم. (برای مساله تصدیق بیشینه).

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

این الگوریتم می تواند با روشی که گفته شد غیرتصادفی شود.

coreset: تقریب گستره نقاط

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

محاسبه قطر نقاط

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

اسلایدهای تیموتی چان

جلسه اول

قطر: تعدادی نقطه در فضای d-بعدی داده شده است، فاصله ی دورترین دو نقطه چقدر است؟

for all p,q in P: diameter = max_p_q (distance(p,q)) = max_p_q( ||p-q|| )

کاربردها: ساده ترین روش برای پیدا کردن شکل نقاط است.

الگوریتم دقیق:

1-به دست آوردن فاصله ی همه ی زوج نقطه ها و ماکسیمم گرفتن: O(n^2)

2-استفاده از anti podal pair (زوج خطوط موازی که همه نقاط بین آنها قرار می گیرند): O(nlogn)

- در دو بعد با به دست آوردن پوسته محدب نقاط

3- در سه بعد با روش تصادفی clarkson, shor 1998، روش قطعی Ramos 1991 زمان O(nlogn)

4- در چهار بعد O(n^4/3 polylog(n)) ارائه شده توسط Matousek 1992

5- در d بعد O(n^ (2-2/(ceil(d/2)+1))

الگوریتم تقریبی:

تعریف جدید مساله: diameter را طوری پیدا کنید که به ازای ثابت c داشته باشیم:

diameter <= diameter_OPT <= c*diameter

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

0- یک نقطه دلخواه از بین نقاط را برداریم و فاصله ی دورترین نقطه از بین نقاط از آن را به عنوان قطر برگردانیم.

زمان: O(dn) : این بهترین زمانی است که برای حل این مساله هست.

ضریب تقریب: 2

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

مزیت الگوریتم: یک بار دیدن داده ها برای آن کافی است. این در الگوریتم هایی که روی جویبار داده (data stream) کار می کنند مهم است.

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

زمان الگوریتم: O(dn)

برخلاف الگوریتم قبلی دو بار باید داده ها را ببیند.

ضریب تقریب: رادیکال 3

اثبات ضریب تقریب:

نقطه دلخواه را p بگیرید دورترین همسایه آن را q بگیرید و t را دورترین نقطه از دورترین همسایه بگیرید.

می خواهیم بین فاصله ی q و t (جواب الگوریتم) و بیشترین فاصله زوج نقاط (جواب بهینه) یک رابطه به دست بیاوریم.

دایره به مرکز q و شعاع قطر نقاط (به دست آمده از الگوریتم که همان ||q-t|| است) می زنیم. همه ی نقاط درون این دایره می افتند چون t دورترین نقطه به q است. نقطه ی p هم درون این دایره است. از مرکز دایره q به p یک خط رسم کنید تا محیط دایره را قطع کند و از آنجا یک دایره به شعاع قطر به دست آمده از الگوریتم بزنید. این دایره از q می گذرد، چون مرکز آن روی محیط دایره بوده و شعاع آن با شعاع این دایره برابر بوده است. مرکز این دایره دوم را o بنامید.

به ازای هر نقطه از نقاط ورودی مثل x می دانیم فاصله ی آن از o کمتر از جمع فاصله x از p و فاصله p از o است (نامساوی مثلث):

||x-o|| <= ||x-p||+||p-o|| <= ||p-q||+||p-o||=||o-q|| = r = ||q-t||

یعنی همه ی نقاط درون این دایره دوم هم می افتند.

دورترین فاصله ی دو نقطه در اشتراک این دو دایره، فاصله ی نقاط تقاطع آنها است، که رادیکال سه برابر شعاع دایره ها می شود. پس ضریب تقریب رادیکال 3 است.

{اگر به مرکز p و شعاع ||p-q|| دایره می زدیم، همه ی نقاط درون آن بودند چون دورترین نقطه از p نقطه q بود. به جای آن از دایره ای که این دایره به آن مماس داخل بود استفاده کردیم که هم شامل این دایره بشود هم تحلیل ساده تر باشد. در واقع بدترین حالت را در نظر گرفتیم که p دورترین نقطه به q بود علاوه بر t!}

2- الگوریتم Barequet, Har-Peled 1999

ایده: رند کردن نقاط با استفاده از توری {به نزدیک ترین گوشه توری}

{این الگوریتم از الگوریتم های تقریبی است که درون آنها از یک الگوریتم تقریبی دیگر استفاده می شود. همان حالتی که ضریب تقریب ها در هم ضرب می شوند.}

1) یک جواب تقریبی با یکی از الگوریتم های قبلی به دست بیاور. (ضریب تقریب آن را c فرض کنید.)

2) به ازای یک epsilon توری diameter*...*diameter با خانه های به طول epsilon*diameter بساز. (تعداد خانه های توری به این صورت است:)

c*diameter/(epsilon*diameter) *...* c*diameter/(epsilon*diameter) = (c/epsilon)^d

3) هر نقطه از نقاط داده شده را به نزدیک ترین گوشه ی خانه های توری رند کن.

4) فاصله ی دورترین نقاط جدید (راسهای توری) را به عنوان قطر برگردان.

زمان اجرا :

تعداد نقاط جدید (رند شده) = حداکثر به تعداد نقاط توری =

(2^d)*(c/epsilon)^d

{دو به توان d تعداد گوشه های هر خانه توری در d بعد است! برای دو بعد می شود 4 گوشه!}

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

O( n+1/(epsilon^2d) )

که قسمت O(n) مربوط به ساخت توری و قسمت O((1/epsilon)^2) مربوط به اجرای الگوریتم دقیق O(n^2) روی نقاط توری است.

ضریب تقریب: 1+epsilon

اثبات:

فاصله ی هر نقطه تا نقطه ی رند شده ی آن یعنی نزدیک ترین گوشه ی خانه ی توری که یک مکعب d بعدی به طول ضلع epsilon*diameter است، حداکثر به اندازه ی نصف قطر مکعب است (حالتی که نقطه دقیقا وسط مکعب باشد) یعنی:

(epsilon*diameter)*1/2*sqrt(1+1+...+1) = (epsilon*diameter)*sqrt(d)/2

حالا می خواهیم با استفاده از آن تقریب جواب را به دست بیاوریم. برای هر دو نقطه p و q از نقاط اولیه که رند شده ی آنها p' و q' هستند، طبق نامساوی مثلث داریم:

||p-q|| <= ||p-p'||+||p'-q||

||p'-q|| <= ||q-q'||+||p'-q'||

==> ||p-q||-||p'-q'|| <= ||p-p'||+||q-q'|| <= (epsilon*diameter)*sqrt(d)/2*2 = (epsilon*diameter)*sqrt(d)

==> |diameter-diameter_OPT| <= diameter*(epsilon*sqrt(d))

==> diameter_OPT*(1-epsilon*sqrt(d)) <= diameter <= diameter_OPT*(1+epsilon*sqrt(d))

یعنی یک 1+epsilon تقریب برای قطر است.

3-بهبود الگوریتم:

برای هر سطر (یک بعد از توری) نقاط مینیمم و ماکسیمم را نگه داریم.

ضریب تقریب:

O( n+1/(epsilon^2(d-1)) )

روش و اثبات:

{فکر کنم منظورش این باشه که توی هر ابرصفحه ی توری مینیمم و ماکسیمم را در یک بعد نگه داریم، چون اگر توی کل مجموعه باشه که درست جواب نمیده. مخصوصا از تعمیمی که داده این طور به نظر میاد.}

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

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

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