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

وبلاگ تخصصی الگوریتم

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

وبلاگ تخصصی الگوریتم

وبلاگ علمی و مخصوص مباحث الگوریتمی است.
نظر خصوصی نگذارید چون جواب نمی‌دهم نظر عمومی بگذارید بدون نام هم که باشد همانجا جواب می‌دهم.

بایگانی

۱۰۷ مطلب با موضوع «هندسه محاسباتی» ثبت شده است

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

  • اول فرض کنید خط ها موازی محورها باشند:

اگر تصویر این خطها را روی محورها در نظر بگیریم، به سادگی می توانیم تشخیص بدهیم با تصویر مستطیل روی محورها تقاطع دارد یا نه.

  • اگر پاره خط ها در هر راستای دلخواهی باشند: (نه الزاما موازی محورها: افقی و عمودی)
یک راه حل: interval tree شبیه range tree اما برای پیدا کردن نقطه به جای بازه است (ساخت درخت جدا برای x و y - یک بعدی: بازه ها برگ های درخت جستجوی دودویی اند). چک کردن همه ی پاره خط های این ناحیه برای اینکه جواب باشند یا نه زمانبر است، پس از یک درخت دیگر به نام segment tree استفاده می کنیم.

روش لوکاس:

به ناحیه هایی تقسیم کنیم که جواب در آنها یکی است.

یک بعدی:

ناحیه های سر پاره خط ها و ناحیه های شامل پاره خط های یکسان.

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

کوئری: پیدا کردن پاره خط هایی که شامل یک x خاص هستند.

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

نحوه ی کوئری زدن:

از ریشه درخت به سمت برگی که شامل نقطه ی کوئری است حرکت کن و همه ی لیست های پاره خط های گره های میانی را به عنوان جواب برگردان!

زمان کوئری: O(logn+k)

تحلیل فضا:

برگ ها: هر پاره خط حداکثر دو سر دارد، پس بازه های ساخته شده O(n) می شود.

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

کلا: O(nlogn)

نکته: ساختار درخت شبیه درخت بازه ی دوبعدی است! (در حالت یک بعدی)

۲ نظر موافقین ۰ مخالفین ۰ ۰۶ دی ۹۲ ، ۰۸:۵۱
سپیده آقاملائی

(واقعا ناراحت کننده است که هیچ کدام از توانایی های من برای هیچ کس ارزش نداره.)

یک چند ضلعی را با رسم کردن یک سری یال به مثلث تقسیم کنیم.

1- پیدا کردن قطر

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

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

زمان الگوریتم: پیدا کردن قطر: O(n)

T(n) = T(n-1)+O(n)

T(n) = O(n^2)

1- 2- بهبود: قطری را پیدا کن که هر دو چندضلعی کمتر از 2/3n ضلع داشته باشند.

T(n) = 2T(2/3n)+O(n)

T(n) = O(nlogn)

2- استفاده از تجزیه ذوزنقه بندی

اول ذوزنقه بندی را به دست می آوریم، اگر دو راسی که ذوزنقه را می سازند مال یک پاره خط نباشند، آنها را به هم وصل می کنیم. (شکل بکشید!)

چندضلعی های ساخته شده را مثلث بندی کنید.

چندضلعی های ساخته شده با این روش همه half monotone هستند، یعنی هر خط عمودی آنها را در دو نقطه قطع می کند. با graham scan می توان هر چند ضلعی به این شکل را در زمان خطی مثلث بندی کرد. (graham scan: نقاط را یکی یکی اضافه می کند و ccw بودن کنج ساخته شده را چک می کند.)

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

O(nlogn)+O(n)+O(n) = O(nlogn)

زمان ذوزنقه بندی+زمان اضافه کردن یال به ذوزنقه ها+زمان مثلث بندی چند ضلعی های half monotone

نکته: برای چند ضلعی های دارای سوراخ هم کار می کند.

نکته: می توان زمان sort را حذف کرد.

3- الگوریتم افزایشی تصادفی تغییر یافته (سیدل)

به ذوزنقه بندی یکی یکی پاره خط اضافه می کنیم، اگر این پاره خط شماره ی ceil(n/logn^h) بود که h بین 1 و log*n است، ذوزنقه ی شامل یک سر این پاره خط را پیدا می کنیم و بقیه را از روی آن پیدا می کنیم. زمان آن logk/j می شود که k تعداد ذوزنقه هایی است که قطع می کند و j شماره ی ذوزنقه ی اول است. (یعنی ساختمان داده را به روز می کنیم.)

