Shiber-vishkin algoritmi
![5
I-BOB. ALGORITMNING G’OYASI HAQIDA KELTIRILGAN
MA’LUMOTLAR
1.1. Algoritm g’oyasi
Biz har bir cho'qqi uchun ildizgacha bo'lgan masofani va biz unga kelgan oldingi
cho'qqiga (ajdod) saqlaymiz. Keyin u va v cho'qqilaridan daraxtning ildizigacha
ko'tarilamiz. Har bir qadamda biz ildizdan eng uzoq bo'lgan u yoki v cho'qqisini
tanlaymiz va keyin uning o'rniga uning ajdodini ko'rib chiqamiz, toki boshlang'ich
u va v dan hosil bo'lgan yo'llar bitta cho'qqi - ularning eng kichik umumiy ajdodiga
olib boradi. Daraxtning turli xil variantlari bilan bunday yo'l N bosqichdan iborat
bo'lishi mumkin, bu juda ko'p sonli tugunlar va so'rovlar bilan juda sekin ishlaydi.
Ushbu dastur har bir so'rovni bajarish uchun O (N) vaqtini talab qiladi .
Endi algoritmni yaxshilaymiz.
Har bir cho'qqi uchun biz uzoq daraxtning ildizigacha bo'lgan masofani, uning
bolalari sonini, shuningdek, biz unga oxirgi marta kelgan ajdodimizni (tanlash
quyida aniqlanadi) va raqamni saqlaymiz. cheti ajdoddan chiqadigan cho'qqidan, bu
cho'qqiga burilish yo'lida ...
Kerakli o'zgaruvchilarni e'lon qilaylik, qulaylik uchun bu global xotirada
amalga oshiriladi.
const int SIZE = 100050;
vector<int> v[SIZE]; // har bir cho'qqi uchun qirralarning ro'yxati
bool vis[SIZE]; // o’t ish paytida cho’qqilarni ziyorat qilish haqida eslatmalar
int kids[SIZE]; // Har bir tepalikdagi avlotlar soni
int dist[SIZE]; // Tepadan ildizgacha bo’lgan masofa
int last[SIZE]; // Oldingi cho’qqi raqami
int turn[SIZE];
Endi har bir cho'qqi uchun rekurs iv funktsiyadan foydalanib (k_go (0) ga
qo'ng'iroq qiling), biz uning avlodlari sonini hisoblaymiz:
int k_go(int s) {
int res = 0;](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_5.png)
![6
vis[s] = true;
for(int i = 0, maxi = v[s].size(); i < maxi; i++) {
if(!vis[v[s][i]])
res += k_go(v[s ][i]) + 1;
}
kids[s] = res;
return res;
}
Endi algoritmning tayyorgarlik qismini tugatamiz va har bir cho'qqi uchun
kerakli ma'lumotlarni to'ldiramiz. Biz funktsiyani l_go (0, 0, 0, 1) deb ataymiz:
void l_go(int s, int d, int l, int r) {
vis[s] = true;
dist[s] = d;
last[s] = l;
turn[s] = r;
int maxval = 0;
int idx = -1;
for(int i = 0, maxi = v[s].size(); i < maxi; i++) {
if(!vis[v[s][i]]) {
int k = kids[v[s][i]];
if(k > maxval) id x = v[s][i], maxval = k;
}
}
for(int i = 0, maxi = v[s].size(); i < maxi; i++) {
if(!vis[v[s][i]]) {
if(idx == v[s][i])](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_6.png)
![7
l_go(v[s][i], d + 1, l, r);
else
l_go(v[s][i], d + 1, s, v[s][i]);
}
}
}
Endi men kodning oxirgi qismi qanday ishlashini tushuntiraman, chunki
cho'qqidagi avlodlar sonini topish juda keng tarqalgan vazifadir.
Har bir cho'qqi uchun biz uning avlodlarini ko'rib chiqamiz va ulardan biz eng
ko'p avlodla r soniga ega bo'lgan shunday cho'qqini tanlaymiz. Uning uchun ajdod
haqidagi barcha ma'lumotlar hozirgisidan meros bo'lib qoladi va faqat ildizgacha
bo'lgan masofa o'zgaradi. Ushbu cho'qqining boshqa barcha avlodlari uchun endi
oxirgining ajdodi joriy cho' qqi bo'ladi va navbat bolaning o'zi bo'ladi.
Endi shuni ta'kidlaymanki, agar daraxtda qandaydir a cho'qqisini olsak va
undan ildizga kelgunimizcha, u holda oxirgi ajdodga o'tishlar soni daraxtdagi
cho'qqilar sonining ikkilik logarifmasidan oshmaydi.
Isbot: bitta avlodga ega bo'lgan v tepasida bo'lamiz. Shunda ajdodga nisbatan
oxirgi ishora uni tark etgan avlodda o‘zgarmasligi aniq. Ikki yoki undan ortiq
cho'qqilar bo'lsa, biz bitta avlodni (joriy tugunning barcha avlodlari ichida eng ko'p
avlodlariga ega) olamiz, uning aloqasi joriy va uni yangilaydigan barcha
boshqalaridan meros bo'lib qoladi. Joriy cho‘qqi avlodlarining umumiy sonini N deb
belgilaymiz.
Keyin biz ajdodga havolani yangilaydigan ushbu cho'qqining avlodidan N 2
avloddan ko'p bo'lmagan a vlod bo'ladi (aks holda bu raqam maksimal bo'ladi, lekin
keyin havolani yangilash shart emas). Shunday qilib, oxirgisining ajdodi bo'lgan har
bir cho'qqida, kimdir uchun, undan chiqadigan barcha avlodlarning yarmidan ko'pi
qolmaydi. Bunday yo'lning umumiy uzunligi N ning ikkilik logarifmasidan
oshmaydi.
Endi algoritmning asosiy funksiyasiga o‘tamiz va nima uchun ishlashini
tushuntiramiz.
Shunday qilib, bizda ikkita u va v uchlari bor, ular uchun so'rovga javob
topishimiz kerak. Funktsiyani p = lca (u, v) de b ataylik:
int lca(int a, int b) {](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_7.png)
![8
if(turn[a] == turn[b]) {
if(dist[a] < dist[b]) return a;
else return b;
}
if(dist[last[a]] > dist[last[b]]) return lca(last[a], b);
return lca(last[b], a);
}
Funktsiya rekursiv ravishda ildizga ko'tarila di. Har bir keyingi a va b
cho'qqilari uchun biz birinchi navbatda oxirgi burilish qilingan cho'qqini
tekshiramiz. Agar u mos kelsa, demak, a cho'qqisi ildizdan b cho'qqiga boradigan
yo'lda yotadi yoki aksincha. Qaysi tepa ildizga yaqinroq bo'lishiga qarab , bu kerakli
eng kichik umumiy ajdoddir.
Aks holda, a yoki b cho'qqisini ildizga yaqinlashtirish kerak. Biz ularning
qaysi biri, ajdodiga o'tishda, ildizdan uzoqroqda joylashganligini taxmin qilamiz (bir
cho'qqi doimiy ravishda ildizga boradigan yo'lda ikk inchi cho'qqiga yetib borishga
harakat qiladi). Shunday qilib, ertami -kechmi cho'qqilar bitta cho'qqiga keladi, bu
darhol ularning eng kichik umumiy ajdodi bo'ladi yoki cho'qqilardan biri birinchi
bosqichda tasvirlanganidek, ildizdan boshqa cho'qqigacha bo 'lgan yo'lda yotadi.
Algoritm samaradorligini baholash:
Algoritmni amalga oshirish uchun O (N) xotira (jami xotira 6N iste'mol
qilinadi), O (N) dastlabki hisoblash va barcha so'rovlarga javob berish uchun O (M
* log (N)) vaqti talab qilinadi.
Algoritm oldindan belgilangan daraxt bo'yicha so'rovlarga javob berishga va
har biriga O (log (N)) ga kelgan zahoti javob berishga imkon beradi.](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_8.png)
![9
II -BOB. KOMPL’OS ALGORITMIDAN SHIBER -VISHKIN
ALGORITMIGA O’TISH. SHIBER -VISHKIN ALGORITMI
2.1 Kompl’os algoritmidan Shiber -vishkin algoritmiga o’tish
Kompl’os algoritmi:
Biz birinchi navbatda daraxtning to'liq shoxlangan yoki yo'qligini qanday
tekshirishni muhokama qilamiz (ya'nidallanish omili kamida 2 va barcha barglari
bo'lgan ildizli daraxtbir xil daraja) O(|E|) vazn taqqoslashlari yordamida MST
hisoblanadi.
T sikl xus usiyatiga ko'ra, har bir daraxt bo'lmaganligini tekshirish kifoya
chekka e = (u, v) hech bo'lmaganda eng og'ir cheti kabi og'ir treepath(u, v), bu yerda
treepath(u, v) - bu qirralarning to'plami daraxtdagi u va v tugunlari ulanadi.
G'oya shundan iboratki, har bir daraxt bo'lmagan chekka (u, v) uchun biz
alohida ko'rib chiqamiz oraliqda joylashgan o'rnatilgan daraxt yo'lining (u, v)
chetlarida[root, u] va oʻrnatilgan daraxt yoʻlining chekkalari (u, v) ichida joylashgan
interval [root, v] va bu ikkalasining h ar birida eng og'ir chetini topingdaraxtdan
pastga tushish va ikkilik qidiruvdan foydalanish orqali o'rnatiladi oldingi daraxt
darajasida to'plangan ma'lumotlar.
Keling, buni oddiy misol yordamida tushuntirib beraylik.
treepath(w, z) va treepath(w, x)
Fa raz qilaylik (w, z) va (w, x) daraxt bo'lmagan qirralardir.](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_9.png)
![Tugunni o'z ichiga olgan daraxt yo'llari to'plamini A(v) bilan belgilaymiz
v va [root, v] oralig'i bilan
cheklanib, so'rov qilinishi kerak.](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_10.png)
![daraxt yo'li (v, b) va daraxt yo'li (v, c). Aytaylik, biz har birining eng og'ir
qirrasining og'irligini allaqachon bilamiz A (p) ning yo'li, b u erda p = ota (v).
Bizning maxsus misolimizda, bu Biz daraxt yo'lidagi eng og'ir vaznni allaqachon
bilganimizni anglatadi (p, a), daraxt yo'li (p, b) va daraxt yo'li (p, c). Chunki A(p)
dagi har bir yo'l mavjud A(p) dagi barcha yo'llar undan qisqaroq bo'l sa, bu degani Har bir yo'lning eng og'ir vazniga ko'ra A (p) ning tartibi yo'llarning uzunligi
bilan belgilanadi. A(v|p) A(v) ning yo‘llari bo‘lsin. [root, p] oralig'i bilan
cheklangan. A(v|p) ni aniqlashga e'tibor bering. vazn solishtirishni o'z ichiga
ol maydi va bizning misolimizda buni unutmang. A(v|p) = A(p). A(v|p)
⊆ A(p) bo'lgani uchun, A(v|p) uchun og'irliklar tartibi ham ma'lum. Bu shuni anglatadiki, biz joylashtirish uchun ikkilik qidiruvdan
foydalanishimiz mumkin vazni (v, p) A(v|p) ning og'irlikl ari orasidan olinadi va shu
bilan A (v) ning eng og'ir vaznlari aniqlanadi. Ushbu manba matn haqida ko'proq ma'lumot Qo'shimcha ma'lumot olish
uchun manba matnni kiriting Ko'rib chiqish
Yon panellar
V tugunidagi Koml'os algoritmi
Koml'os algoritmi bilan
bog'liq qiyinchiliklar. Og'irlikni taqqoslashdan tashqari hisoblash qo'shimchalari](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_11.png)
![14
v da ildiz otgan pastki daraxt. LEVEL(v) - v ning ildizdan masofasi, shuning
uchun, masalan. LEVEL(root) = 0. Keyin SIZE jadvalini INLABEL bilan
almashtiramiz jadval, bu erda INLABEL(v) maksimal bo'lgan PREORDER
raqamidir pastki daraxtda (v) yoki [a, b] oralig'ida tugunning eng o'ngdagi “0” bitlari
a = OLDINDAN BUYRUQ (v) va b = OLDINDAN BUYRUQ (v) + SIZE(v) - 1.
Bu bajarilgan: i ← BSR((a − 1) xor b), INLABEL(v) ← (b >> i) << i, bu yerda BSR
- bu "bitni teskari skanerlash" ko'rsatmasi bo'lib, unga ekvivalentdir
blog2 c va eng chap bitning indeksini '1' ga o'rnatadi (dan boshlab indeksi 0
ga teng bo'lgan eng o'ngdagi bit), bu bizning holatlarimizda uchun indeksdir a va b
orasidagi eng katt a quvvat 2 ga teng. Biz ham ASCENDANT ni yaratamiz jadval,
bu erda agar i indeks bo'lsa, ASCENDANT(v) ning th biti '1' ga o'rnatiladi
v ajdodining INLABEL ning eng o‘ngdagi “1” raqamidan. Biz buni shunday
qilamiz ASCENDANT(root) ← 1 << BSR(n) bilan boshlan gan daraxtni kesib o'tish,
va boshqa har bir v tuguniga biz ASCENDANT(v) ni bo'lishini o'rnatamiz
ASCENDANT(ota -ona(v))|(INLABEL(v)&(−INLABEL(v)))).
Ko'rib turganimizdek, bitta ASCENDANT(v) so'zidan foydalanish mumkin
INLABEL(v) dan v ning barcha ajdodlari ning INLABEL raqamlari.
Daraxt qirrasining tegini e = (u, v) O(log log n) bit satri sifatida belgilaymiz
u < LEVEL(v), BSR(INLABEL(v)&(−INLABEL(v)))) >,
ya’ni v darajasi va INLABEL(v) ning eng o‘ngdagi “1” indeksi,
bu yerda v - ildizdan uzoqroq joylashgan tugun. MST tekshiruvi uchun
algoritm, biz quyidagi teg xususiyatiga bog'liq: har qanday teg berilgan
daraxt qirrasi e va INLABEL(w), bu erda w e dan yo'ldagi ba'zi tugun
ba'zi bir bargga e (yoki e ning og'irligi) doimiy vaqtda joylashgan bo'lishi
mumkin.
Teg xususiyatini qondirish uchun biz HEAD jadvalini biroz boshqacha
tuzamiz original Schieber -Vishkin algoritmiga qaraganda. Avval biz Har bir ichki
tugun uchun bolani o'z ichiga olgan vaqtinchalik jadval (agar u mavjud)
INLABEL(p) = INLABEL(v) bo'lgan p da n v. Bu tomonidan amalga oshiriladi
daraxtni kesib o'tish va tugun p ning jadval yozuvini yangilash faqat qachon p dan
bir xil INLABEL raqamiga ega bo'lgan v tuguniga tushamiz.
Endi biz ALL va HEAD jadvallarini quyidagi tarzda yaratamiz.x ni kesib
o'tamiz daraxtni vaqtinchalik jadval tomonidan belgilangan tartibda, ya'ni biz doimo
pastga tushamiz, birinchi navbatda bir xil INLABEL raqamiga ega bo'lgan bolaga
(va keyin boshqa bolalar o'zboshimchalik bilan). i ← 0 dan boshlab, har doim biz](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_14.png)
![18
bo'lgan butun son) va bu vektorlarda bit operatsiyalaridan foydalanib, LCA (u, v) ni
topamiz. ).
Keyin, bu daraxtni to'liq ikkilik daraxt sifatida taqdim etsak, uning ba'zi
uchlarida oddiy yo'l bor, biz O (1) ichida LCA (v, u) ni qidirishni o'rganishimiz
mumkin.
Oldindan ishlov berish.
T - n ta burchakli kirish daraxti. Buning uchun siz LCA so'rovlariga javob
berishingiz kerak.
B - kamida n ta burchakli to'liq ikkilik daraxt. Keyinchalik tanishtirish va
tushuntirish uchun.
S (v) - v uchining pastki daraxti. Bundan keyin cho'qqi ham uning ajdodi, ham
avlodi deb faraz qilamiz.
u ustidagi v u ∈S (v) bilan bir xil. Ildiz har qanday tepadan yuqorida
joylashgan.
Biz cho'qqilarni prefiks daraxti o'tish tartibida sanab o'tamiz. v cho'qqisining
pastki daraxtidagi cho'qqilar sonini size v bilan belgilaymiz.
U ∈S (v) bo'lsin. Keyin preOrder u ∈ [preOrder v ; preOrder v + sizee v − 1]
PreOrder ta'rifiga ko'ra: v pastki daraxtdan preOrder u cho'qqilari o'lchami ev
- 1 uzunlikdagi natural sonlar segmentini tashkil qiladi. Chunki bu segment bilan
boshlanadi preOrder v + 1, keyin preOrder u [preOrder v; preOrder v + size v - 1]
segmentida joylashgan.
Keling, daraxtni yo'llar bilan yopaylik. Ya'ni, biz har bir v cho'qqini inlabelv
raqami bilan shunday bog'laymizki, T dagi har bir inlabel v ning oldingi tasviri
bog'lanadi va u qandaydir cho'qqidan barggacha bo'lgan oddiy yo'ldir.
Inlabel v sifatida siz preOrder u ni tanlashingiz mumkin, bu ikki maksimal
quvvatning ko'paytmasi, bu erda u ∈S (v).
Inlabel v = preOrde ru = k2^ b, b - maksimal bo'lsin. U' ∈S (v) cho'qqisi bo'lsin,
shundayki preOrderu ′ = k′2b. v cho'qqisiga mos keladigan segment 2b ga karrali
ikkita sonni o'z ichiga olganligi sababli, 2b + 1 ga karrali son ham mavjud. Ammo
keyin inlabel v to'g'ri tanlanmagan. Demak, v pastki daraxti faqat bitta u tepasini o'z
ichiga oladi, shuning uchun 2max | preOrder u.
Ke ling, ikkita holatni ko'rib chiqaylik:
Birinchi holat: inlabel v = preOrder u. U ikkitaning bir xil kuchini beradigan
boshqa hech qanday cho'qqi yo'q. Shunday qilib, inlabel qiymatlari barcha v pastki
daraxtlardagi inlabelvdan farq qiladi.](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_18.png)
![21
uchun siz yo'lda eng kam ahamiyatli bitni topishingiz kerak. 12 (x ⊕ (x − 1)) + 1
formulasi bunga ega va qiladi.
Ushbu harakatlardan so'ng biz javob joylashgan yo'lni oldik. Inlabel LCA (x,
y) yo'lidagi x va y kirish nuqtalariga qarash qoladi. Buni hisoblangan funktsiya boshi
yordamida amalga oshirish mumkin: headv ′ ni to ping, bu erda v ′ yo'lda oxirgidan
oldingi yo'lning cho'qqisidir. Keyin, dastlabki daraxt bo'ylab undan yuqoriga
ko'tarilib, biz kerakli kirish nuqtasini olamiz.
Ikkita kirish nuqtasiga ega bo'lgan holda, siz birinchi holatda bo'lgani kabi,
ularni balandli kda taqqoslashingiz va yuqoriroqni tanlashingiz mumkin.
Murakkablikni baholash.
Bino.
“Shiber -Vishkin algoritmi “daraxtdagi ikkita cho'qqining eng kichik umumiy
ajdodini topish uchun ishlatiladi.
U <tex> O (n) </tex> tayyorlash vaqtidan foydalanadi va keyi n <tex> O (1)
</tex> da har bir soʻrovga javob beradi.
# Agar <tex> LCA </tex> ni qidirish daraxti qator boʻlsa, siz <tex> LCA (u,
v) </tex> ni topishingiz mumkin edi.
yuqoridagi daraxtda joylashgan cho'qqisini olish.
# Agar {{ --- }} daraxt balandligi <tex> h </tex> boʻlgan toʻliq ikkilik daraxt
boʻlsa, unda siz har bir choʻqqini bit vektor bilan bogʻlashingiz mumkin.
uzunlik <tex> h </tex> (<tex> 0 </tex> dan <tex> 2 ^ h -1 </tex> gacha
boʻlgan butun son) va bit boʻyicha operatsiyalardan foydalanish bu vekto rlar ustida
<tex> LCA (u, v) </tex> ni toping. Keyin, bu daraxtni har bir tepasida zanjir bo'lgan
to'liq ikkilik daraxt sifatida ifodalashimiz mumkin. <tex> O (1) </tex> uchun <tex>
LCA (v, u) </tex> ni qanday qidirishni bilib oling. Biz cho'qqilarni prefi ks
daraxtining o'tish tartibida sanab o'tamiz: birinchi navbatda, joriy cho'qqi, so'ngra
{{ --- }} pastki daraxtlar kesib o'tiladi. <tex> \ operatorname {order}: V \ to \ mathbb
{N} </tex> {{ --- }} shunday o'tish tartibi bo'lsin. <tex> \ operatorname {size} v
</tex> orqali <tex> v </tex> cho'qqi pastki daraxtidagi cho'qqilar sonini
belgilaymiz. Bu erda va quyida biz taxmin qilamiz cho‘qqi ham uning ajdodi, ham
avlodi ekanligini.
{{Bayonot | bayonoti = <tex> u </tex> {{ --- }} <tex> v </tex> ostki
daraxtining tep asi boʻlsin. Keyin <tex> \ operatorname {order} u \ in [ \
operatorname {order} v; \ operatorname {tartib} v + \ operator nomi {siz} v - 1]
</tex> | dalil = Ta'rifga ko'ra, <tex> \ operatorname {order} </tex>, <tex> \
operatorname {order} u </tex> cho'qqila ri <tex> v </tex> pastki daraxt shaklidan.](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_21.png)
![22
<tex> uzunlikdagi natural sonlar segmenti \ operatorname {size} v - 1 </tex>.
Chunki bu segment bilan boshlanadi <tex> \ operatorname {order} v + 1 </tex>,
keyin <tex> \ operatorname {order} u </tex> {{ --- }} segme nt <tex> [ \ operatorname
{order} v; \ operatorname {tartib} v + \ operator nomi {siz} v - 1] </tex>. }}
Keling, daraxtni yo'llar bilan yopaylik. Ya'ni, har bir <tex> v </tex>
cho'qqisini <tex> \ operatorname {chain} v </tex> raqami bilan bog'laymiz.
<tex> \ operatorname {chain} </tex> quyidagi xususiyatlarga ega boʻlishi
kerak <tex> T </tex> dagi har bir <tex> \ operatorname {chain} v </tex> prototipi
ulanadi va shakllanadi.
Eng kichik umumiy ajdod. O (1) da O (N) oldindan ishlov berish bilan
toppish
G da raxti berilgan bo'lsin.Kirish (V1, V2) ko'rinishdagi so'rovlarni oladi, har
bir so'rov uchun ularning eng kichik umumiy ajdodini topish talab qilinadi, ya'ni.
ildizdan V1 gacha bo'lgan yo'lda, ildizdan V2 gacha bo'lgan yo'lda yotuvchi V
cho'qqisi va shu ka bi barcha cho'qqilardan eng pastini tanlash kerak. Boshqacha qilib
aytadigan bo'lsak, zarur bo'lgan V cho'qqisi ham V1, ham V2 ning ajdodi bo'lib,
barcha ana shunday umumiy ajdodlar orasidan pastki qismi tanlanadi. Shubhasiz,
V1 va V2 cho'qqilarining eng k ichik umumiy ajdodi ularning umumiy ajdodi bo'lib,
u V1 dan V2 gacha bo'lgan eng qisqa yo'lda joylashgan. Xususan, masalan, V1 V2
ning ajdodi bo'lsa, V1 ularning eng kichik umumiy ajdodidir.
Ingliz tilida bu vazifa LCA vazifasi - Least Common Ancestor deb ataladi.
Bu erda tasvirlangan Farach -Colton va Bender algoritmi asimptotik jihatdan
optimal va shu bilan birga nisbatan sodda (boshqa algoritmlar bilan solishtirganda,
masalan, Shiber -Vishkin).
Algoritm
LCA muammosini RMQ muammosiga (intervaldagi minimal) klassik
qisqartirishdan foydalanamiz (batafsilroq ma'lumot uchun Eng kichik umumiy
ajdodga qarang. O (sqrt (N)) va O (log N) da oldindan ishlov berish bilan O (N))
topish) . Keling, har bir so'rov uchun O (N) va O (1) ni oldindan qayta ishlash bilan
ushbu alohida holatda RMQ muammosini qanday hal qilishni bilib olaylik.
E'tibor bering, biz LCA muammosini qisqartirgan RMQ muammosi juda
o'ziga xosdir: massivdagi har qanday ikkita qo'shni element bittadan farq qiladi
(chunki massiv elementlari o'tish tartibi da tashrif buyurilgan cho'qqilarning
balandligidan boshqa narsa emas, va biz avlodga boramiz, keyin keyingi element 1](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_22.png)
![23
ta ko'proq bo'ladi yoki biz ajdodga boramiz, keyin keyingi element 1 ta kam bo'ladi).
Aslida, Farah -Kolton va Bender algoritmi aynan shund ay RMQ muammosining
yechimidir.
RMQ so'rovlari bajariladigan massivni A bilan, N - bu massivning o'lchamini
belgilaymiz.
Keling, avvalo, har bir so'rov uchun O (N log N) va O (1) ga oldindan ishlov
berish orqali ushbu muammoni hal qiladigan algoritmni tuza miz. Buni qilish oson:
T [l, i] ning har bir elementi [l oraliqdagi A minimaliga teng bo'lgan T [l, i] siyrak
jadvalini yarating; l + 2i). Shubhasiz, 0 <= i <= ⌈log N ⌉ va shuning uchun Sparse
jadvalining o'lchami O (N log N) bo'ladi. T [l, i] = min (T [l, i-1], T [l + 2i -1, i -1])
ekanligini sezsangiz, uni O (N log N) da qurish ham oson. Endi O (1) dagi har bir
RMQ so'roviga qanday javob berish kerak? So'rov (l, r) qabul qilinsin, keyin javob
min bo'ladi (T [l, sz], T [r -2sz + 1, sz]), bu erda sz - rl + 1 da n oshmaydigan ikkita
eng katta quvvat. . Darhaqiqat, biz segmentni (l, r) olamiz va uni uzunligi 2sz bo'lgan
ikkita segment bilan qoplaymiz - biri l dan boshlanadi, ikkinchisi esa r bilan tugaydi
(bundan tashqari, bu segmentlar bir -birining ustiga chiqadi, bu holda bizni umuman
bezovta qilmaydi. ). Har bir so'rovda O (1) asimptotikaga erishish uchun biz 1 dan
N gacha bo'lgan barcha mumkin bo'lgan uzunliklar uchun sz qiymatlarini oldindan
hisoblashimiz kerak.
Keling, ushbu algoritmni O (N) asimptotikasiga qa nday yaxshilashni tasvirlab
beraylik.
Keling, A massivni K = 0,5 log2 N o'lchamdagi bloklarga ajratamiz. Har bir
blok uchun undagi minimal elementni va uning holatini hisoblang (chunki LCA
muammosini hal qilish uchun bizni minimallarning o'zi emas, balki u larning
pozitsiyalari qiziqtiradi). B har bir blokdagi ushbu minimumlardan tashkil topgan N
/ K massivi bo'lsin. Yuqorida tavsiflanganidek B massividan Sparse Tableni
tuzamiz, bunda Sparse Table hajmi va uni qurish vaqti teng bo'ladi: N/K log N/K =
(2N / log N) log (2N / log N) =
= (2N / log N) (1 + log (N / log N)) <= 2N / log N + 2N = O (N)
Endi biz har bir blokdagi RMQ so'rovlariga tezda qanday javob berishni
o'rganishimiz kerak. Haqiqatan ham, agar RMQ (l, r) so'rovi qabul qilinsa, u holda l
va r turli bloklarda bo'lsa, javob quyidagi qiymatlarning minimali bo'ladi: l blokidagi
minimal, l dan boshlab va oxirigacha. blokning, keyin l dan keyin bloklardagi
minimal va r gacha (shu jumladan emas) va nihoyat r blokidagi minimal, blok
boshidan r gacha. Biz Sp arse Table yordamida O (1) uchun "minimal bloklarda"
so'roviga allaqachon javob berishimiz mumkin, bloklar ichida faqat RMQ so'rovlari
mavjud.](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_23.png)
![24
Bu erda biz "+ -1 xususiyat" dan foydalanamiz. E'tibor bering, agar birinchi
element har bir blok ichidagi uning har bir elementidan ayirilsa, unda barcha bloklar
+ -1 raqamlaridan iborat K -1 uzunlikdagi ketma -ketlik bilan noyob tarzda
aniqlanadi. Shunday qilib, turli bloklar soni quyidagicha bo'ladi:
2K -1 = 20.5 log N - 1 = 0.5 sqrt(N)
Shunday qilib, turli bloklar s oni O (sqrt (N)) bo'ladi va shuning uchun biz O
(sqrt (N) K2) = O (sqrt (N) log2 N) = barcha turli bloklar ichida RMQ natijalarini
oldindan sanashimiz mumkin. O (N). Amalga oshirish nuqtai nazaridan, biz har bir
blokni K -1 uzunlikdagi bit niqobi bilan tavs iflashimiz mumkin (bu, shubhasiz,
standart int turiga mos keladi) va oldindan hisoblangan RMQ -larni qandaydir R
massivida saqlashimiz mumkin [maska, l, r] hajmi O (sqrt (N) log2 N).
Shunday qilib, biz har bir blok ichidagi RMQ natijalarini, shuningdek,
blo klarning o'zlari bo'yicha RMQni, yig'indidagi hamma narsani O (N) da, har bir
RMQ so'roviga O (1) da javob berishni o'rgandik - faqat oldindan -dan foydalanib.
hisoblangan qiymatlar, eng yomon holatda to'rtta: l blokida, r blokida va l va r
o'rtasidagi blok lar inklyuziv emas.
Xulosa:
Men kurs ishimni Shiber -Vishkin algoritmi haqida yozdim. Shiber -Vishkin
algoritmi mavzusida tayyorlagan kurs ishi davomida LCA algoritmi haqida tariflar
keltirdim. Bu algoritmlar Shiber -vishkin algoritmi, Kompl’os algoritmlariga misol
qilishimiz mumkin. Shiber -Vishkin algoritmini Berkman Shiber va Uzi Vishkin
tomonidan ishlab chiqilgan. 1988 yilda Baruch Shiber bilan birgalikda u
o'zboshimchalik bilan (lekin qat'iy) yo'naltirilgan o'rmonda eng yaqin umumiy
ajdodlarn i bit va algoritmik usullarning jozibali va ko'rsatma aralashmasidan
foydalangan holda hisoblash usulini ishlab chiqdi. Shiber va Vishkin yog'ochni
oldindan qayta ishladilar, uning tepalarini S piramidasiga aylantirdilar. Hajmi n har
bir u tepasi uchun uc hta miqdorni hisoblash yo'li bilan Baruch Shiber va Uzi
Vishkinning eng quyi umumiy ajdod uchun algoritmidan foydalanish va dasturlash
uchun juda qulay hisoblanadi.
Bu kurs ishida bajarishda C++ dasturlash tilida kodlar yozildi hamda Shiber -
vishkin algorit miga oid ma’lumotlar keltirib o’tildi. Shiber -Vishkin algoritmida
dasturlashda foydalanish uchun LCA algoritmi uchiun yetarlicha ma’lumot
keltirdim.](/data/documents/f1d065cc-a73c-4dfd-b0b8-9dabffdcc35e/page_24.png)
SHAROF RASHIDOV NOMIDAGI SAMARQAND DAVLAT UNIVERSITETI RAQAMLI TEXNOLOGIYALAR FAKULTETI - vishkin algoritmi Bajaruvchi: L.Xamidov Ilmiy rahbar : ______________ Kafedra mudiri : _____________ ishi Tarix kafedrasining 2022 - yil ___ ________ majlisida himoya qilindi va ______ foizga baholandi . Komissiya raisi :________________ _________________________ A :______________________ _________________________ Samarqand – 2022
2 Sharof Rashidov nomidagi Samarqand davlat universiteti Raqamli texnologiyalar fakulteti Amaliy matematika 202 -guruh talabasi Xamidov Jahongir ning « Shiber -Vishkin algoritmi » mavzusidagi kurs ishiga T A Q R I Z ___________________________________________________________________ ___________________________________________________________________ ___________________________________________________________________ _______________________________________________________ ____________ ___________________________________________________________________ ___________________________________________________________________ ___________________________________________________________________ ___________________________________________ ________________________ ___________________________________________________________________ ___________________________________________________________________ ___________________________________________________________________ _______________________________ ____________________________________ ___________________________________________________________________ ___________________________________________________________________ ___________________________________________________________________ ___________________ ________________________________________________ ___________________________________________________________________ ___________________________________________________________________ ___________________________________________________________________ _______ ____________________________________________________________ ___________________________________________________________________ ___________________________________________________________________ ______________________________________________________________ _____ ___________________________________________________________________ ___________________________________________________________ ________ ___________________________________________________________________ __________________________________________________ _________ ________ ___________________________________________________________ ________ Ilmiy rahbar: __________________ o’qit. _____________
3 MUNDARIJA KIRISH ……………………………………………….…………………………. 4 I-BOB. ALGORITMNING G’OYASI HAQIDA KELTIRILGAN MA’LUMOTLAR 1.1. Algoritm g’oyasi ……………………………………………………………. 5 II -BOB. KOMPL’OS ALGORITMIDAN SHIBER VISHKIN ALGORITMIGA O’TISH. SHIBER -VISHKIN ALGORITMI 2.1 Kompl’os algoritmidan Shiber -vishkin algoritmiga o’tish……… …………… 9 2.2. Shiber -vishkin algoritmi……….……… ………………. …………………… 17 XULOSA…. .………………………………………………………………….…. 24 FOYDALANILGAN ADABIYOTLAR RO’YXATI …….…………………… 25 ILOVALAR ………………………………………………………………………26
4 KIRISH Muammoning dolzarbligi. Cho'qqilari va qirralari bilan yo'naltirilgan yoki yo'naltirilmagan vaznli grafik berilgan. Hammaning vazni qirralari manfiy emas. Ba'zi boshlang'ich uchlari ko'rsatilgan. Cho'qqidan eng qisqa yo'llarning uzunliklarini topish talab qilinadi boshqa barcha cho'qqilarga, s huningdek, eng qisqa yo'llarni o'zlari chiqarish yo'lini ta'minlaydi. Bu muammo bitta manbali eng qisqa yo'llar muammosi deb ataladi. Daraxtlardagi eng asosiy algoritmik muammolardan biri eng kichik umumiy ajdodni qanday topishdir. Har bir tugun o'z ota -on asiga ishora qiluvchi daraxt ma'lumotlar strukturasida v va w dan ildizgacha bo'lgan yo'llarning birinchi kesishishini topish orqali eng kichik umumiy ajdodni osongina aniqlash mumkin. Umuman olganda, ushbu algoritm uchun zarur bo'lgan hisoblash vaqti O (h ), bu erda h - daraxtning balandligi (bargdan ildizgacha bo'lgan eng uzun yo'lning uzunligi) hisoblanadi. Daraxt - N ta uchi va N -1 qirralari bo'lgan yo'naltirilmagan bog'langan grafik. Har qanday cho'qqidan boshqasiga bitta oddiy yo'l bor.Daraxtning ildi zi cho'qqi deb ataladi, undan o'tayotganda daraxt bo'ylab harakat yo'nalishi ko'rsatilgan. Ikki u va v cho'qqilarning eng kichik umumiy ajdodi ildizdan v cho'qqigacha va u cho'qqigacha bo'lgan yo'lda, shuningdek, undan eng uzoqda joylashgan p uchi deb atal adi. Ma'lumotlarni kiritish: Kirish daraxt haqida ma'lumot oladi: N - uchlari soni, chekka bilan bog'langan N -1 juft uchlari va M - so'rovlar soni. Keyin dastur so'rovlarni qabul qiladi: ikkita u va v uchlari, buning uchun ularning eng kichik umumiy ajdodi ni topish talab qilinadi.
5 I-BOB. ALGORITMNING G’OYASI HAQIDA KELTIRILGAN MA’LUMOTLAR 1.1. Algoritm g’oyasi Biz har bir cho'qqi uchun ildizgacha bo'lgan masofani va biz unga kelgan oldingi cho'qqiga (ajdod) saqlaymiz. Keyin u va v cho'qqilaridan daraxtning ildizigacha ko'tarilamiz. Har bir qadamda biz ildizdan eng uzoq bo'lgan u yoki v cho'qqisini tanlaymiz va keyin uning o'rniga uning ajdodini ko'rib chiqamiz, toki boshlang'ich u va v dan hosil bo'lgan yo'llar bitta cho'qqi - ularning eng kichik umumiy ajdodiga olib boradi. Daraxtning turli xil variantlari bilan bunday yo'l N bosqichdan iborat bo'lishi mumkin, bu juda ko'p sonli tugunlar va so'rovlar bilan juda sekin ishlaydi. Ushbu dastur har bir so'rovni bajarish uchun O (N) vaqtini talab qiladi . Endi algoritmni yaxshilaymiz. Har bir cho'qqi uchun biz uzoq daraxtning ildizigacha bo'lgan masofani, uning bolalari sonini, shuningdek, biz unga oxirgi marta kelgan ajdodimizni (tanlash quyida aniqlanadi) va raqamni saqlaymiz. cheti ajdoddan chiqadigan cho'qqidan, bu cho'qqiga burilish yo'lida ... Kerakli o'zgaruvchilarni e'lon qilaylik, qulaylik uchun bu global xotirada amalga oshiriladi. const int SIZE = 100050; vector<int> v[SIZE]; // har bir cho'qqi uchun qirralarning ro'yxati bool vis[SIZE]; // o’t ish paytida cho’qqilarni ziyorat qilish haqida eslatmalar int kids[SIZE]; // Har bir tepalikdagi avlotlar soni int dist[SIZE]; // Tepadan ildizgacha bo’lgan masofa int last[SIZE]; // Oldingi cho’qqi raqami int turn[SIZE]; Endi har bir cho'qqi uchun rekurs iv funktsiyadan foydalanib (k_go (0) ga qo'ng'iroq qiling), biz uning avlodlari sonini hisoblaymiz: int k_go(int s) { int res = 0;