Рандомизирани алгоритам

Рандомизирани алгоритам је алгоритам који користи степен случајности као део своје логике. Алгоритам обично користи униформно распоређене случајне битове као помоћни улаз да воде његово понашање, у нади да ће се постићи добре перформансе у "просечном случају", када се у обзир узму сви могући избори случајних битова. Формално, учинак алгоритма ће бити случајна променљива одређена случајним битовима; Према томе, било текуће време, било излаз (или обоје) су случајне променљиве.

Потребно је направити разлику између алгоритама који користе случајан улаз да би смањили очекивано време извршавања или заузеће меморије, али се увек завршавају са коректним резултатом (Лас Вегас алгоритам) за одређено време, и пробабилистичких алгоритама, код којих, у зависности од случајног улаза, постоји шанса да произведу нетачан резултат (Монте Карло алгоритам) или да не дају никакав резултат, било сигнализирањем грешке или неуспехом да се извршавање прекине.

У другом случају, где је у питању случајано извршавање и насумичан излаз, термин "алгоритам" за поступак је донекле упитан. У случају насумичног излаза, то није више формално ефективни метод.

Како год, у неким случајевима, пробибалистички алгоритми су једини практичан начин за решавање проблема.

У уобичајеној пракси, рандомизирани алгоритми се апроксимирају користећи генератор псеудослучајних бројева уместо изворних случајних битова; таква примена може одступати од очекиваног теоријског понашања.

Мотивација

Као мотивациони пример, размотримо проблем проналажења елемента "а" у неком низу од н елемената.

Улаз: Низ од н≥2 елемената, у коме је половина ‘а’ елемената, а другу половину чине ‘б’ елементи.

Излаз: Пронађено неко ‘а’ у низу.

Дајемо две верзије алгоритма, најпре Лас Вегас алгоритам, а затим Монте Карло алгоритам.

Лас Вегас алгоритам:

findingA_LV(array A, n)
begin
    repeat
        Randomly select one element out of n elements.
    until 'a' is found
end

Овај алгоритам постиже успех са вероватноћом 1. Дужина трајања једног позива варира и може бити произвољно велика, али очекивано време за већину позива је $\Theta (1)$. (Погледај велико О)

Монте Карло алгоритам:

findingA_MC(array A, n, k)
begin
    i=0
    repeat
        Randomly select one element out of n elements.
        i = i + 1
    until i=k or 'a' is found
end

Ако је ‘а’ пронађено, извршавање алгоритма је успешно, иначе је неуспешно. Након к итерација, вероватноћа проналаска елемента ‘а’ је:

$\Pr[\mathrm {find~a} ]=1-(1/2)^{k}$

Овај алгоритам не гарантује успех, али време извршавања је константно. Током много позива селекција се извршава очекивано 1≤к<2 пута, зато је време извршавања једнако $\Theta (1)$.

Рандомизирани алгоритми су нарочито корисни када се суочавате са злонамерним "противником" или нападачем, који намерно покушава да "нахрани" лош улаз у алгоритам (погледај комплексност у најгорем случају и конкурентна анализа (онлине алгоритам)) као што је Дилема затвореника. Из тог разлога је случајност свеприсутна у криптографији. У криптографским апликацијама, псеудо-случајни бројеви се не могу користити, јер их противник може предвидети, правећи ефективан детерминистички алгоритам. Стога је потребно користити или извор заиста насумичних бројева, или криптографски осигуран генератор псеудо-случајних бројева. Друга област где се насумичност користи је квантно рачунарство.

У примеру изнад, Лас Вегас алгоритам увек даје коректан одговор, али његово време извршавања је одређено случајном променљивом. Монте Карло алгоритам (повезано са Монте Карло метода за симулацију) извршава се у константном времену (као функција са улазном величином), али дозвољава малу вероватноћу грешке. Приметимо да се сваки Лас Вегас алгоритам може конвертовати у Монте Карло алгоритам (користећи Марковљеву неједнакост) тако што ће на излазу бити произвољна вредност, где постоји могућност нетачног одговора уколико не успе да се изврши у одређеном року. Обрнуто, ако постоји ефикасан поступак верификације којим можемо проверити да ли је одговор тачан, онда Монте Карло алгоритам може бити конвертован у Лас Вегас алгоритам, покретајући Монте Карло алгоритам у више наврата док се не добије тачан одговор.