با این کار زمان الگوریتم nlog*n می شود.

۰ نظر موافقین ۰ مخالفین ۰ ۰۶ دی ۹۲ ، ۰۷:۵۲
سپیده آقاملائی

یک مجموعه نقطه داریم در صفحه.

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

یک بعدی: نقاط را مرتب می کنیم و ... .

دو بعدی:

1- k-d tree

اسمش از k dimension tree آمده که به معنی درخت k بعدی است. در حالت دو بعدی، یک عمق در میان x و y است. در هر عمق میانه ی نقاط (از نظر x یا y) به دست می آید و بر اساس آن نقاط را دو دسته می کنیم که فرزندان آن گره می شوند.

زمان ساخت درخت O(nlogn) است و فضای O(n) می گیرد و زمان کوئری آن O(sqrt(n)+k) است.

محاسبه ی زمان کوئری:

T(n) = 2T(n/4)+1 = O(sqrt(n))

نحوه ی کوئری زدن: (پیدا کردن مستطیل با این درخت)

اگر گره ی فعلی برگ است و درون مستطیل می افتد آن را به عنوان جواب برگردان.

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

دلیل زمان کوئری:

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

برای ابعاد دیگر:

یک بعدی: مثل درخت جستجوی دودویی معمولی است فقط دو بار کوئری می زنیم.

سه بعدی: به جای مستطیل مکعب داریم و زمان ساخت درخت nlogn و سایز حافظه n و زمان کوئری n^(1-1/d)+k است.

2- range tree

یک درخت جدا برای x می سازیم و برای نقاط آن زیر درخت (که x آنها در بازه ی مورد نظر است) یک درخت دیگر بر حسب y می سازیم.

تحلیل حافظه: چون هر نقطه در دو گره است (یکبار برای x یکبار برای y ) پس همان O(n) می شود.

تحلیل زمان:

T(n) = 2T(n/2)+O(nlogn)

T(n) = O(nlogn)

طبق حالت دوم قضیه اصلی

n^log(a,b) *logn^k = nlogn

k=1, log(a,b) = 1

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

T(n) = 2T(n/2)+O(n)

T(n) = O(nlogn)

طبق حالت دوم قضیه اصلی

n^log(a,b) = n

k = 0

کوئری زدن:

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

در غیر این صورت در درخت y جستجو کن و جواب را برگردان.

(اگر غیر برگ است اینجا چک کن.)

زمان کوئری:

logn = زمان پیدا کردن x

logn+k = زمان پیدا کردن y

کلا: O(logn*logn)

ایده کلی و تفاوت با حالت 1 (k-d tree)

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

تعمیم: برای d بعد

فضای لازم:

S(d,n) <= 2*S(d,n/2)+S(d-1,n)

S(n) = n*(logn)^(d-1)

برای حلش هم میشه استقرا زد. یعنی فرض کنیم S(d-1,n) = n*(logn)^(d-2) باشه، طبق حالت دوم قضیه اصلی n*(logn)^k که k=d-2 در نتیجه یک logn اضافه میشه و n*(logn)^(k-1) به دست میاد.

حافظه لازم:

T(d,n) <= 2logn*T(d-1,n)+O(logn)

که میشه O(logn^d)

2-2- fractional cascading

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

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

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

این باعث می شود که زمان به O(logn^(d-1)) کاهش پیدا کند. (برای قسمت جستجو روی y و ابعاد بالاتر)

* اگر ساختار داینامیک باشد (حذف و درج داشته باشیم) باید درخت نگه داریم اما باز هم می توانیم همین ایده را پیاده کنیم.

# حالتهای خاص

وقتی که x چند نقطه با هم مساوی باشد (یا y) برای اینکه مشکلی پیش نیاید، در مقایسه ی نقاط مختصات را به ترتیب مقایسه می کنیم. (شبیه مقایسه ی pair در c++)

۰ نظر موافقین ۰ مخالفین ۰ ۰۲ دی ۹۲ ، ۱۵:۴۰
سپیده آقاملائی

به دلیل نامعلومی تصمیم گرفتم ارائه هام رو آپلود کنم.

دریافت
عنوان: fault tolerant clustering

دریافت
عنوان: P3C clustering algorithm
توضیحات: projected + subspace

دریافت
عنوان: online unit clustering
توضیحات: randomized clustering

۰ نظر موافقین ۰ مخالفین ۰ ۰۲ دی ۹۲ ، ۱۵:۳۴
سپیده آقاملائی

