logo

Shiber-vishkin algoritmi

Загружено в:

12.08.2023

Скачано:

0

Размер:

1039.146484375 KB
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;	  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])	  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) {	  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.	 	
 	
 
 
 
 
 
 
 
  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.	   
 
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.     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
   A (w) = {daraxt yo'li (w, a), daraxt yo'li (w, c)}, A (t) = {daraxt yo'li (t, b)}.
 Yoki,  masalan,  boshq
a  daraxt  bo'lmagan  chekka  (q,r)  mavjud,  bu  erda  q  ∈/ 
pastki daraxt(a) va r  ∈ subtree(p)  \ subtree(v) keyin u holda A(v|p) 6= A(p).  Koml'os  algoritmini  o'zgartirish  uchun  asosiy  to'siq  chiziqli  vaqtda 
ishlaydigan  algoritm  A(child(p)|p)  ni  hosil  qiladi  A(p)  chiziqli  ustki  w.r.t.  vazn 
taqqoslashlari.  Boshqalarida  so'zlar,  O(|E|)  vaqtida  qanday  taqqoslash  kerakligini 
qanday hal qilish kerak.  Tarixiy eslatma
  Koml'os 
algoritmini tahlil qilish   
Agar A(root) = 
∅ dan boshlasak va daraxtdan pastga tushsak,  har birida ikkilik qidiruv uchun zarur bo'lgan vazn taqqoslashlari soni
 u tugun dlog2 bilan chegaralangan (1 + |A(u)|)e. n = |V| bo'lsin  va  m bo'lishi 
kerak  bo'lgan  daraxt  yo'llari  soni  bo'lsin  sikl  xususiyatiga  mos  ravishda  so'raladi, 
ya'ni m = |E| − n + 1.   i darajadagi tugunlar to‘plami va   
. Endi,
   
 
(
∗ ) botiq funksiya log(·) uchun Jensen tengsizligi boʻyicha    
Shuning uchun og'irlikni taqqoslash soni c
hegaralangan     (
∗∗ ) T toʻliq shoxlanadigan daraxt boʻlgani uchun shuni bildiradi    
Endi 
 beri,    oldik. Shuning uchun, har bir daraxt yo'li uchun 2 ta qo'shimcha taqqoslashni 
amalga oshirish orqali sikl  xususiyatini tekshirish  uchun zarur bo'lgan so'rov,  u o'z 
ichiga oladi Og'irlikni taqqoslashning umumiy soni O(n + m) + 2m = O(n + m).  Koml'os algoritmini o'zgartirish
 Oldinda nima kutmoqda. . .
 Qolgan vazifalarimiz
  LCA ga javob berish uchun Schieber
-Vishkin algoritmini taqdim etish  oldindan  ishlangan 
jadvallar  yordamida  doimiy  vaqtda  so'rovlar  chiziqli 
vaqtda tayyorlanadi. Biz aniq bir narsaga e'tibor qaratamiz original algoritmga mos 
keladigan o'zgartirishlar bizning ehtiyojlarimiz uchun.  Koml'os  algoritmini  ishlash  uchun  moslashtirish  daraxt  to'liq  s
hoxlangan 
daraxt emas. Ushbu algoritmlarni ma'lumotlar tuzilmasi bilan birlashtirish  bizga chiziqli qo'shimcha xarajatlarga erishishga imkon beradi, ya'ni vaqt
 Koml'os  algoritmini  bajarib,  har  bir  tugunda  biz  buni  qilamiz  O(log(1  + 
|A(u)|)) mashina ko‘rsat malarini bajaring.  Schieber
-Vishkin algoritmining dastlabki ishlov berish bosqichi:  Biz O(n) vaqt va fazoda bir nechta qidirish jadvallarini oldindan hisoblashdan 
boshlaymiz.   Biz  oldindan  buyurtma  orqali  PREORDER(v),  SIZE(v)  va  LEVEL(v)  ni 
yaratamiz   T. 
ning kesib o'tishi. SIZE(v)  - pastki daraxtdagi (v) tugunlar soni, the        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  15	 	
 
