Күтілетін сызықтық уақыт MST алгоритмі - Expected linear time MST algorithm

The күтілетін сызықтық уақыт алгоритмі MST Бұл рандомизацияланған алгоритм есептеу үшін ең аз созылатын орман а өлшенген график жоқ оқшауланған шыңдар. Ол әзірледі Дэвид Каргер, Филипп Клейн және Роберт Таржан.^[1] Алгоритм келесі тәсілдерге сүйенеді Боровканың алгоритмі сызықтық уақытта минималды аралықты тексеру алгоритмімен бірге.^[2]^[3] Ол дизайн парадигмаларын біріктіреді алгоритмдерді бөлу және бағындыру, ашкөз алгоритмдер, және рандомизацияланған алгоритмдер жету күткен сызықтық өнімділік.

Минималды аралықты табатын детерминирленген алгоритмдерге кіреді Прим алгоритмі, Крускалдың алгоритмі, кері жою алгоритмі, және Боровканың алгоритмі.

Шолу

Алгоритмнің негізгі түсінігі графикті екіге бөлетін кездейсоқ іріктеу кезеңі болып табылады ішкі графиктер әр подграфқа қосу үшін кездейсоқ таңдау арқылы. Алгоритм рекурсивті түрде табады ең аз созылатын орман Бірінші кіші проблеманың шешімі және сызықты уақытты тексеру алгоритмімен бірге графикте минималды созылатын ағашта болуы мүмкін емес шеттерді жою үшін қолданылады. Боревканың алгоритмінен алынған процедура графиктің әрқайсысында кішірейту үшін қолданылады рекурсия.

Боровка қадамы

Алгоритмнің әр қайталануы а. Деп аталатын Боровканың алгоритмінің бейімделуіне негізделген Боровка қадамы:

 Кіріс: график G оқшауланған шыңдары жоқ 1 Әр шың үшін v, ең жеңіл жиекті таңдаңыз v    2 Келісілген график жасаңыз G ' әр компонентін ауыстыру арқылы G 1-қадамда таңдалған шеттермен бір шыңмен байланыстырылған 3 Барлық оқшауланған шыңдарды, өзіндік циклдарды және қайталанатын минималды емес шеттерді алып тастаңыз G '  Шығу: 1-қадамда таңдалған шеттер және келісімшартты график G '

Боровка қадамы Боровканың алгоритмінің ішкі циклына сәйкес келеді, ол іске асады O(м) уақыт қайда м - шеттерінің саны G. Сонымен қатар, әр жиекті ең көп дегенде екі рет таңдауға болатындықтан (әр төбеде бір рет) 1-қадамнан кейін ажыратылған компоненттердің максималды саны төбелер санының жартысына тең болады. Осылайша, Borůvka қадамы графиктегі шыңдар санын кем дегенде екі есе азайтады және кем дегенде жояды n/ 2 шеті бар жерде n - шыңдар саны G.

Боревка қадамының орындалуы

Кескін	Сипаттама
	Әр төбедегі ең жеңіл жиек жасыл түспен белгіленеді.
	График жиырылып, 1-қадамда таңдалған шеттермен байланысқан әрбір компонент бір шыңмен ауыстырылады. Бұл екі супернод жасайды. Бастапқы графиктен барлық шеттер қалады.
	Супернодтарға өздігінен цикл жасайтын жиектер жойылады.
	Супернодтар арасындағы минималды емес артық жиектер жойылады.
	Үлгі графигіндегі бір Боревка қадамының нәтижесі - бір шетінен қосылған екі супернодтан тұратын график.

F-ауыр және F-жеңіл шеттері

Әрбір қайталану кезінде алгоритм белгілі бір қасиеттері бар жиектерді оларды ең аз ағаш. Бұлар аталады F-ауыр жиектер және келесідей анықталады. Келіңіздер F бойынша орман бол график H. F-ауыр шеті - бұл шеті e байланыстырушы шыңдар сен,v оның салмағы жолдағы ең ауыр жиектің салмағынан қатаң үлкен сен дейін v жылы F. (Егер жол жоқ болса F ол шексіз салмаққа ие деп саналады). F-ауыр емес кез-келген жиек F-жарық. Егер F Бұл подограф туралы G содан кейін кез-келген ауыр F-жиегі G ең аз болатын ағашта болуы мүмкін емес G бойынша цикл қасиеті. Орманды ескере отырып, F-ауыр шеттерін есептеуге болады сызықтық уақыт ағашты тексерудің минималды алгоритмін қолдану.^[2]^[3]

