logo
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. Shiber-vishkin algoritmi

Shiber-vishkin algoritmi

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

1039.146484375 KB
Ko'chirib olish
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;

O'xshashlar

KRASKAL ALGORITMI
Deykstra Algoritmi
Xon saralash algoritmi
Timsort saralash algoritmi
Oriyentatsiya funksiyasi. Grexem algoritmi. Ajrat va hukmron bo`l algoritmi