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

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

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

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

simrank

یادآوری می کنم من منبع غیر موثق ام و مسئولیت غلط بودن حرفهام هم به عهده نمی گیرم.

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

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

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

بعد بازگشتی میان حسابش می کنن:

شباهت هر کس با خودش یکه.

در بقیه موارد شباهتش جمع فاصله ی گره های ورودی به اون گره ها تقسیم بر تعدادشونه. تعدادشون که میشه حاصل ضرب تعداد گره های ورودی به x در تعداد گره های ورودی به y. یه ضریب هم توش ضرب می کنن.

شباهتش به random walk هم احتمالا توی اینه که اون گره ای که می خوایم شباهتش رو با x حساب کنیم (مثلا y) یه جایی توی گرافه و باید به مقصد x برسیم. خب توی random walk که می دونیم با بینهایت تا گام حتما میرسیم، میانگین هم کمتر از دو برابر تعداد یالها ضربدر (n-1) میشه (n تعداد راسها). (این آخری رو از رو نگاه کردم. - زندگی سخت شده دیگه میانگین ها هم اون میانگین های قبلی نیستن.)

برای نامتقارن کردنش هم توان 2 ی تعداد یالهای ورودیش رو توش ضرب می کنن.

الآن به اونجایی رسیدم که از random walk بودنش حرف زده، گفته که از گره های x و y شروع می کنیم و گراف رو یالهاش رو خلاف جهت میریم تا به هم برسیم. (توی random walk احتمال رفتن به هر همسایه ای مساویه).

دیگه اینکه برای خروجی هم میشه تعریفش کرد. زمانش هم O(n^2*d^2) میشه که n تعداد راسهاست و d درجه ورودی راسهاست. برای اینکه بهتر کار کنه خودش پیشنهاد کرده که راسهایی از این گراف دومیه رو که خیلی دورند در نظر نگیریم اصلا! (خودش یه شعاع فرض کرده) بعد این باعث شده بشه O(n*d^2).

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

اشکالهایی که هنوز داره اینه که فقط لینک ها رو در نظر گرفته، مقیاس پذیری و کارایی اش مشکل داره (چرا؟ اینکه شعاع r گرفته بود؟) و نمیشه شباهت های دیگه رو باهاش به کار گرفت.