درخت های نزدیک ترین همسایه

http://www.cs.columbia.edu/CAVE/projects/nnsearch/images/nn.png

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

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

مسیریابی: برای حذف بدترین حالت روی ورودی جایگشت رندم اعمال کنیم. + تقارن

روش احتمالاتی: برای حل مسائل ترکیبیاتی از احتمال استفاده کنیم (اثبات). برای این کار دو راه هست:

1-حداقل یک x هست که از E(X) کمتر مساوی باشه و یک x هست که حداقل E(x) باشه.

2-اگر احتمال وجود یک خاصیت در یک چیز که تصادفی از یک مجموعه انتخاب شده، بزرگتر از صفر باشه چیزی وجود داره که اون خاصیت رو داشته باشه!

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

الگوریتم تصادفی -فصل 3

* ساختمان داده های تصادفی

ساختمان داده با عملیات: جستجو، اضافه کردن و حذف کردن

1- آرایه مرتب شده: زمان جستجو O(logn) زمان حذف و اضافه O(n)

2- انواع درخت های جستجوی متوازن: (مثلا red-black tree و BST) زمان جستجو، حذف و اضافه O(logn)

چون پیاده سازی اینها سخت است:

ساختمان داده های تصادفی:

1- Treap

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

زمان جستجو در درخت به عمق آن درخت بستگی دارد.

در treap یک درخت جستجوی دودویی داریم که heap هم هست، یعنی عناصر بالاتر آن اولویت بیشتری دارند. وجود و یکتایی treap با استقرا روی n ثابت می شود.

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

ویژگی treap: هر گره در آن اولویت بیشتر از زیر درخت هایش دارد.

زمان: برای محاسبه ی زمان جستجو باید عمق درخت را حساب کنیم. برای این کار به ازای یک گره ی x مسیر از ریشه به آن گره را در نظر می گیریم. اعداد را بر اساس مقدار آنها مرتب و شماره گذاری می کنیم.

E( depth(Xk) ) = sum(E(Xi))

Xi = 1 if i-th node is in the path root-Xk, 0 otherwise

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

...

الگوریتم تصادفی -فصل 2

انتخاب و مرتب سازی

n عدد متمایز و عدد صحیح i بین 1 تا n داده شده است. می خواهیم i-امین عنصر را پیدا کنیم.

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

زمان الگوریتم معمولی: O(n^2)

worst case analysis: T(n)<= T(n-1)+O(n) ==> T(n) = O(n^2)

مجموعه حالت ها: n عدد

پیشامد: i-امین عدد

راه حل 1:

انتخاب تصادفی: یک عدد تصادفی انتخاب می کنیم، نه الزاما اولین عدد.

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

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

زمان:

Xi: متغیر تصادفی رنک عنصر انتخابی در مرحله i ام الگوریتم