پیدا کردن نقطه (point location): یک گراف هندسی داریم، آن را طوری پیش پردازش کنید که بتوانیم کوئری های به شکل پیدا کردن فیس شامل یک نقطه را زود جواب بدهیم.

  • یک بعدی:

یک سری بازه روی محور اعداد داریم. (مجزا) می خواهیم ببینیم نقطه در کدام بازه است؟

بازه ها را مرتب می کنیم و باینری سرچ می زنیم! :)

زمان پیش پردازش: nlogn (مرتب کردن)

فضا: n (لیست مرتب شده)

زمان کوئری: logn (باینری سرچ)

با قضیه ben ore ثابت می شود که از logn کمتر نمی شود نقطه را پیدا کرد. (املای اسم طرف رو مطمئن نیستم! :دی)

  • دو بعدی:
به جای اینکه خود مساله را حل کنیم، صورت ساده تری از آن را حل می کنیم که جواب آن مساله ی قبلی را هم می دهد:

مجموعه ای از پاره خط های مجزا داریم که می خواهیم طوری آن را پیش پردازش کنیم که به کوئری های به شکل اولین خط بالای یک نقطه ورودی در زمان کم جواب بدهیم.

روش های 0-2 بر مبنای تقسیم صفحه به نوارهای عمودی از سر پاره خط ها هستند. (slab) اما روش 3 بر مبنای ذوزنقه بندی و روش 4 بر مبنای مثلث بندی هستند. (از سر پاره خط تا قطع کردن پاره خط بعدی)

0- روش Dobkin و Lipton

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

جواب دادن به کوئری: روی x نقطه باینری سرچ می زنیم تا نوار شامل آن را پیدا کنیم. بعد روی y آن باینری سرچ می زنیم تا y را پیدا کنیم.

زمان پیش پردازش: O(n2): اگر بدون sweep انجام بدهیم چون O(n) تا ناحیه (سر پاره خط) داریم و مرتب کردن خطوط هر ناحیه O(nlogn) زمان می خواهد کلا می شود O(n^2logn) اما اگر sweep را یادتان باشد، از روی ناحیه قبلی ناحیه جدید به دست می آید و در نتیجه زمان آن فقط زمان کپی کردن لیست قبلی O(n) می شود برای هر ناحیه که کلا چون n ناحیه است می شود O(n^2).

زمان جواب دادن به کوئری: O(nlogn) (باینری سرچ)

فضای مورد نیاز: O(n^2) : چون n تا لیست به طول n داریم.

1- روش تقسیم و حل

از segment tree استفاده می کنیم.

زمان: nlogn*logn

زمان کوئری: logn*logn

فضا: nlogn

از fractional cascading هم استفاده می کنیم.

زمان: nlogn

زمان کوئری: logn

فضا: n

2- persistent search tree (درخت جستجوی پایدار)

ایده: هر slab (ناحیه بین دو خط عمودی از سر پاره خط ها) با بعدی درختی که می سازد فقط در یک مسیر فرق دارد. (فقط در یک پاره خط تغییر ایجاد شده است، چون سر پاره خط ها را تک تک می بینیم.)

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

زمان کوئری: logn

فضا: nlogn

ایده: path copying

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

زمان: nlogn

زمان کوئری: logn

فضا: n

3- تصادفی افزایشی

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

(قبلا در نمونه سوالهای هندسه محاسباتی توضیح دادم ذوزنقه بندی را.)

الگوریتم:

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

تحلیل:

تعداد راسهای ذوزنقه بندی: 2n+2*(2n)+4 = تعداد دو سر پاره خط ها*2 (تقاطع خطوط دو سر پاره خط ها)+ 4 گوشه ی مستطیل+ تعداد دو سر پاره خط ها

تعداد ذوزنقه ها: 3n+1 = پاره خط اول 4 ناحیه می سازد، اما هر کدام از بعدی ها یک ناحیه کم می کنند و سپس 4 ناحیه اضافه می کنند. پس می شود:

4+(n-1)*(4-1) = 3n+1

تعداد پاره خطهای اطراف هر ذوزنقه: کمتر از 4n

زمان کوئری:

Q(n) = Q(n-1)+O(1/n)

Q(n) = O(logn)

در واقع زمان جستجو زمان رسیدن از مستطیل محیطی ذوزنقه بندی (ریشه گراف جهت دار) به ذوزنقه ی شامل نقطه ی کوئری است. برای به دست آوردن متوسط تعداد این راس ها، این را حساب می کنیم که در مرحله ی i ام که پاره خط si اضافه شده است، این پاره خط به طور متوسط چند ناحیه ایجاد کرده است. تعداد ناحیه هایی که هر پاره خط درست می کند حداکثر 4 تا است. هر کدام از n پاره خط می توانسته اند این ذوزنقه را ساخته باشند، پس احتمال آن n^-1 است که در نتیجه امید ریاضی آن می شود 4*n^-1 که O(1/n) است.

