الگوریتم های LP (قسمت دوم)

در قسمت قبل الگوریتم های قطعی را دیدیم. در این قسمت الگوریتم تصادفی برای این کار ارائه می شود. :)

2- الگوریتم تصادفی افزایشی seidel برای دو بعد

نیم صفحه = خطی که یک طرف آن مورد نظر است! :))

جواب محدب است: چون تقاطع(اشتراک) یک سری نیم صفحه است.

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

* فکر کنم زمان O(n) برای حساب کردن تقاطع لازم است وگرنه می دانیم خط حداکثر در دو جا CH را قطع می کند و مینیمم گرفتن بین این دو نقطه O(1) می شود.

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

T(n) = T(n-1)+2/n*O(n) = O(n)

در مورد دو nام هم احتمال رخ دادن حالت دوم در الگوریتم است. (زمان بالا expected است.) احتمال اجرا شدن هم برابر با این است که خطی که اضافه می کنیم از جواب فعلی بگذرد که احتمال آن کمتر از این است که از جواب واقعی بگذرد که آن 2 تقسیم بر n است (چون نقطه حداقل تقاطع دو خط است و کلا n خط داریم.)

تعمیم:

برای d بعد زمان d فاکتوریل ضربدر زمان فعلی O(n) می شود. چون هر بار به جای اینکه احتمال ما 2 بر n باشد، d بر n است.

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

3- الگوریتم نمونه گیری تصادفی برای LP ارائه شده توسط clarkson

ایده: نیم صفحه های اضافی را دور بریز

(در واقع تصادفی شده ی همان الگوریتمی است که در قسمت قبل دیدیم.)

اول توضیحی که باید در مورد نمونه گیری تصادفی (random sampling) بدهم: برای اینکه احتمال رسیدن به جواب را در الگوریتم بهتر کنیم، یک سری از کاندیداها را که می دانیم جواب در آنها نیست حذف می کنیم و باید طوری این کار را بکنیم که یکنواخت بودن همچنان باقی بماند. با این کار احتمال اینکه چیزی که انتخاب می کنیم جواب باشد بیشتر می شود.

فضای نمونه: کل شرطها

احتمال انتخاب جواب بدون نمونه گیری (مثل قسمت قبل کمتر از 2 تقسیم بر n است.)

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

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

با نمونه گیری انجام شده، احتمال اینکه از بین قیدهای انتخاب شده (d*sqrt(n) تا قید) یک راس از CH نهایی باشد، sqrt(n)*lgn است.

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

تعداد اعضای هر نمونه حداقل c*sqrt(n)*lgn باید باشد که احتمال رسیدن الگوریتم به جواب n^-cd شود. (چون راه حل تصادفی است، بین زمان الگوریتم و احتمال رسیدن آن به جواب چنین رابطه ای وجود دارد.)

الگوریتم از نوع las vegas است و احتمال موفقیت (برنولی) در آن c*sqrt(n)*lgn است که وقتی d+1 مرحله انجام می شود به مقدار بالا برای موفقیت می رسیم.

زمان اجرا:

T(n)=(d+1)*T(cd*sqrt(n)logn)+O(d2*n) = O(d*d*n+d^d)

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

بهترین زمان الگوریتم های تصادفی: O(d*d*n+2^sqrt(dlog)) است.