E(T(n)) <= sum_j_1_n( pr(Xi=j)T(max(j,n-j) ) +O(n)

pr(Xi=j) = 1/n

split to close to median & far from median : if j=n/4 ==> max(j,n-j)=3n/4

E(T(n)) <= 1/n*( sum_j_1_n/4(T(n-1))+sum_j_n/4_3n/4(T(3n/4))+sum_j_3n/4(T(n)) )+O(n)

E(T(n)) <= 1/n( n/2*T(n-1)+n/2*T(3n/4))+O(n)

E(T(n)) <= 1/2(T(n-1)+T(3n/4))+O(n)

از شباهت این مساله با مساله پیدا کردن میانه حدس می زنیم جواب آن هم O(n) باشد و با استقرا ثابت می کنیم.

راه حل 2: 

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

انتخاب تصادفی: از تابع میانه استفاده کنیم و با باینری سرچ آن را به دست بیاوریم.

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

T_find_median(n) = O(n/delta)

2*delta=1/2 ==> T_find_median = O(n)

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

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

ایده: غیرتصادفی کردن: روشی ارائه می دهیم که خصوصیت بالا را حفظ کند و تصادفی نباشد.

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

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

زمان: پیدا کردن میانه یک مجموعه 5 عضوی = O(1)

T(n)<=T(n/5)+O(n)+T(7n/10)

چون هر کدام از مجموعه های partition ها حداکثر 7n/10 عضو دارند. (به دلیل تقسیم های بعدی، n/5/2=n/10 و ceiling(5/2)=3 )

در نهایت زمان T(n) = O(n) به دست می آید.

----------

مرتب سازی:

راه حل 1:

ایده: پیدا کردن میانه

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

زمان: در هر قدم الگوریتم همه ی عناصر را با pivot مقایسه می کنیم و با زمان این مقایسه ها در زیر مساله ها جمع می کنیم. پس زمان کل برابر جمع تعداد مقایسه ها است.

متغیر تصادفی: تعداد عناصر مقایسه شده

حداکثر هر عنصر یک بار با یک عنصر دیگر مقایسه می شود پس متغیرهای تصادفی دیگری به شکل Xij تعریف می کنیم که اگر عناصر i و j مقایسه شوند یک می شوند در غیر این صورت صفر.

اگر i و j در هیچ فراخوانی از تابع مرتب سازی حضور نداشته باشند (زیر مساله ها) مقایسه نمی شوند و Xij=0 خواهد بود. در غیر این صورت تنها در صورتی مقایسه می شوند که یکی از آنها به عنوان pivot انتخاب شود.

pr(Xij=1)=2/(j-i+1)

با جایگذاری به زمان nlogn می رسیم.

راه حل 2: 

ایده: استفاده از پیدا کردن میانه با روش تصادفی دوم

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

این راه از راه حل قبلی بدتر است، چون کار تکراری انجام می دهیم. (قسمتی که برای میانه 1/4 را چک می کنیم و بعد برای تقسیم کردن دوباره این کار را انجام می دهیم.) اما در کل همان O(nlogn) می شود.

الگوریتم تصادفی -فصل1

وقتی یه الگوریتم معمولی رو از یه حالت رندم شروع می کنیم تا زمانش به طور میانگین (expected value) بهتر بشه.

چیزهایی که باید حساب کنیم کل حالت های ممکن (S)، یه زیر مجموعه از حالت های ممکن(A)، احتمال اونها (p) و نسبت دادن یه عدد به A یعنی X(متغیر تصادفی) است.

متغیرهای مستقل: متغیرهایی که امید ریاضی حاصل ضرب و احتمال اشتراکشون بشه حاصلضرب امیدریاضی و حاصل ضرب احتمالشون.

نامساوی مارکوف: برای هر X>=0 و t>0 که میانگین X بشه m داریم: pr(x>mt)<=1/t.

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

آزمایش پواسون: اگر در آزمایش برنولی، احتمال موفقیت تغییر کند، یک آزمایش پواسون داریم. تخمین احتمال کرانهای یک آزمایش پواسون رو با نامساوی چرنف به دست میارن.

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

الگوریتم تصادفی تقریبی برای به دست آوردن میانه: (با به طور کلی kامین عدد)

زمان حل کردن دقیق مساله: = k بار مینیمم رو در بیاریم = O(n)

فرض کنید ما دقیقا عدد وسطی رو نمی خوایم فقط می خوایم تقریبا وسط باشه.

راه حل 0: یک عدد رندم انتخاب می کنیم، اگر تقریبا وسط بود به عنوان جواب بر می گردونیم و پایان؛ در غیر این صورت خطا.

زمان : O(n)

الزاما به جواب درست نمی رسه. یعنی هیچ مزیتی نسبت به راه حل معمولی اش نداره.

ایده: سعی و خطا! :) -- پایه الگوریتم تصادفی

پس باید احتمال موفقیت رو افزایش بدیم. احتمال موفقیت در این حالت تعداد اعداد نزدیک به میانه به تعداد کل اعداده، یعنی با فرض ضریب delta برابر میانه احتمال اینکه درست جواب بده میشه 2*delta.

(  (n/2+delta*n/2)+(n/2-delta*n/2)  )/n = 2*delta

راه حل 1:(مانتی کارلو) تعداد ثابتی (c) بار این کار رو انجام بدیم.

زمان: O(c*n)

احتمال خطا:

(1-2*delta)^c

ایده: می دانیم delta*2 عدد بین صفر و یک است. پس توانهای بزرگترش کوچکتر می شوند.

راه حل 2: (لاس وگاس) تکرار تا رسیدن به جواب.

زمان: آزمایش برنولی است که احتمال موفقیت در آن 2*delta است، پس تعداد تکرار برای رسیدن به موفقیت به طور متوسط: 

p_success = 1/(2*delta)

E(T(n)) = O(n)*1/p_success = O(n)*1/(2*delta) = O(n/delta)

ایده: حذف احتمال خطا با احتمال افزایش زمان اجرا

هدف الگوریتم تصادفی: حذف بدترین حالت (زمان اجرا) و رسیدن به متوسط زمان بهتر

مثال: استخدام بهترین منشی: (هر اخراج به اندازه ی f ضرر می زند)

راه حل معمولی: همه را به ترتیب چک کند و هر وقت آدم بهتری پیدا کرد قبلی را اخراج کند. O(nf)