فضای حافظه الگوریتم:

تعداد ذوزنقه های ساخته شده در هر مرحله O(1) است و کلا n مرحله داریم پس کلا O(n) فضا لازم است.

زمان الگوریتم: (پیش پردازش)

در هر مرحله ی الگوریتم یک کوئری زده می شود که logn زمان می برد و ساخت گراف جهت دار هم به اندازه ی تعداد راسهای آن یعنی O(n) زمان می برد.

پس کلا زمان O(nlogn) می برد. (متوسط)

4- روش هرس و جستجو (prune and search)

فرض می کنیم شکل مثلث بندی شده است و به جای ذوزنقه بندی از مثلث بندی استفاده می کنیم.

الگوریتم: هر بار یک راس از مثلث بندی را حذف می کنیم، بعد چند ضلعی جدید را مثلث بندی می کنیم.

این کار را که بازگشتی انجام بدهیم، در قسمت اول به جایی می رسیم که فقط یک ناحیه است (ریشه گراف جهت دار؟!) و با برگشت به قسمت های قبلی و اضافه شدن راس و ساخته شدن مثلث ها گراف کامل می شود.

۰ نظر موافقین ۰ مخالفین ۰ ۰۲ دی ۹۲ ، ۱۳:۵۸
سپیده آقاملائی

مساله های شبیه LP یا LP-type problem ها مساله هایی هستند که با همان ایده ی LP حل می شوند اما LP نیستند.

یکی از ایده هایی که به کار می رود ایده ی seidel است (تصادفی افزایشی).

مثال:

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

پیدا کردن دایره: سه نقطه روی محیط آن یا دو نقطه روی قطر آن

الگوریتم تصادفی welz و Seidel

ایده: یک نقطه روی محیط را داریم.

تابع بازگشتی: circle(S,B) را تعریف می کنیم. در آن S مجموعه نقاط است و B نقاط روی محیط کوچکترین دایره ی محیطی این نقاط است.

شروع الگوریتم: circle(all points, empty)

حالت پایه: اگر S تهی بود یا B سه عضو داشت جواب را برگردان.

یک نقطه ی تصادفی از S را بردار و circle(S-{p},B) را صدا کن.

اگر نقطه ی p درون دایره افتاد همین جواب را برگردان، در غیر این صورت p روی محیط دایره می افتد و circle(S-{p},B U {p}) را برگردان.

( مثل استقرای قهقرایی :) )

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

احتمال اینکه نقطه روی دایره بیفتند : 3 تقسیم بر n (شبیه 2 تقسیم بر n برای LP)

T(n,b) = T(n-1,b)+O(1)+3/n*T(n-1,b+1)

T(n,3) = O(1)

==>

T(n,2) <= T(n-1,1)+O(1)+T(n-1,3)=T(n-1,1)+O(1) ==> T(n,2) = O(n)

T(n,1) <= T(n-1,1)+O(1+3/n*n) ==> T(n,1) = O(n)

T(n,0) = T(n-1,0)+O(1)+3/n*T(n-1,1) <= T(n-1,0)+O(1)+3/n*O(n) = T(n-1,0)+O(1) ==> T(n,0) = O(n) 

تعمیم:

برای حالت d بعدی، زمان (d+1)!n به دست می آید.

بهتر از این هم هنوز حل نشده است. :)

۰ نظر موافقین ۰ مخالفین ۰ ۰۲ دی ۹۲ ، ۱۰:۳۹
سپیده آقاملائی

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

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)) است.

۰ نظر موافقین ۰ مخالفین ۰ ۰۲ دی ۹۲ ، ۰۸:۴۵
سپیده آقاملائی

در قسمت قبل دیدیم که یک سری قید خطی (خط) داریم و می خواهیم در یک جهت اکسترمم (اینجا فرض کنید فقط مینیمم) را به دست بیاوریم.

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

برای شرط هایی که بالای یک خط را نشان می دهند upper envelop را حساب کنیم برای آن شرطهایی که زیر خط بودن رو نشان می دهند lower envelop بعد بین این دو اشتراک بگیریم.

زمان: O(nlogn)

1- الگوریتم هرس و جستجو (prune & search) در دو بعد

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