Рачунарска комлексност

Теорија комплексности моделује рандомизиране алгоритме као пробабилистичку Тјурингову машину. Оба алгоритма, Лас Вегас и Монте Карло алгоритам се разматрају, и класе сложености се проучавају. Најосновнија рандомизирана класа сложености је РП (рандомизирано полиномијално време), што је класа проблема одлучивања, за коју постоји ефикасан (полиномијално време) рандомизирани алгоритам (или пробабилистичка Тјурингова машина) који препознаје негативне инстанце са апсолутном сигурношћу и позитивне инстанце са вероватноћом од најмање 1/2. Комплементна класа за РП је комплемент-РП.

Класа проблема где се алгоритми извршавају у полиномијалном времену и чији излаз је увек коректан, назива се и пробабилистичко полиномијално време без грешака (ен. зеро-еррор пробабилистиц полyномиал тиме, ЗПП).

Класа проблема где је дозвољено да се и ДА и НЕ-инстанце идентификију са неком грешком назива се пробабилистичко полиномијално време са ограниченом грешком (ен. Боундед-еррор пробабилистиц полyномиал, БПП). Ова класа се понаша као насумични еквивалент од П, односно БПП, и представља класу ефикасних насумичних алгоритама.

Историјат

Историјски, први рандомизирани алгоритам био је метод развијен од стране Мајкла Рабина за алгоритам две најближе тачке у рачунарској геометрији.

Проучавање рандомизираних алгоритама било је подстакнуто 1977. године откићем рандомиизираног теста за просте бројеве (односно, одређивање да ли је број прост) од стране Соловеја и Штрасена. Убрзо након тога, Мајкл Рабин је показао да Милер-Рабинов тест из 1976. може бити претворен у рандомизирани алгоритам. У то време, ни један практичан детерминистички алгоритам за просте бројеве није био познат.

Милер-Рабинов тест за просте бројеве заснива се на бинарној релацији између два позитивна цела броја к и н који се могу изразити речима: " к је сведок сложености броја н ". Може се показати:

• Ако постоји сведок сложености броја н, онда је н сложен број (односно, н није прост број),
• Ако је н сложен број, онда су најмање три четвртине природних бројева мањих од н сведоци његове сложености,
• Постоји брз алгоритам који, уз дато к и н, утврђује да ли је к сведок сложености броја н. Запазимо да то значи да је проблем одређивања да ли је број прост сложености комплемент-РП.

Ако се насумично изабере 100 бројева мањих од сложеног броја н, онда је вероватноћа да се међу њима не нађе "сведок" једнака (1/4)¹⁰⁰, тако да за већину практичних примена, ово је добар тест за одређивање сложености броја. Ако је н велико, може бити да не постоји неки други практичан тест. Вероватноћа грешке може бити редукована на произвољан ниво обављањем више независних тестова.

Из тог разлога, у пракси, нема пенала у вези са прихватањем мале вероватноће грешке, јер, уз мало пажње, вероватноћа грешке може бити астрономски мала. Заиста, иако је у међувремену пронађен детерминистички тест, који одређује да ли је број прост у полиномијалном времену (погледај АКС), у пракси није заменио старије пробабилистичке тестове у криптографији, нити се очекује да се то догоди у блиској будућности.

Примери

Квиксорт

Квиксорт је познат, често коришћен алгоритам, где насумичност може бити корисна. Било која детерминистичка верзија овог алгоритма захтева О(н²) време да сортира н бројева за добро дефинисану класу дегенерисаних улаза (као што је већ сортиран низ), са специфичном класом улаза који генеришу овакво понашање дефинисано протоколом за избор пивота. Како год, ако алгоритам изабере пивот насумице, има доказиво велику вероватноћу да време извршавања буде О(н лог н), независно од карактеристика улаза.