istalgan  v  tuguniga	 tushamiz,  biz  ALL(i)  ni  v  bilan  yangilaymiz  va  har  doim  biz 	
INLABEL  i  INLABEL  dan  farq  qiladigan  v  tuguniga  tushing  uning  ota	-onasi  (v 	
INLABEL(v)  yo'lining  boshi  ekanligini  bildiradi),  biz  HEAD(INLABEL(v))  ni  i 
bilan yangilang va har bir tugunga tashrif b	uyurganimizdan keyin biz increment i ← 	
i  +  1.  Shunday  qilib,  ALL  jadvali  aniq  n  ta  elementni  o'z  ichiga  oladi  daraxt 
tugunlariga  mos  keladigan,  lekin  bo'yicha  guruhlangan  INLABEL  yo'llari  har  bir 
yo'lning  tugunlari  ketma	-ket  paydo  bo'lishi  uchun  ALLda  tart	ib  (yo'llar  orasidagi 	
tartib  o'zboshimchalik  bilan)  Va  stol  HEAD  har  bir  INLABEL  yo'lining  boshining 
joylashishini ALL ichida saqlaydi. Endi teg xususiyatiga ega ekanligini ko'rishimiz 
mumkin:  <  d,  k  >  of  tegi  berilgan  chekkasi  e  =  (u,  v)  va  INLABEL(w),  bi	z  Lv  = 	
INLABEL(v)  ni  olamiz  Lv  ←  ((INLABEL(w)  >>  k)  |  1)  <<  k  va  keyin  j  ← 
HEAD(Lv ) va keyin v ← ALL(k − LEVEL(ALL(j)) + j), shuning uchun e ni yagona 
deb topamiz chekka v dan uning ota	-onasiga.	 	
z = LCA(x, y), dz = LEVEL(z) , LCA˜ (x, y) ni topish uchun S	chiber	-Vishkin 	
algoritmi	 	
1.	 	agar  INLABEL(x)  =  INLABEL(y)  boʻlsa,  dz  ←  min(LEVEL(x), 	
LEVEL(y)) ni qaytaring.	  	
2. 	i 0 ← ASCENDANT(x) & ASCENDANT(y) & (−(1 << i))	 	
3. 	i ← BSR(i 0 & (−i 0 ))	 	
4. 	Lz ← ((INLABEL(x) >> i) | 1) << i	 	
5. 	agar  INLABEL(x)  =  Lz  bo'lsa, 	dx  ←  LEVEL(x)  bo'lsa,  7  va  8	-	
bosqichlarni bajaring	 	
6. 	k = BSR(ASCENDANT(x) & ((1 << i) − 1))	 	
7. 	x 0 ← ALL(HEAD(((INLABEL(x) >> k) | 1) << k)), dx ← LEVEL(x 	
0 ) 	– 1 
8. 	agar  INLABEL(y)  =  Lz  bo'lsa,  dy  ←  LEVEL(y)  bo'lsa,  10  va  11	-	
bosqichlarni bajaring	 	
9. 	k = 	BSR(ASCENDANT(y) & ((1 << i) − 1))	 	
10	. 	y 0 ← ALL(HEAD(((INLABEL(y) >> k) | 1) << k)), dy ← LEVEL(y 	
0 ) 	– 1 
11	. 	 qaytish dz ← min(dx , dy )	 	
 
Bizning  ehtiyojlarimiz  uchun  LCA˜  (x,  y)  ni  hisoblash  kifoya  qiladi,  lekin 	
xuddi shunday z ning o'zini hisoblash oso	n (z ota (x0) yoki ota	-ona (y0) yoki x yoki 	
y).	  2
-bosqichda  b  =  LCA(INLABEL(x),  INLABEL(y))  ning  eng  o‘ngdagi  “1” 
indeksi topiladi.   3
-qadam yon daraxtdagi INLABEL(z) darajasining bitini eng past bit sifatida 
belgilaydi   qayd  etilgan  darajalar  uchun  umumiy  bo'lgan  b  dan  yuqoridagi  eng  yaqin 
darajani topish orqali yoqiladi  ASCENDANT(x) va ASC
ENDANT(y) da. 4-qadam ushbu bitning indeksini 
oladi.   To'g'rilik nasl
-nasabni saqlash xususiyatidan kelib chiqadi, ya'ni har qanday v 
tugun uchun.   T  inlabel  xaritalash  v  ning  avlodlarini  INLABEL(v)  ning  avlodlariga 
yuboradi.yonbosh daraxt (shuning uchun v n ing ajdodlari orasida eng ko'p log n xil 
INLABEL mavjud). Bu xususiyat kuzatuvdan kelib chiqadiki,   -  
bu  ajdod  s2  ning  (s1  =  s2  holatini  o'z  ichiga  oladi)  yon  daraxtda,  agar  s2  bir  xil  r 
bo'lsa  eng  chapdagi  bitlar  va  eng  o'ngdagi  “0”  bitdan  ortiq  emas.  Sh uning  uchun, 
agar  w  ∈ subtree(v)  in  daraxt  T,  chunki  INLABEL(v)  ning  eng  chap  r  bitlari 
INLABEL  tomonidan  taqsimlanadi  subtree(v)  dagi  barcha  tugunlarning  raqamlari 
va bu tugunlarning  hech birida INLABEL  mavjud emas t dan ortiq o'ngdagi  '0' bit, 
nasl -nasabni saqlash xususiyati ga ega.  5
-bosqich indeksdan (4 -bosqichda olingan) Lz = INLABEL(z) ni tuzadi va x 
ning INLABEL ning qolgan eng chap bitlari (yoki y).  6,7,8
-bosqichlar INLABEL(z) tomonidan belgilangan yo‘lda x ning eng quyi 
ajdodi bo‘lgan ˆx ni hisoblaydi.  7
-qadam  x  ning  en g  o'ngdagi  "1"  ni  oladi  0,  x  ning  ajdodi  bo'lgan  ˆx  ning 
bolasi, topish orqali INLABEL(z) darajasidan past boʻlgan ASCENDANT(x) da eng 
chap “1” qayd etilgan.  8
-qadam qolgan chap bitlarni biriktirish orqali  ushbu bolaning INLABEL -ni 
yaratadi    va  keyin  bolan ing  o'zini  HEAD  jadvali  orqali  oladi,  bu  shundan  beri 
munosibdir  bola    uning  INLABEL  yo'lidagi  birinchi  tugundir  (chunki  uning  ota -
onasi ˆx boshqa INLABELga ega).  9,10,11
-qadamlar  xuddi  shunday  INLABEL(z)  yo'lidagi  y  ning  eng  quyi 
ajdodi bo'lgan ˆy ni hiso blaydi.   Shiber
-Vishkin algoritmining illyustratsiyasi  Daraxt misoli: chapda PREORDER, tepada INLABEL, pastda ASCENDANT
   
2.2. Shiber
-vishkin algoritmi   U  O  (n)  oldindan  ishlov  berish  vaqtini  ishlatadi  va  keyin  O  (1)  dagi  har  bir 
so'rovga javob beradi.  1.Agar  LCA  ni  qidiradigan  daraxt  oson  yo'l  bo'lsa,  daraxtning  ildiziga 
yaqinroq cho'qqisini olish orqali LCA (u, v) ni topish mumkin bo'lar edi .  2. Agar daraxt balandligi h bo'lgan to'liq ikkilik daraxt bo'lsa, u holda biz har 
bir cho'qqini h uzunlikdagi bit vektori bilan bog'lashimiz mumkin (0 dan 2h  - 1 gacha   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.	  Biz tushundikki, v cho'qqida
gi inlabelv preimage yo uzilib qoladi yoki aynan 
bitta  bolaga  aylanadi.  Bu  shuni  anglatadiki,  inlabelv  preimage,  talab  qilinganidek, 
ba'zi bir cho'qqilardan T gacha bo'lgan oddiy yo'ldir.    
Keling,  A = (preOrder  v 
- 1)  ⊕ (preOrder v + size v  - 1) ni ko'rib  chiqaylik. 
Keling, A dagi eng muhim bitta bit l ning o'rnini ko'rib chiqaylik.  Keling,  2^(
l  +  1)  ning  ko'paytmalari  yo'qligini  isbotlaylik.  Shunday  raqam 
topilsin.  Keyin  l -bit  kamida  ikki  marta  o'zgardi,  ya'ni  l  +  1 -bit  o'zgargan.  Bu 
preOrder v − 1 va preOrder v + size v − 1 o‘rtasidagi eng muhim farq biti 1 -bitdan 
kattaroq ekanligini anglatadi .  E'tibor bering, 
⌊log2a ⌋ + 1 funktsiyasi eng muhim bitta bit sonini tanlaydi.   
 
funktsiyasi l dan past bo'lgan barcha bitlarni tozalaydi. Segmentdan 
2l ga karrali olish uchun uning mavjudligiga ishonch hosil qilgan holda segmentning 
o'ng chegarasida l bi tni nolga tenglashtirish kifoya.  Har bir inlabelv qiymati h = 
⌈log2n ⌉ balandlikdagi toʻliq B ikkilik daraxtining 
choʻqqisiga  mos  keladi.  Daraxtda  bir  cho'qqi  to'plamiga  ikkita  qirralar  to'plami 
quriladi: simli ramka va asosiy. Darajali har bir v ∈V (B) cho'qqisi uchun, oxirgisidan 
tashqari,  v  →  2v  va  v  →  2v  +  1  ramka  qirralari  bo'ladi.  Shunday  qilib,  B  dagi 
cho'qqilar  sim  ramka  qirralari  bo'ylab  infiks  tartibida  raqamlanadi:  birinchi 
navbatda,  chap  pastki  daraxt,  so'ngra  cho'qqi,  keyin  o'ng  pastki  daraxt  qayta  Keling,  har  bir  yorliq  uchun  B  dagi  uning  barcha  avlodlari  to'plamini  asosiy 
qirralar bo'ylab hisoblayli k. E'tibor bering, bitta bolani saqlash uchun daraxtda faqat 
uning balandligini saqlash kifoya. Uning qiymatini tiklash uchun siz faqat yuqoridan 
Delta  h  yuqoriga  ko'tarilishingiz  kerak  v.  Shuning  uchun  bu  to'plamning  barchasi 
butun  songa  sig'ishi  mumkin:  i  balandlikda  avlod  mavjud  bo'lsa,  i -bit  bitta  bo'ladi. 
Keling, bu raqamni ajdodlar to'plamiga mos keladigan ascendant v deb ataylik.  Kelajakda  ascendantv  LCA  (inlabelv,  inlabelu)  ni  topishga  yordam  beradi. 
Bundan  tashqari,  bizga  quyidagi  ma'lumotlar  kerak .  headv  u  eng  sayoz  cho'qqi 
bo'lib, inlabelv = inlabelu. levelv  - T da v cho'qqisining chuqurligi.  Quyidagi hisob
-kitoblar inlabelLCA (x, y) ni topadi:    
Bu  shuni  anglatadiki,  biz  LCA  ni  simli  ramka  qirralari  orqali  topdik.  Biroq, 
biz  izlayotgan  asosiy  qirralarning  LCA  yuqoriroq  bo'lishi  mumkin  (u  pastroq  yoki 
yon  tomonga  bo'lishi  mumkin  emas,  chunki  barcha  asosiy  qirralar  pastga 
yo'naltirilgan).   Bi
t bo'yicha va ko'tarilish va ko'tarilishni eng muhim bitlarda olib, biz asosiy 
qirralar bo'ylab ildizdan bu cho'qqilarga yo'l olamiz. Shu bilan birga, LCA dan past 
darajalar  uchun  javobgar  bo'lgan  bitlar  haqida  hech  narsa  ma'lum  emas.  Shuning 
uchun  siz  ula rni  nolga  qaytarishingiz  kerak.  2^i  ga  ko'paytirish  va  bo'lish  keraksiz 
bitlarni  nolga  tenglashtiradi.  Shundan  so'ng,  LCA  ni  asosiy  qirralar  bo'ylab  topish   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.	  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  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.	  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.	 	
 
  25	 	
 	
Foydalanilgan adabiyotlar:	 	
 
1.Shiloach,  Yossi;  Vishkin,  Uzi  (1982a),  "An  O(log  n)  parallel  ulanish 	
algori	tmi", Algoritmlar jurnali, 3: 57	–67.	 	
2. Shiloach, Yossi; Vishkin, Uzi (1982b), "An O(n2 log n) parallel maksimal 	
oqim algoritmi", Algoritmlar jurnali, 3 (2): 128	–146.	 	
3.  Mehlhorn,  Kurt;  Vishkin,  Uzi  (1984),  "Paralel  xotiralarning  cheklangan 	
granulyarligi  b	ilan  parallel  mashinalar  tomonidan  PRAMlarning  tasodifiy  va 	
deterministik simulyatsiyasi", Acta Informatica, 21 (4): 339	–374	 	
4. Algoritmlar: qurish va tahlil qilish. Kormen T., Leiserson C., Rivest R.	 	
5. Dasturchilar uchun kombinatorika. Lipskiy V.	 	
6. 	Grafik  nazariyasi  bo'yicha  ma'ruzalar.  Emelichev  V.,  Melnikov  O., 	
Sarvanov V., Tyshkevich R.	 	
7. https://habr.com/ru/post/198464/	 	
8. https://ru.wikipedia.org/wiki/	 	
9. http://e	-maxx.ru/algo/export_lca_linear	 	
10. 	https://neerc.ifmo.ru/wiki/index.php	?

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;