Алгоритм

Кіріс: график G оқшауланған шыңдары жоқ

Егер G бос орман бос орман
Келісілген график жасаңыз G ' Боровканың екі адымымен жүгіру арқылы G
Ішкі графика жасаңыз H әр шетін таңдау арқылы G ' 1/2 ықтималдықпен. Алгоритмді рекурсивті түрде қолданыңыз H оның ең аз орман алуы үшін F.
F-ауыр жиектерінің барлығын алыңыз G ' (қайда F бұл 3) қадамнан бастап орман болып табылады, алгоритм бойынша сызықтық уақытты ағаштарды тексеру алгоритмін қолданады.^[2]^[3]
Алгоритмді рекурсивті түрде қолданыңыз G ' оның ең аз орман алуы үшін.

Шығарылым: минималды созылатын орман G ' және Боровка баспалдақтарынан жиырылған жиектер

Дұрыстық

Дұрыстық графиктегі шыңдар санына индукция арқылы дәлелденеді. Негізгі жағдай өте маңызды емес. Келіңіздер T * ең аз болатын ағаштар болуы керек G. Боревка қадамында таңдалған барлық шеттерде T * бойынша кесілген мүлік және жиырылған графикті қалыптастыру үшін бірде-бір шеті алынбаған T * бойынша кесілген мүлік (артық шеттер үшін) және цикл қасиеті (өзіндік ілмектер үшін). Қалған шеттері T * 2-қадамда таңдалмаған ең аз ағаш бойынша келісімшартты графиктің кесілген мүлік (әр қиылыс супернод болсын). Әрқайсысы F-ауыр шеті жойылған болса, ең аз созылатын ағашта жоқ цикл қасиеті. Ақыры F ' - индуктивті гипотеза бойынша жиырылған графиктің минималды созылу ағашы. Осылайша F ' және Боревка баспалдақтарынан жиырылған жиектер ең аз ағашты құрайды.

Өнімділік

Күтілетін өнімділік кездейсоқ іріктеу кезеңінің нәтижесі болып табылады. Кездейсоқ іріктеу кезеңінің тиімділігі келесі леммамен сипатталады, ол санына шек қояды F-жарық жиектері G осылайша екінші кіші проблеманың мөлшерін шектейді.

Кездейсоқ іріктеу леммасы

Лемма- Рұқсат етіңіз H тармақшасы болу G әр жиегін қосу арқылы қалыптасады G ықтималдықпен дербес б және рұқсат етіңіз F ең аз орман болуы H. The күтілетін сан туралы F-жарық жиектері G ең көп дегенде n / p қайда n - шыңдар саны G

Лемманы дәлелдеу үшін шеттерін зерттеңіз G олар қосылуда H. Саны F-жарық жиектері G шеттерінің орналасу ретінен тәуелсіз H ең аз созылатын орманнан бастап таңдалады H барлық таңдау тапсырыстарына бірдей. Дәлелдеу үшін жиектерді таңдауды қарастырыңыз H шеттерін алу арқылы G бірінен соң бірі ең жеңілден ауырға дейін. Келіңіздер e қарастырылатын қазіргі шеті болуы керек. Егер соңғы нүктелер e ажыратылған екі компонентте орналасқан H содан кейін e осы компоненттерді қосатын ең жеңіл жиек және егер ол қосылса H ол болады F бойынша кесілген мүлік. Бұл сондай-ақ білдіреді e болып табылады F-жарық қосылғанына немесе қосылмағанына қарамастан H өйткені кейінірек тек ауыр шеттер қарастырылады. Егер екі нүкте де e сол компонентте орналасқан H онда ол (және әрқашан болады) арқылы F-ауыр цикл қасиеті. Жиек e содан кейін қосылады H ықтималдықпен б.