Рандомизиране инкременталне конструкције у геометрији

У рачунарској геометрији, стандардна техника за изградњу структуре као што је конвексни омотач, или Деланијева триангулација јесте да се насумично пермутују улазне тачке и онда једна по једна убацују у постојећу структуру. Насумичност осигурава да је очекивани број измена у структури, изазваних убацивањем, мали, и зато очекивано време извршавања алгоритма може бити ограничено одозго. Ова техника је позната као рандомизирана инкрементална конструкција.

Верификација множења матрица

Улаз: Матрице А ∈ Р^{м × п}, Б ∈ Р^{п × н}, и C ∈ Р^{м × н}.

Излаз: Тачно, ако C = А · Б; нетачно, ако C ≠ А · Б

Дајемо Монте Карло алгоритам као решење овог проблема.

 begin
   i=1
   repeat
       Choose r=(r1,...,rn) ∈ {0,1}n at random.
       Compute C · r and A · (B · r)
       if C · r ≠ A · (B · r)
           return FALSE
       endif
       i = i + 1
   until i=k
   return TRUE
 end

Временска сложеност овог алгоритма је $O(kn^{2})$.

Теорема: Алгоритам је тачан са вероватноћом од најмање $1-\left({\frac {1}{2}}\right)^{k}$.

Доказаћемо да ако $A\cdot B\neq C$ онда $Pr[A\cdot B\cdot r=C\cdot r]\leq 1/2$.

Ако је $A\cdot B\neq C$, по дефиницији имамо $D=A\cdot B-C\neq 0$. Без губљења на општости, можемо претпоставити да је $d_{11}\neq 0$.

Са друге стране, $Pr[A\cdot B\cdot r=C\cdot r]=Pr[(A\cdot B-C)\cdot r=0]=Pr[D\cdot r=0]$.

Ако је $D\cdot r=0$, онда је први унос $D\cdot r$ једнак 0, што је

$\sum _{j=1}^{n}d_{1j}r_{j}=0$

Пошто $d_{11}\neq 0$, можемо решити за $r_{1}$:

$r_{1}={\frac {-\sum _{j=2}^{n}d_{1j}r_{j}}{d_{11}}}$

Ако поправимо све $r_{j}$, осим $r_{1}$, једнакост важи за највише један од два избора $r_{1}\in \{0,1\}$. Зато, $Pr[ABr=Cr]\leq 1/2$.

Пролазимо кроз петљу к пута. Ако је $C=A\cdot B$, алгоритам је увек тачан; ако $C\neq A\cdot B$, вероватноћа добијања коректног одговора је најмање $1-\left({\frac {1}{2}}\right)^{k}$.

Минималан рез графа

Главни чланак: Каргеров алгоритам

Улаз: Граф Г(V,Е).

Излаз:Минималан рез графа Г, у коме су темена подељена у L и Р скупове, са минималним бројем грана између L и Р.

Подсетимо да контракција два чвора, у и в, у (мулти)графу даје нови чвор у', са гранама које представљају унију грана инцидентних са у или в, осим за грану, или гране које спајају у и в. Слика 1 даје пример контракције темена А и Б.

Након контракције, резултујићи граф може имати паралелне гране, али не садржи петље.

Слика 2: Успешно примењен Каргеров алгоритам на граф са 10 чворова. Минимално смањење гафа је величине 3 и означено је бојама темена.

Слика 1: Контракција темена А и Б

Каргеров основни алгоритам:

 begin
   i=1
   repeat
     repeat
        Take a random edge (u,v)∈ E in G
        replace u and v with the contraction u'
     until only 2 nodes remain
     obtain the corresponding cut result Ci
     i=i+1
   until i=m
   output the minimum cut among C1,C2,...,Cm.
 end