ایده: روی ورودی یک جایگشت رندم اعمال کنیم.

از آنجایی که بهترین را می خواهیم الگوریتم لاس وگاس را باید به کار ببریم.

هزینه الگوریتم: به تعداد افرادی وابسته است که اشتباهی استخدام شده اند = متغیر تصادفی X

X = sum(Xi) ; Xi = 1 if i-th person is hired, 0 otherwise

E(cost(n)) = E(f*X) = f*sum(E(xi)) = f*sum(Pi) = f*(1/1+1/2+...+1/n) = f*ln(n)

نکته: تصادفی بودن نباید روی ورودی باشد، یعنی به آن بستگی داشته باشد.

مثال: اگر هر بار جای عنصر آخر و i ام آرایه را عوض کنیم، رندم نیست.

مثال: اگر هر بار جای یک عنصر رندم و i ام آرایه را عوض کنیم، رندم است.

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

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

http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/course-notes-AA-2013.pdf

این جاییه که استادمون از روش تمرین ها رو داده، احتمالا امتحان هم قراره از همینها بیاد!

میان ترم هندسه محاسباتی

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

"

اول باید CH اون رو حساب می کردم بعد با rotating calipers (و حساب کردن مینیمم فاصله ی اونها) به دست میاوردیمش:

http://cgm.cs.mcgill.ca/~orm/diam.html

"

واقعا گول خوردم وقتی اون بچه ها گفتن اینها رو نمیده دیگه دوره اش نکردم! :| :(( خیلی بد دادم.

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

سوال1: الف) تعداد یالهای تقاطع n خط n^2 است، تعداد یالهای تقاطع n صفحه چندتاست؟

ب) n نقطه و m خط داریم، تعداد تقاطع ها (نقطه های روی خطها) با عوض کردن تعداد نقطه ها و خط ها ثابت می ماند. (خودم دوگان گرفتم)

ج) ثابت کنید اگه یه سری نقطه رو بر حسب x شون مرتب کنیم و هر نقطه رو با بعدی اش چک کنیم، برای محاسبه ی بیشترین زاویه با محور x کافیه.

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

سوال 3: یه چند ضلعی ساده داریم، یه قطر اون رو پیدا کنید. توی O(n).

سوال 4: t تا مثلث داریم، دوگان اینها چی میشه؟ چطوری یه خطی پیدا کنیم که بیشترین تعداد مثلث رو قطع کنه؟

سوال 5: n تا دایره به شعاع یک داریم، در چه صورتی میشه از هر نقطه ی p به هر نقطه ی q رسید؟ (با عبور از اشتراک دایره ها) -- با EMST حل کردم.

سوال 6:  یه افراز از یه مربع می سازیم به این شکل که از پایین ترین نقطه شروع می کنیم یه خط به چپ راست و بالا رسم می کنیم. بعد برای نقطه های بالاتر به ترتیب این کار رو می کنیم. (منظور بر حسب y مرتب شده بودنه). 

الف) ثابت کنید این تعدادش O(n) میشه. (تعداد ناحیه ها)

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

ج) ثابت کنید اگه رندم نقطه اضافه کنیم، متوسط تعداد به روز رسانی ناحیه ها O(1) میشه.

تمرین 2

2.7 Given a doubly-connected edge list representation of a subdivision where

Twin( e)= Next( e) holds for every half-edge e, how many faces can the

subdivision have at most?

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

2.9 Suppose that a doubly-connected edge list of a connected subdivision is

given. Give pseudocode for an algorithm that lists all faces with vertices

that appear on the outer boundary.

مثلا dfs بزنیم روی dcel ببینیم کجا یال بعدی null میشه.

2.10 Let S be a subdivision of complexity n, and let P be a set of m points. Give

a plane sweep algorithm that computes for every point in P in which face

of S it is contained. Show that your algorithm runs in O((n+m) log(n+

m)) time.

سوییپ معمولی میشه دیگه. علاوه بر دو سر پاره خط ها نقطه های p رو هم میدیم.

2.14 Let S be a set of n disjoint line segments in the plane, and let p be a

point not on any of the line segments of S. We wish to determine all

line segments of S that p can see, that is, all line segments of S that

contain some point q so that the open segment pq doesn’t intersect any

line segment of S.Givean O(nlogn) time algorithm for this problem that

uses a rotating half-line with its endpoint at p.

نمی دونم.

3.6 Give an algorithm that computes in O(nlogn) time a diagonal that splits

a simple polygon with n vertices into two simple polygons each with at

most 2n/3+2 vertices. Hint: Use the dual graph of a triangulation.