Максималды саны F-жарық жиектер қосылды H болып табылады n-1 кез келген минималды созылатын ағаштан бастап H бар n-1 шеті. Бір рет n-1 F-жарық жиектері қосылды H қарастырылған келесі шеттердің ешқайсысы F шамы емес цикл қасиеті. Осылайша, F-жарық жиектерінің саны G қарастырылған F-жарық жиектерінің санымен шектеледі H бұрын n-1 F-жарық шеттері қосылады H. Кез келген F-жарық жиегі ықтималдылықпен қосылатындықтан б бұл монетаны ықтималдықпен айналдыруға тең б дейін бас көтеру туралы n-1 бас пайда болды. Монеталардың айналуының жалпы саны F-жарық жиектерінің санына тең G. Монета флиптері санының таралуы кері биномдық үлестіру параметрлерімен n-1 және б. Осы параметрлер үшін бұл үлестірімнің болжамды мәні (n-1)/б.

Күтілетін талдау

Рекурсивті субпроблемаларда орындалған жұмысты елемеу алгоритмнің бір шақыруындағы орындалған жұмыстың жалпы көлемі сызықтық енгізу графигіндегі жиектер санында. 1-қадам тұрақты уақытты алады. Borůvka қадамдары көрсетілгендей жиектер саны бойынша сызықтық уақыт бойынша орындалуы мүмкін Боровка қадамы бөлім. 3-қадам шеттер бойынша қайталанады және әрқайсысына бір монетаны айналдырады, сондықтан ол жиектер саны бойынша сызықтық болады. 4-қадам өзгертілген сызықтық уақытты ең төменгі ағаштарды тексеру алгоритмі арқылы сызықтық уақытта орындалуы мүмкін.^[2]^[3] Алгоритмнің бір қайталануында орындалған жұмыс шеттер саны бойынша сызықтық болғандықтан, алгоритмнің бір толық айналымында жасалған жұмыс (барлық рекурсивті шақыруларды қосқанда) бастапқы есепте жиектердің жалпы санынан еселі тұрақты фактормен шектеледі және барлық рекурсивті ішкі проблемалар.

Алгоритмнің әр шақыруы ең көп дегенде екі ішкі проблеманы тудырады, сондықтан ішкі проблемалар жиынтығы а құрайды екілік ағаш. Әрқайсысы Боровка қадамы шыңдар санын кем дегенде екі есе азайтады, сондықтан екі Боровка қадамынан кейін шыңдар саны төрт есе азайды. Осылайша, егер бастапқы график болса n шыңдар және м шеттері тереңдікте г. әрбір кіші проблема ең көбі графикте орналасқан n/4^г. төбелер. Сондай-ақ, ағашта ең көп бөрене бар₄n деңгейлер.

Екілік ағаштың сол жақ жолдары көкпен қоршалған

Рекурсия ағашы туралы ойлау үшін сол жақтағы проблема 3-қадамдағы рекурсивті шақырудағы ішкі проблема, ал оң жақтағы проблема 5-ші қадамдағы рекурсивті шақырудағы ішкі проблема болсын. Бастапқы есеп пен барлық ішкі проблемалардағы жиектердің жалпы санын есептеңіз. ағаштың әр сол жолындағы жиектер санын санау арқылы. Сол жақ жол оң жақтан немесе тамырдан басталады және сол жақтағы балалардың жолы арқылы жетуге болатын барлық түйіндерді қамтиды. Екілік ағаштың сол жақ жолдары оң жақтағы сызбада көк түспен дөңгелектелген.

Сол жақтағы проблеманың әр шеті оның бас проблемасының шеттерінен таңдалады (жиектер аз болған жағдайда жиырылған Боровка қадамдары ) 1/2 ықтималдықпен. Егер ата-ананың проблемасы болса х шеттері, содан кейін күтілетін сан сол жақтағы балалардағы шеттер ең көп х/ 2. Егер х кездейсоқ шамамен ауыстырылады X содан кейін күтудің сызықтығы сол жақтағы баланың проблемасында күтілетін жиектер саны Y арқылы беріледі ${ displaystyle E [Y] leq E [X] / 2}$ . Осылайша, егер сол жақтағы жолдың жоғарғы жағындағы проблемадағы жиектердің күтілетін саны болса к онда сол жолдағы әрбір кіші проблемадағы шеттердің күтілетін санының қосындысы ең көбі болады ${ displaystyle sum _ {d = 0} ^ { infty} { frac {k} {2 ^ {d}}} = 2k}$ (қараңыз Геометриялық қатарлар ). Тамыры бар м шеттері солай күтілетін сан шеттері 2-ге теңм әрбір оң жақ проблеманың шектерінің екі еселенген қосындысы.