У сваком извршавању спољне петље, алгоритам понавља унутрашњу петљу све док не остану 2 чвора, и одговарајући рез је добијен. Време једног извршавања је $O(n)$, где н означава број темена.

Након м извршавања спољне петље, на излазу се налази минимум од свих резултата. Слика 2 даје пример једног извршавања алгоритма. Након извршавања, добијамо минималан рез величине 3.

Лема 1: Нека је к величина минималног реза, и нека је C = {е₁,е₂,...,е_к} минималан рез. Ако, током и-те итерације, ни једна ивица е ∈ C није селектована за контракцију, онда C_и = C.

Доказ: Ако граф Г није повезан, онда Г може бити партиционисан у L и Р скупове, без иједне гране између њих. Дакле, минималан рез неповезаног графа је 0. Сада претпоставимо да је Г повезан. Нека је V=L∪Р подела инукована од стране C : C={ {у,в} ∈ Е : у ∈ L,в ∈ Р } (добро је дефинисано, јер је Г повезан). Размотримо грану {у,в} која припада C. Иницијално, у,в су различита темена. Све док узимамо грану ф различиту од е, не вршити спајање у и в. Зато, на крају алгоритма, добијамо два сложена чвора који покривају читав граф, од којих се један састоји од L, а други од Р темена. На слици 2, величина минималног смањења је 1, и C = {(А,Б)}. Ако не бисмо употребили (А,Б) за контракцију, не бисмо добили минимално смањење.

Лема 2: Ако је Г мултиграф са п чворова, и чији је минималан рез величине к, тада Г има најмање пк/2 ивица.

Доказ: Пошто је к величина минималног реза, сваки чвор в мора задовољити степен (в) ≥ к. Зато, сума свих степена чворова је најмање пк. Али, пошто је познато да је сума свих степена чворова једнака 2|Е|, лема је доказана.

Анализа алгоритма

Вероватноћа да ће се алгоритам извршити успешно једнака је 1 − вероватноћа да ће сви покушаји бити неуспешни.

До независности, вероватноћа да сви покушају буду неуспешни је

$\prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).$

Из леме 1, вероватноћа да је C_и = C је вероватноћа да ни једна грана од C није селектована током и-те итерације. Размотримо унутрашњу петљу и нека Г_ј означава граф након ј контракција грана, где је ј ∈ {0,1,...,н − 3}. Г_ј има н − ј чворова. Искористимо правило ланца условне вероватноће.

Вероватноћа да грана изабрана у ј-тој итерацији није у C, што значи да ни једна грана од C није раније изабрана, је $1-{\frac {k}{|E(G_{j})|}}$. Запазимо да је Г_ј минималан рез величине к, па из леме 2, и даље има најмање ${\frac {(n-j)k}{2}}$ грана.

Следи: $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$.

Дакле, из правила ланца, вероватноћа проналаска минималног смањења C је $Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).$

Отказивање даје $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$. Зато је вероватноћа да алгоритам успе најмање $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$. За $m={\frac {n(n-1)}{2}}\ln n$, ово је еквивалентно са $1-{\frac {1}{n}}$. Алгоритам проналази минималан рез са вероватноћом $1-{\frac {1}{n}}$, у времену $O(mn)=O(n^{3}\log n)$.

Дерандомизација

Насумичност може да се посматра као ресурс, као простор и време. Дерандомизација је онда процес уклањања случајности. Са тачке гледишта рачунарске комплексности, дерандомизација ефикасног рандомизираног алгоритма је питање да ли П = БПП ?

Постоје и специфични методи који могу бити искоришћени за дерандомизацију конкретних рандомизираних алгоритама:

• Метод условне вероватноће, и његова генерализација, Песимистичка процена,
• Теорија неслагања (користи се за дерандомизацију геометријских алгоритама),
• Експлоатација ограничене независности случајних променљивих које се употребљавају у алгоритму, као што је поравнање независности које се користи у универзалном хеширању,
• Употреба експанзионог графа да појача ограничену количину иницијалне случајности (овај последњи приступ је такође познат као генерисање псеудо-случајних битова из насумичног извора, и води до повезане теме о псеудо-случајности).