فرض کنید می خواهیم x را مینیمم کنیم. (با تغییر متغیر می شود به این حالت رسید.)

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

ایده: بالاترین شرط از بین شرطهایی که بالای خط اند و پایین ترین شرط از بین شرطهایی که زیر خط اند را در یک x در نظر می گیریم. اگر این خطها طوری بودند که همین نقطه جزو جواب بود یعنی در x کمتری هم به جواب می رسیدیم، پس سمت چپ می رویم. حالت دیگری هم هست که جواب سمت چپ باشد: اگر شیب خطی که جواب بالای آن است از شیب خطی که جواب پایین آن است کمتر باشد. (اینجا این دو خط در سمت چپ x همدیگر را قطع می کنند.) این حالتی است که از جواب رد شده ایم کلا! :)

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

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

زمان: T(n) = T(3n/4)+O(n)=O(n)

چون هر بار از نیمه ی سمت راست (یا چپ) نصف خطوط حذف می شوند.

تعمیم: برای ابعاد بالاتر هم همین کار را می توان انجام داد و زمان آن در دو به توان دو به توان d ضرب می شود. بهبود یافته ی آن در دو به توان d2 کار می کند. بهترین الگوریتم در n در دو به توان dlogd کار می کند. (d = تعداد ابعاد)

۰ نظر موافقین ۰ مخالفین ۰ ۰۲ دی ۹۲ ، ۰۸:۲۹
سپیده آقاملائی

برنامه ریزی خطی (Linear Programming): تعدادی قید خطی (نامساوی) داریم و می خواهیم یک تابع خطی از همین متغیرها را مینیمم کنیم. بهترین زمان آن O(n) است.

1-خط تقسیم کننده:

دو مجموعه نقطه با n عضو داده شده است. خطی که آنها را تقسیم می کند پیدا کنید.

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

متغیرها: شیب خط و عرض از مبدا خط (جدا کننده)

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

2-برازش خط:

مجموعه n نقطه داده شده است، می خواهیم خطی را پیدا کنیم که فاصله ی عمودی (y) آن با نقاط مینیمم شود.

قید: فاصله عمودی نقاط تا خط (معادله ی خط در x آن نقطه را می نویسیم و منهای y نقطه می کنیم و قدر مطلق می گیریم). این باید بین d و 0 باشد. (برای اینکه خطی شود هر قید را به دو قید تبدیل می کنیم که قدر مطلق را برداریم.)

متغیر: شیب خط و عرض از مبدا خط و d (حداکثر فاصله عمودی یک نقطه تا خط)

تابع هدف: مینیمم کردن d

3- دو دایره هم مرکز پیدا کنید که همی نقاط بین این دو دایره بیفتند و مساحت بین دو دایره مینیمم شود.

تابع هدف: مینیمم کردن مساحت بین دو دایره (مساحت بزرگتر منهای کوچکتر: درجه یک نسبت به توان دو شعاع)

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

متغیرها: R2-x2-y2 و r2-x2-y2 و x و y (مرکز دایره)

4- کوچکترین دایره محیطی

مجموعه n نقطه داده شده است. دایره با کوچکترین شعاع را بیابید که همه ی نقاط را شامل شود.

قید: فاصله هر نقطه تا مرکز دایره (درجه 2)

متغیرها: مرکز دایره و شعاع دایره

تابع هدف: مینیمم کردن شعاع دایره

*خطی نیست اما محدب سه بعدی است.

۱ نظر موافقین ۰ مخالفین ۰ ۰۲ دی ۹۲ ، ۰۷:۱۷
سپیده آقاملائی

درخت بازه و درخت جستجوی با اولویت

http://www.cise.ufl.edu/class/cot5520fa13/CG_WindowingQueriesCh10.pdf

درخت پاره خط ها (سگمنت)

http://www.cise.ufl.edu/class/cot5520fa13/CG_WindowingMoreCh10.pdf

ساختمان داده های هندسی: (این مال یکی دیگه است سر کلاس هم درس نداد. رسما هر ساختمان داده ای که فکر کنید توش هست! آخرین اسلاید یه فهرست داره که لینک به قسمت های دیگه داره.)

http://wwwisg.cs.uni-magdeburg.de/ag/lehre/WS1213/GDS/slides/GeomDS1213.pdf

مرجعش:

http://www.cise.ufl.edu/class/cot5520fa13/

۰ نظر موافقین ۰ مخالفین ۰ ۲۰ آذر ۹۲ ، ۱۵:۳۳
سپیده آقاملائی