هر چند ضلعی رو به دو قسمت تقسیم کنه که هر کدوم حداکثر 2n/3+2 راس دارن؟ خب میشد یه چیزی مثل قطر کشید ولی باید مطمئن باشیم توی اون چند ضلعیه میفته.

جوابها:

خب اولی رو با برهان خلف ثابت کرده.

دومی رو نگفته چک کنید null میشه گفته چک کنید جزو outer boundary میشه یا نه.

سومی همین کارو کرده اما قبلش باید مرتب کنیم. گفته اگه جایی به یه نقطه رسیدیم پاره خط زیری رو ناحیه اش رو پیدا می کنیم و اعلام می کنیم، اگر توی BST چیزی زیر p نبود پاره خط بالایی رو ناحیه اش رو بر می گردونیم. حالت خاص هم داشته دو تا: p روی یه یال باشه، p روی یه راس باشه. توی اولی جوابش دو تا فیس میشه که فیس نیم یال اینوری و اونوری یالی هستند که p روشه، تو حالت دوم همه ی نیم یالهایی که از p شروع میشن فیسشون جوابه. گفته به همون دلیلی که توی سوئیپ ما با برگردوندن نقاط تقاطع زمانمون زیاد نمیشه تو حالت دومی هم هم همین اتفاق میفته.

چهار خیلی جالب بود. گفته که بر اساس زاویه نسبت به p مرتب کنید و توی یه priority queue بریزید و توی نقاط انتهایی پاره خط ها عوضش کنید. اونی که بالاتر از همه است دیده میشه.

سوال 5: گراف دوگان این رو می سازه. 

تمرین 1

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

1.3 Let E be an unsorted set of n segments that are the edges of a convex

polygon. Describe an O(nlogn) algorithm that computes from E a list

containing all vertices of the polygon, sorted in clockwise order.

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

1.8 The O(nlogn) algorithm to compute the convex hull of a set of n points

in the plane that was described in this chapter is based on the paradigm

of incremental construction: add the points one by one, and update the

convex hull after each addition. In this exercise we shall develop an

algorithm based on another paradigm, namely divide-and-conquer.

a. Let P1 and P2 be two disjoint convex polygons with n vertices in total.

Give an O(n) time algorithm that computes the convex hull of P1 ∪P2.

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

b. Use the algorithm from part a to develop an O(nlogn) time divide-and-

conquer algorithm to compute the convex hull of a set of n points in

the plane.

الگوریتمش هست دیگه، نقطه ها رو نصف می کنی، CH راستی ها، CG چپی ها و ادغام هم O(n).

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

1.9 Suppose that we have a subroutine CONVEXHULL available for comput-

ing the convex hull of a set of points in the plane. Its output is a list of con-

vex hull vertices, sorted in clockwise order. Now let S = {x1,x2,...,xn}

be a set of n numbers. Show that S can be sorted in O(n) time plus the

time needed for one call to CONVEXHULL. Since the sorting problem

has an Ω(nlogn) lower bound, this implies that the convex hull problem

has an Ω(nlogn) lower bound as well. Hence, the algorithm presented in

this chapter is asymptotically optimal.

اعضای S رو به نقاط xi, xi^2 تبدیل می کنیم و CH اونها رو حساب می کنیم. بعد مرتب شده بر می گردونه. چون بر اساس زاویه مرتب می کنه که tan a = x^2/x = x

خب ببینیم چقدر از این جواب ها درست بوده!

باید سه تا راس رو در نظر می گرفتیم برای حالت بندی پیدا کردن مماس مشترک. خیلی خوبه که هیچ کس اینو نگفته! :| (سوال 1) کلا 4 تا حالت میشه.

یه سوالو جا انداخته بودم:

2.3 Change the code of Algorithm FINDINTERSECTIONS (and of the pro-

cedures that it calls) such that the working storage is O(n) instead of

O(n+k).

الگوریتمی که گفته یه sweep بوده که قرار بوده تقاطع خطوط رو پیدا کنه. خودش گفته که فقط تقاطع پاره خط های مجاور رو نگه دارید (که خط جارو رو قطع می کنن) گفته n تا پاره خط اند حداکثر که دارن خط جارو رو قطع می کنن پس این میشه O(n). بعد گفته تعداد event ها هم خطیه چون همین ها event هم هستند. (در هر مرحله ی الگوریتم: چون برای مرحله ی بعد حذف می کنیم از n بیشتر نمیشه).

تو سوال یک یادم رفت تکراری ها رو باید حذف کنم! :) خودش بر حسب زاویه مرتب کرده. و گفته از کم به زیاد مرتب کنیم CH میشه.