Где случајност помаже

Када је модел израчунавања ограничен на Тјурингову машину, тренутно је отворено питање да ли могућност прављења случајних избора дозвољава да неки проблеми буду решени у полиномијалном времену, а не могу бити тако решени без ове могућности; Ово је питање да ли је П = БПП. Међутим, у другим контекстима, постоје специфични примери проблема где насумичност доприности стриктним побољшањима.

• На основу почетног мотивационог примера: дат је експоненцијално дуг низ од 2^к карактера, где једну половину чине "а", а другу "б" карактери. Машина са случајним приступом захтева најмање 2^к−1 претрага у најгорем случају да би се вратио индекс од првог пронађеног "а"; ако је дозвољено прављење насумичних избора, очекивани број претрага може бити полиномијалан.

• Природан начин вршења нумеричког рачунања у уграђеним системима или сајбер-физичким системима, јесте да се обезбеди резултат који је приближно једнак тачном, са великом вероватноћом успеха. Велики проблем у вези са проценом губитка (разлика између тачног и приближно тачног решења) може се ефикасно решити ослањањем на сучајност.

• У комуникационој сложености, једнакост два низа може се утврдити са неком поузданошћу користећи $\log n$ битова комуникације са рандомизираним протоколом. Било који детерминистички протокол захтева $\Theta (n)$ битова за одбрану од јаког противника.

• Обим конвексног тела може се проценити рандомизираним алгоритмом до произвољне прецизности у полиномијалном времену. Бáрáнy и Фüреди показали су да ниједан детерминистички алгоритам не може да уради исто то.

Литература

• Цормен, Тхомас Х.; Леисерсон, Цхарлес Е.; Ривест, Роналд L.; Стеин, Цлиффорд (1990). Интродуцтион то Алгоритхмс. Сецонд Едитион. МИТ Пресс анд МцГраw–Хилл. ИСБН 0-262-03293-7.  Цхаптер 5: Пробабилистиц Аналyсис анд Рандомизед Алгоритхмс. стр. 91–122.
• Јон Клеинберг анд Éва Тардос. Алгоритхм Десигн. Цхаптер 13: "Рандомизед алгоритхмс".
• Фаллис, D. (2000). „Тхе Релиабилитy оф Рандомизед Алгоритхмс”. Тхе Бритисх Јоурнал фор тхе Пхилосопхy оф Сциенце. 51 (2): 255—271. дои:10.1093/бјпс/51.2.255. 
• M. Митзенмацхер анд Е. Упфал. Пробабилитy анд Цомпутинг : Рандомизед Алгоритхмс анд Пробабилистиц Аналyсис. Цамбридге Университy Пресс, Неw Yорк (НY), 2005.
• Рајеев Мотwани анд П. Рагхаван. Рандомизед Алгоритхмс. Цамбридге Университy Пресс, Неw Yорк (НY), 1995.
• Рајеев Мотwани анд П. Рагхаван. Рандомизед Алгоритхмс. А сурвеy он Рандомизед Алгоритхмс.
• Пападимитриоу, Цхристос (1993). „11: Рандомизед цомпутатион”. Цомпутатионал Цомплеxитy (1ст изд.). Аддисон Wеслеy. стр. 241—278. ИСБН 0-201-53082-1. 
• M. О. Рабин. (1980), "Пробабилистиц Алгоритхм фор Тестинг Прималитy." Јоурнал оф Нумбер Тхеорy 12:128–38.
• А. А. Тсаy, W. С. Ловејоy, Давид Р. Каргер, Рандом Самплинг ин Цут, Флоw, анд Нетwорк Десигн Проблемс, Матхематицс оф Оператионс Ресеарцх, 24(2):383–413, 1999.