Әр оң жақ ішкі проблеманың жиектерінің күтілетін саны - санына тең F-жарық ата-ананың проблемасындағы шеттер, онда F сол жақ проблеманың ең аз таралған ағашы. F-жарық жиектерінің саны подпроблемадағы шыңдар санынан екі есе кем немесе тең сынама алу леммасы. Тереңдіктегі субпроблемадағы шыңдар саны г. болып табылады n/4^г. сондықтан барлық дұрыс ішкі проблемалардағы шыңдардың жалпы саны берілген ${ displaystyle sum _ {d = 1} ^ { infty} { frac {2 ^ {d-1} n} {4 ^ {d}}} = n / 2}$ . Сонымен, бастапқы есепте және барлық ішкі проблемаларда күтілетін шеттер саны ең көбі 2 құрайдым+n. Бастап n ең көп дегенде 2м оқшауланған төбелері жоқ график үшін алгоритм күтілетін уақытта жұмыс істейді O(м).

Ең нашар жағдайды талдау

Ең нашар жұмыс уақыты жұмыс уақытына тең Боровканың алгоритмі. Бұл барлық шақыруларда барлық шеттер солға немесе оңға ішкі проблемаға қосылса пайда болады. Бұл жағдайда алгоритм бірдей Боровканың алгоритмі кіреді O(мин {n², мжурналn}) бар графикте n шыңдар және м шеттері.

Әдебиеттер тізімі

^ Каргер, Дэвид Р .; Клейн, Филипп Н .; Тарджан, Роберт Е. (1995). «Минималды созылатын ағаштарды табудың кездейсоқ сызықтық алгоритмі». ACM журналы. 42 (2): 321. CiteSeerX 10.1.1.39.9012. дои:10.1145/201019.201022.
^ ^а ^б ^c ^г. Диксон, Брэндон; Рауч, Моника; Тарджан, Роберт Е. (1992). «Сызықтық уақыттағы минималды аралықтарды тексеру және сезімталдықты талдау». Есептеу бойынша SIAM журналы. 21 (6): 1184. CiteSeerX 10.1.1.49.25. дои:10.1137/0221070.
^ ^а ^б ^c ^г. Король, Валерия (1995). Ағаштарды тексерудің минималды алгоритмі. Алгоритмдер және мәліметтер құрылымы бойынша 4-ші Халықаралық семинардың материалдары. Лондон, Ұлыбритания, Ұлыбритания: Springer-Verlag. 440-448 бет.

Әрі қарай оқу

Сызықтық уақыттағы ең аз ағашты тексеру

[1] Каргер, Дэвид Р .; Клейн, Филипп Н .; Тарджан, Роберт Е. (1995). «Минималды созылатын ағаштарды табудың кездейсоқ сызықтық алгоритмі». ACM журналы. 42 (2): 321. CiteSeerX 10.1.1.39.9012. дои:10.1145/201019.201022.

[MST-V1-2] а ^б ^c ^г. Диксон, Брэндон; Рауч, Моника; Тарджан, Роберт Е. (1992). «Сызықтық уақыттағы минималды аралықтарды тексеру және сезімталдықты талдау». Есептеу бойынша SIAM журналы. 21 (6): 1184. CiteSeerX 10.1.1.49.25. дои:10.1137/0221070.

[MST-V2-3] а ^б ^c ^г. Король, Валерия (1995). Ағаштарды тексерудің минималды алгоритмі. Алгоритмдер және мәліметтер құрылымы бойынша 4-ші Халықаралық семинардың материалдары. Лондон, Ұлыбритания, Ұлыбритания: Springer-Verlag. 440-448 бет.

[1]

[2]

[3]