Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti urganch filiali telekommunikatsiya texnologiyalari fakulteti

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI URGANCH FILIALI


TELEKOMMUNIKATSIYA TEXNOLOGIYALARI FAKULTETI
972-18 guruh talabasi Erkinova Irodaning
Algoritmni loyihalash fanidan mustaqil ishi


Mavzu: Kesishmaydigan to`plamlar uchun ma’lumotlar tuzilmasi


Topshirdi Erkinova Iroda
Qabul qildi ___________________

2021 y

Mavzu: Kesishmaydigan to`plamlar uchun ma’lumotlar tuzilmasi
Reja:

1. 
   Kesishmaydigan to`plamlar (ingliz tilida " disjoint-set -union" yoki oddiygina "DSU") ma'lumotlar tuzilishi.
   
2. 
   Yo'lni siqish evristik
   
3. 
   Rivojlanish evristik
   
4. 
   Raqamli evristikani qo'llashda asimptotikani baholash
   
5. 
   Xulosa
   
6. 
   Foydalanilgan adabiyotlar
   

Ushbu ma'lumotlar tuzilishi quyidagi imkoniyatlarni beradi. Dastlab, bir nechta elementlar mavjud, ularning har biri alohida (o'ziga xos) to'plamda. Bitta operatsiyada siz istalgan ikkita to'plamni birlashtira olasiz va shuningdek, ko'rsatilgan elementni hozirda qaysi qatorda o'rnatishingizni so'rashingiz mumkin. Shuningdek, klassik versiyada yana bir operatsiya - alohida to'plamga joylashtirilgan yangi elementni yaratish kiradi.

Shunday qilib, ushbu ma'lumotlar strukturasining asosiy interfeysi faqat uchta operatsiyadan iborat:
• - yangi elementni qo'shadi, uni undan iborat yangi to'plamga joylashtiradi.
• - ko'rsatilgan ikkita to'plamni birlashtiradi (element joylashgan to'plam va element joylashgan to'plam).
• - belgilangan element joylashgan to'plamni qaytaradi. Aslida, bu to'plamning elementlaridan birini qaytaradi (vakil yoki etakchi deb nomlanadi (ingliz tilidagi adabiyotda "rahbar")). Ushbu vakil har bir to'plamda ma'lumotlar strukturasining o'zi tomonidan tanlanadi (va vaqt o'tishi bilan, ya'ni qo'ng'iroqlardan keyin o'zgarishi mumkin).
Masalan, agar ba'zi bir ikkita element uchun qo'ng'iroq bir xil qiymatni qaytargan bo'lsa, demak, bu ushbu elementlar bir xil to'plamda, aks holda har xil to'plamlarda.
Quyida tavsiflangan ma'lumotlar tuzilishi ushbu operatsiyalarning har birini deyarli o'rtacha bajarishga imkon beradi (asimptotiklar haqida batafsil ma'lumot uchun quyida algoritm tavsifidan keyin qarang).
Shuningdek, maqolaning kichik bo'limlaridan birida DSUning muqobil varianti tasvirlangan, bu esa bitta so'rov uchun o'rtacha ravishda assimptotikaga erishishga imkon beradi; va (ya'ni, bundan ham ko'proq) - hatto har bir so'rov uchun o'rtacha vaqt (qarang "DSUlarni to'plamlarning aniq ro'yxati sifatida saqlash").
Ma'lumotlarning samarali tuzilishini yaratish
Avval barcha ma'lumotlarni qanday shaklda saqlashimiz to'g'risida qaror qabul qilaylik.
Biz elementlar to'plamini daraxtlar shaklida saqlaymiz: bitta daraxt bitta to'plamga to'g'ri keladi. Daraxtning ildizi - to'plamning vakili (etakchisi).
Amalga oshirilganda, bu biz har bir element uchun daraxtda ota-bobolariga bog'lanishni saqlaydigan qator yaratamiz degan ma'noni anglatadi. Daraxtlarning ildizlari uchun ularning ajdodlari o'zlari deb o'ylaymiz (ya'ni, bog'lanish bu joyda halqalangan).
Sodda amalga oshirish
Biz allaqachon disjoint set tizimining birinchi dasturini yozishimiz mumkin. Bu juda samarasiz bo'ladi, ammo keyin biz uni ikkita hiyla bilan yaxshilaymiz, natijada deyarli doimiy ish vaqti bo'ladi.
Shunday qilib, elementlar to'plamlari haqidagi barcha ma'lumotlar bizda massiv yordamida saqlanadi.
Yangi element (operatsiya) yaratish uchun biz shunchaki uning bobosi o'zi ekanligini ta'kidlab, tepada ildiz otgan daraxt hosil qilamiz.
Ikki to'plamni (operatsiyani) birlashtirish uchun avval u joylashgan to'plam va u joylashgan to'plamning rahbarlarini topamiz. Agar etakchilar bir-biriga to'g'ri keladigan bo'lsa, unda biz hech narsa qilmaymiz - demak, to'plamlar allaqachon birlashtirilgan. Aks holda, siz shunchaki vertexning ajdodi teng ekanligini (yoki aksincha) ko'rsatishingiz mumkin - shu bilan bitta daraxtni boshqasiga qo'shish.
Va nihoyat, etakchini topish () operatsiyasini amalga oshirish juda oson: biz ildiz otguncha ajdodlarimizni tepadan ko'taramiz, ya'ni. ajdodlar ma'lumotnomasi o'z-o'zini anglamagan bo'lsa. Ushbu operatsiyani rekursiv ravishda amalga oshirish ancha qulaydir (ayniqsa, keyinchalik qo'shilgan optimallashtirish bilan bog'liq holda qulayroq bo'ladi).
void make_set (int v) {
parent[v] = v;
}
int find_set (int v) {
if (v == parent[v])
return v;
return find_set (parent[v]);
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b)
parent[b] = a;
}
Biroq, disjoint setlar tizimini bunday amalga oshirish juda samarasiz. Bir nechta to'plamlarning birlashmasidan so'ng, bu to'plam uzun zanjirga aylangan daraxt ekanligi aniqlanganda, misolni tuzish oson. Natijada, har bir qo'ng'iroq daraxt chuqurligi tartibi vaqtida, ya'ni bunday testda ishlaydi. per.
Bu biz oladigan asimptotikadan juda uzoq (doimiy ish vaqti). Shuning uchun biz ishni sezilarli darajada tezlashtirishga imkon beradigan (hatto alohida qo'llaniladigan) ikkita optimallashtirishni ko'rib chiqamiz.
Yo'lni siqish evristik
Ushbu evristik ishni tezlashtirish uchun mo'ljallangan.
Qo'ng'iroqdan so'ng, to'plamning kerakli rahbarini topganimizda, vertex va yo'l bo'ylab o'tgan barcha tepaliklar ushbu rahbarga ega ekanligini eslaymiz. Buning eng oson yo'li ularni ushbu tepalikka yo'naltirishdir.
Shunday qilib, ajdodlar qatorining ma'nosi biroz o'zgaradi: endi bu ajdodlarning siqilgan massivi, ya'ni. har bir tepalik uchun bevosita ajdod emas, balki ajdod ajdodi, ajdod ajdodi va boshqalar saqlanishi mumkin.
Boshqa tomondan, siz ushbu ko'rsatgichlarni har doim etakchiga ko'rsatib qo'yishingiz mumkin emasligi aniq: aks holda operatsiya davomida elementlarning etakchilarini yangilashingiz kerak bo'ladi.
Shunday qilib, qatorga ajdodlar qatori sifatida yaqinlashish kerak, ehtimol qisman siqilgan bo'lishi kerak.
Operatsiyani yangi amalga oshirish quyidagicha:
int find_set (int v) {
if (v == parent[v])
return v;
return parent[v] = find_set (parent[v]);
}
Bunday sodda dastur mo'ljallangan barcha narsani bajaradi: birinchi navbatda, rekursiv qo'ng'iroqlar bilan to'plamning etakchisi topiladi, so'ngra stekni echish jarayonida ushbu rahbar barcha o'tgan elementlar uchun havolalarga tayinlanadi.
Ushbu operatsiyani rekursiv bo'lmagan holda amalga oshirish mumkin, ammo keyin siz daraxt orqali ikkita o'tishni amalga oshirishingiz kerak: birinchisi kerakli rahbarni topadi, ikkinchisi uni yo'lning barcha tepalariga belgilaydi. Biroq, amalda rekursiv bo'lmagan dastur sezilarli foyda keltirmaydi.
Yo'lni siqishni evristikasini qo'llashda asimptotikani baholash
Kelinglar, bitta yo'lni siqish evristikasidan foydalanish logaritmik asimptotikaga erishishga imkon beradi: har bir so'rov bo'yicha o'rtacha.
Shuni esda tutingki, operatsiya operatsiyani bajarish uchun ikkita chaqiriqdan va undan ko'p operatsiyalardan iborat bo'lganligi sababli, biz faqat operatsiya vaqtini hisoblashda dalillarga e'tibor qaratishimiz mumkin.
Bir tepalikning og'irligini ushbu tepalikning avlodlari soni deb ataymiz (shu jumladan o'zi ham). Tepaliklarning og'irliklari, shubhasiz, faqat algoritm ishlashi paytida ko'payishi mumkin.
Keling, chekka oralig'ini ushbu qirraning uchlari vaznidagi farq deb ataymiz: (aniqki, ajdodlar vertexi har doim avlod vertikasiga qaraganda ko'proq vaznga ega). Shuni ta'kidlash kerakki, har qanday sobit qirralarning diapazoni faqat algoritm ishlashi paytida ko'payishi mumkin.
Bundan tashqari, biz qirralarni sinflarga ajratamiz: agar uning diapazoni segmentga tegishli bo'lsa, chekka sinfga ega deb aytamiz. Shunday qilib, chekka sinf - dan raqam.
Keling, o'zboshimchalik bilan vertikani tuzatamiz va ajdodidagi qirraning qanday o'zgarishini kuzatamiz: avval u yo'q (tepa etakchi bo'lsa), keyin chekka ba'zi tepalikka tortiladi (tepalik bilan to'plam boshqa to'plamga qo'shilganda) , keyin esa qo'ng'iroqlar paytida yo'llarni siqish uchun o'zgarishi mumkin. Bizni faqat oxirgi holatdagi asimptotik xatti-harakatlar qiziqtirishi aniq (yo'llarni siqish paytida): qolgan barcha holatlar bitta so'rov uchun vaqt talab qiladi.
Muayyan operatsiya chaqirig'ining ishini ko'rib chiqing: u daraxtda ma'lum bir yo'l bo'ylab ketadi, bu yo'lning barcha qirralarini yo'q qiladi va ularni rahbarga yo'naltiradi.
Ushbu yo'lni ko'rib chiqing va har bir sinfning oxirgi qirrasini (ya'ni, sinfdan ko'pi bilan bir chetini) chiqarib tashlang. Shunday qilib, biz har bir so'rovdan qirralarni chiqarib tashladik.
Endi ushbu yo'lning barcha boshqa qirralarini ko'rib chiqing. Har bir shunday chekka uchun, agar u sinfga ega bo'lsa, unda bu yo'lda sinfning yana bitta qirrasi bor ekan (aks holda biz hozirgi chekkani sinfning yagona vakili sifatida chiqarib tashlashimiz kerak edi). Shunday qilib, yo'lni qisqartirgandan so'ng, bu chekka hech bo'lmaganda sinfning chetiga almashtiriladi. Chegaraning vazni kamayishi mumkin emasligini hisobga olsak, so'rov ta'sirida bo'lgan har bir tepalik uchun ajdodidagi chekka chiqarib tashlangan yoki o'z sinfini qat'iy oshirganligini aniqlaymiz.
Bu erda biz nihoyat so'rovlarning asimptotik xatti-harakatlarini olamiz: bu (for) o'rtacha har bir so'rov uchun logaritmik ish vaqtini anglatadi.
Rivojlanish evristik
Keling, bu erda yana bir evristikani ko'rib chiqaylik, u o'zi algoritmning ishlash vaqtini tezlashtirishi mumkin va siqishni evristikasi yo'l bilan birgalikda o'rtacha har bir so'rov bo'yicha deyarli doimiy ish vaqtiga erishishga qodir.
Ushbu evristik ishdagi kichik o'zgarishdir: agar sodda dasturda qaysi daraxt bog'lanib qolishi tasodifan aniqlansa, endi biz buni darajalarga qarab qilamiz.
Darajali evristikaning ikkita varianti mavjud: bitta variantda daraxtning darajasi undagi tepalar soni, ikkinchisida daraxtning chuqurligi (aniqrog'i, daraxt chuqurligining yuqori chegarasi, chunki yo'lni siqish evristikasi birgalikda ishlatilganda, daraxtning haqiqiy chuqurligi pasayishi mumkin).
Ikkala holatda ham evristikaning mohiyati bir xil: ijro etilganda biz quyi darajadagi daraxtni yuqori darajadagi daraxtga qo'shamiz.
Daraxt o'lchamlari asosida darajali evristikani amalga oshirish:
void make_set (int v) {
parent[v] = v;
size[v] = 1;
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (size[a] < size[b])
swap (a, b);
parent[b] = a;
size[a] += size[b];
}
}

Daraxt chuqurligiga asoslangan darajadagi evristikani amalga oshirish:

void make_set (int v) {
parent[v] = v;
rank[v] = 0;
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = a;
if (rank[a] == rank[b])
++rank[a];
}
}
Darajali evristikaning ikkala varianti ham asimptotik jihatidan tengdir, shuning uchun amalda ulardan birini qo'llash mumkin.
Raqamli evristikani qo'llashda asimptotikani baholash
Yo'lni siqish evristikisiz, faqat darajali evristikadan foydalanganda disjunkt to'plamlar tizimining asimptotik harakati o'rtacha har bir so'rov uchun logarifmik bo'ladi:.
Bu erda biz darajadagi evristikaning har qanday ikkita variantidan har biri uchun har bir daraxtning chuqurligi qiymat bo'lishini ko'rsatamiz , bu avtomatik ravishda so'rov uchun logaritmik asimptotikani va shuning uchun so'rovni bildiradi.
Daraxt chuqurligiga asoslangan darajadagi evristikani ko'rib chiqing. Agar daraxtning darajasi teng bo'lsa, unda bu daraxtda hech bo'lmaganda tepaliklar borligi ko'rsatiladi (shundan u avtomatik ravishda bu darajaga, shuning uchun daraxtning chuqurligiga qiymat bo'ladi). Biz buni induksiya bilan isbotlaymiz: buning uchun bu aniq. Yo'llar siqilgan bo'lsa, chuqurlik faqat pasayishi mumkin. Daraxtning darajasi unga daraja daraxti qo'shilgan paytdan ko'tariladi; Induksiya gipotezasini ushbu ikkita daraxtga qo'llagan holda, biz yangi darajadagi daraxt, albatta, talab qilinganidek, hech bo'lmaganda tepaliklarga ega bo'lishini aniqlaymiz.
Endi daraxt o'lchamlari uchun evristik darajani ko'rib chiqing. Keling, agar daraxtning kattaligi teng bo'lsa, unda uning balandligi maksimal darajada ekanligini ko'rsatamiz. Biz buni induksiya bilan isbotlaymiz: chunki bu gap to'g'ri. Siqish yo'llari faqat chuqurlikni pasaytirishi mumkin, shuning uchun siqish yo'llari hech narsani buzmaydi. Keling, o'lchamdagi ikkita daraxtni birlashtiraylik; u holda, induksiya gipotezasi bo'yicha ularning balandliklari mos ravishda kamroq yoki teng bo'ladi va. Umumiylikni yo'qotmasdan, biz birinchi daraxt kattaroq () deb hisoblaymiz, shuning uchun birlashtirilgandan so'ng, hosil bo'lgan daraxtning tepalikdagi chuqurligi quyidagicha bo'ladi:
Dalilni to'ldirish uchun quyidagilarni ko'rsatish kerak:


bu deyarli aniq tengsizlik, chunki  и  .
Evristikani birlashtirish: yo'lni siqish va daraja evristikasi
Yuqorida ta'kidlab o'tilganidek, ushbu evristikadan birgalikda foydalanish, ayniqsa, eng yaxshi natijalarni beradi va oxir-oqibat deyarli doimiy ish vaqtiga etadi.
Biz bu erda asimptotikaning dalillarini taqdim etmaymiz, chunki u juda katta (qarang, masalan, Kormen, Leyzerson, Rivst, Shtayn "Algoritmlar. Qurilish va tahlil"). Ushbu dalil birinchi marta Tarjan tomonidan amalga oshirilgan (1975).
Yakuniy natija quyidagicha: yo'lni siqish va darajaga qo'shilish evristikadan birgalikda foydalanilganda, so'rov bo'yicha ish vaqti o'rtacha bo'lib, teskari Ackerman funktsiyasi qaerda, u juda sekin o'sib boradi, shuning uchun barcha oqilona cheklovlar uchun u sekin ishlamaydi 4 dan oshishi kerak (taxminan) ...
Shuning uchun "deyarli doimiy ish vaqti" ajratilgan to'plamlar tizimining asimptotik harakati haqida gapirish o'rinli.
Bu ikkala evristikani amalga oshiradigan disjoint setlar tizimining yakuniy tatbiqi (daraxt chuqurligi bo'yicha darajadagi evristikadan foydalaniladi):
void make_set (int v) {
parent[v] = v;
rank[v] = 0;
}
int find_set (int v) {
if (v == parent[v])
return v;
return parent[v] = find_set (parent[v]);
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = a;
if (rank[a] == rank[b])
++rank[a];
}
}
Vazifalardagi dasturlar va turli xil yaxshilanishlar
Ushbu bo'limda biz ma'lumotlar bazasi tarkibiy qismlarining ahamiyatsiz va ba'zi bir qo'shimcha tuzilmalaridan foydalanib, birlashtirilgan tizim tizimining bir nechta ishlatilishini ko'rib chiqamiz.
Grafikka ulanish komponentlarini qo'llab-quvvatlash
Bu ma'lumotlar ajratilgan ma'lumotlar tizimining aniq qo'llanilishlaridan biri bo'lib, bu ushbu tuzilmani o'rganishni rag'batlantirganga o'xshaydi.
Rasmiy ravishda, muammo quyidagicha shakllantirilishi mumkin: dastlab bo'sh grafik berilgan, asta-sekin vertikallar va yo'naltirilmagan qirralar ushbu grafaga qo'shilishi mumkin va so'rovlar qabul qilinadi - "tepaliklarmi va bir xil bog'langan komponentlarda yotadimi?"
Bu erda yuqorida tavsiflangan ma'lumotlar tuzilishini to'g'ridan-to'g'ri qo'llash orqali biz vertikal / chekka qo'shish uchun bitta so'rovni yoki ikkita tepalikni tekshirish bo'yicha so'rovni o'rtacha deyarli doimiy vaqt ichida ishlab chiqadigan echimni olamiz.
Minimal uzunlikdagi daraxtni topish uchun Kruskal algoritmidan foydalanganda deyarli bir xil muammo yuzaga kelganligini hisobga olsak, darhol ushbu algoritmning deyarli chiziqli vaqt ichida ishlaydigan takomillashtirilgan versiyasini olamiz.
Ba'zan, amalda, bu muammoning teskari versiyasi mavjud: dastlab ba'zi tepaliklar va qirralar bilan grafik mavjud va qirralarni olib tashlash uchun so'rovlar olinadi. Agar vazifa oflayn rejimda berilsa, ya'ni. barcha so'rovlarni oldindan bilib olishimiz mumkin, keyin bu muammoni quyidagicha hal qilish mumkin: muammoni orqaga burish: bizda qirralar qo'shilishi mumkin bo'lgan bo'sh grafik bor deb o'ylaymiz (avval biz oxirgi so'rovning chetini qo'shamiz, keyin oldingi va boshqalar)). Shunday qilib, ushbu muammoni teskari aylantirish natijasida biz odatdagi muammoga keldik, uning echimi yuqorida tavsiflangan edi.
Tasvirdagi ulanish komponentlarini topish
DSU ning sirt dasturlaridan biri bu quyidagi muammoni hal qilishdir: piksellar tasviri mavjud. Dastlab, butun rasm oq rangga ega, ammo keyin unga bir nechta qora piksellar tortiladi. Yakuniy rasmda har bir "oq" ulanish komponentining hajmini aniqlash talab qilinadi.
Buni hal qilish uchun biz shunchaki tasvirning barcha oq hujayralarini ko'rib chiqamiz, chunki har bir hujayra uchun to'rtta qo'shnisi orqali o'tamiz va agar qo'shni ham oq bo'lsa, biz ushbu ikkita tepadan qo'ng'iroq qilamiz. Shunday qilib, biz rasmdagi piksellarga mos keladigan tepaliklar bilan DSUga ega bo'lamiz. Natijada paydo bo'lgan DSU daraxtlari kerakli ulanish komponentlari hisoblanadi.
Ushbu muammoni chuqurlikdan birinchi o'tish (yoki kenglikdan birinchi o'tish) yordamida osonroq hal qilish mumkin, ammo bu erda tavsiflangan usul aniq ustunlikka ega: u matritsani satrlar bo'yicha qayta ishlashi mumkin (faqat joriy satrda, oldingi qatorda ishlaydi, va bir xil qator elementlari uchun qurilgan disjoint set tizimi), ya'ni. xotira tartibidan foydalanish.
Har bir to'plam uchun qo'shimcha ma'lumotlarni qo'llab-quvvatlaydi
"Ajratilgan to'plam tizimi" har qanday qo'shimcha to'plam bilan bog'liq ma'lumotlarni saqlashni osonlashtiradi.
Oddiy misol - bu to'plamlarning o'lchamlari: ularni qanday saqlash haqida daraja evristikasi tavsifida tasvirlangan (u erda to'plamning amaldagi rahbari uchun ma'lumot yozilgan).
Shunday qilib, har bir to'plamning etakchisi bilan birgalikda siz aniq vazifada talab qilingan har qanday qo'shimcha ma'lumotlarni saqlashingiz mumkin.
Bo'shliq bo'ylab hopni siqish uchun DSU-dan foydalanish. Oflayn rasm ishlash
DSU ning keng tarqalgan qo'llanilishlaridan biri shundaki, agar elementlar to'plami bo'lsa va har bir elementdan bitta chekka chiqsa, u holda biz (deyarli doimiy vaqt ichida) chekka bo'ylab harakatlanadigan bo'lsak, biz tezda qaerga boramiz? berilgan boshlang'ich nuqtadan.
Ushbu dasturning yorqin namunasi pastki qismlarni bo'yash muammosi: uzunlik segmenti mavjud, uning har bir katakchasi (ya'ni har bir uzunlik bo'lagi) nol rangga ega. Shaklning so'rovlari mavjud - segmentni rangga bo'yash. Har bir katakning yakuniy rangini topish talab qilinadi. So'rovlar oldindan ma'lum deb hisoblanadi, ya'ni. vazifa oflayn.
Ushbu muammoni hal qilish uchun har bir katak uchun o'ng tomonga rangsiz katakchaga havolani saqlaydigan DSU-tuzilmasini yaratishimiz mumkin. Shunday qilib, dastlab har bir hujayra o'ziga ishora qiladi va birinchi bo'linmani bo'yab bo'lgandan so'ng, bo'linma boshlanishidan oldin hujayra bo'linma tugaganidan keyin katakchaga ishora qiladi.
Endi, muammoni hal qilish uchun biz qayta tiklash bo'yicha so'rovlarni teskari tartibda ko'rib chiqamiz: oxirgisidan birinchisiga. So'rovni bajarish uchun biz har safar DSU yordamida segment ichidagi eng chap rangsiz katakchani topamiz, uning rangini o'zgartiramiz va ko'rsatgichni undan o'ngdagi keyingi bo'sh katakchaga o'tkazamiz.
Shunday qilib, biz aslida DSU-ni siqishni evristik yo'li bilan ishlatmoqdamiz, ammo darajadagi evristikasiz (chunki birlashgandan keyin kim etakchiga aylanishi biz uchun muhim). Natijada, natijada assimptotiklar har bir so'rov bo'yicha bo'ladi (ammo boshqa ma'lumotlar tuzilmalari bilan taqqoslaganda kichik doimiy).
Amalga oshirish:
void init() {
for (int i=0; i make_set (i);
}
void process_query (int l, int r, int c) {
for (int v=l; ; ) {
v = find_set (v);
if (v >= r) break;
answer[v] = c;
parent[v] = v+1;
}
}
Biroq, ushbu echimni darajadagi evristik bilan amalga oshirish mumkin: biz har bir to'plam uchun ushbu to'plam tugaydigan ba'zi bir qatorda saqlaymiz (ya'ni eng o'ng nuqta). Keyin ikkala to'plamni ularning evristik darajalariga ko'ra birlashtirish mumkin, so'ngra hosil bo'lgan to'plamga yangi o'ng chegarani belgilash mumkin bo'ladi. Shunday qilib, biz hal qilamiz.
Liderni masofadan qo'llab-quvvatlash
Ba'zan, ajratilgan to'plam tizimining aniq dasturlarida etakchiga masofani saqlab qolish talabi paydo bo'ladi (ya'ni daraxtning chekkalarida yo'lning uzunligi hozirgi tepadan daraxtning ildizigacha).
Agar yo'lni siqish evristikasi bo'lmaganida, unda asoratlar bo'lmaydi - ildizgacha bo'lgan masofa shunchaki funktsiya bajarilgan rekursiv chaqiriqlar soniga teng bo'lar edi.
Biroq, yo'llarning siqilishi natijasida yo'lning bir nechta qirralari bir chekkaga qisqarishi mumkin. Shunday qilib, har bir tepalik bilan birga siz qo'shimcha ma'lumotlarni saqlashingiz kerak bo'ladi: tepalikdan ajdodgacha bo'lgan chekka uzunligi.
Amalga oshirishda massiv va funktsiya endi bitta raqam emas, balki juft sonni qaytarishini tasavvur qilish qulay: etakchi tepalik va unga masofa:
void make_set (int v) {
parent[v] = make_pair (v, 0);
rank[v] = 0;
}
pair find_set (int v) {
if (v != parent[v].first) {
int len = parent[v].second;
parent[v] = find_set (parent[v].first);
parent[v].second += len;
}
return parent[v];
}
void union_sets (int a, int b) {
a = find_set (a) .first;
b = find_set (b) .first;
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = make_pair (a, 1);
if (rank[a] == rank[b])
++rank[a];
}
}
Yo'l uzunligining tengligini qo'llab-quvvatlash va grafning ikkitomonlama bo'lishini onlayn tekshirish
Rahbarga boradigan yo'lning uzunligiga o'xshashlik bilan, unga yo'lning uzunligini tengligini saqlab qolish ham mumkin. Nima uchun ushbu dastur alohida xatboshida ta'kidlangan?
Haqiqat shundaki, odatda yo'lning paritetini saqlash talablari quyidagi muammo bilan bog'liq holda paydo bo'ladi: dastlab bo'sh grafik berilgan, unga qirralar qo'shilishi mumkin va shaklning so'rovlari "bu o'z ichiga olgan bog'langan komponent. vertex bipartit berilganmi? "
Ushbu muammoni hal qilish uchun biz ulanish komponentlarini saqlash uchun ajratilgan to'plamlar tizimini yaratishimiz va har bir tepada uning etakchisiga yo'l uzunligining tengligini saqlashimiz mumkin. Shunday qilib, biz belgilangan chekka qo'shilishi grafaning ikkiga bo'linishini buzilishiga olib keladimi yoki yo'qligini tezda tekshirib ko'ramiz: agar chekka uchlari bir xil bog'langan komponentda yotsa va shu bilan bir vaqtda bo'lsa etakchiga yo'l uzunligining tengliklari, keyin bu chekkaning qo'shilishi g'alati uzunlik tsiklining shakllanishiga va hozirgi komponentning ikki tomonlama bo'lmaganga aylanishiga olib keladi.
Bunda duch keladigan asosiy qiyinchilik shundaki, biz paritetlarni hisobga olgan holda, ikkita daraxtni funktsiyalarga birlashtirishimiz kerak.
Agar biz ikkita bog'langan komponentni biriga bog'laydigan chekka qo'shsak, unda bitta daraxtni boshqasiga qo'shganda, biz unga shunday tenglikni ko'rsatishimiz kerak, natijada tepalar yo'l uzunligining turli xil paritetlariga ega bo'ladi.
Keling, bu tenglikni olish kerak bo'lgan formulani keltiraylik, u boshqa to'plamning etakchisiga qo'shilganda bitta to'plamning etakchisiga o'rnatiladi. Keling, tepalikdan uning to'plamiga etakchiga boradigan yo'l uzunligining tengligi bilan belgilaymiz, vertexdan uning to'plamiga etakchisigacha bo'lgan yo'l uzunligining tengligini va izlanayotgan paritetni belgilaymiz. biz biriktirilgan rahbarga tayinlashimiz kerak. Agar tepalikka ega bo'lgan to'plam vertex bilan to'plamga qo'shilib, subtreega aylansa, u holda tepada qo'shilgandan keyin uning tengligi o'zgarmaydi va teng bo'lib qoladi va tepada tenglik teng bo'ladi (bu erda belgi XOR operatsiyasini bildiradi (nosimmetrik farq)). Bizga bu ikki parite turlicha bo'lishi kerak, ya'ni. ularning XOR bittaga teng edi. O'sha. biz quyidagi t tenglamani olamiz:

shuni hal qilishda biz quyidagilarni topamiz:

Shunday qilib, qaysi to'plam qaysi biriga qo'shilishidan qat'i nazar, ko'rsatilgan formuladan foydalanib, bitta etakchidan boshqasiga tortilgan qirralarning tengligini o'rnatish kerak.
Paritetni qo'llab-quvvatlaydigan DSU dasturi. Oldingi xatboshida bo'lgani kabi, qulaylik uchun biz ajdodlarimiz va operatsiya natijalarini saqlash uchun juftliklardan foydalanamiz. Bundan tashqari, har bir to'plam uchun, biz hali ham ikki tomonlama yoki yo'qligidan qat'i nazar, qatorda saqlaymiz.
void make_set (int v) {
parent[v] = make_pair (v, 0);
rank[v] = 0;
bipartite[v] = true;
}
pair find_set (int v) {
if (v != parent[v].first) {
int parity = parent[v].second;
parent[v] = find_set (parent[v].first);
parent[v].second ^= parity;
}
return parent[v];
}
void add_edge (int a, int b) {
pair pa = find_set (a);
a = pa.first;
int x = pa.second;
pair pb = find_set (b);
b = pb.first;
int y = pb.second;
if (a == b) {
if (x == y)
bipartite[a] = false;
}
else {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = make_pair (a, x ^ y ^ 1);
bipartite[a] &= bipartite[b];
if (rank[a] == rank[b])
++rank[a];
}
}
bool is_bipartite (int v) {
return bipartite[ find_set(v) .first ];
}
O'rtacha oflayn rejimda RMQ (segment bo'yicha minimal) topish algoritmi
Rasmiy ravishda, muammo quyidagicha qo'yilgan: siz ikkita turdagi so'rovlarni qo'llab-quvvatlaydigan ma'lumotlar tuzilishini amalga oshirishingiz kerak: belgilangan raqamni qo'shish () va hozirgi minimal raqamni topish va olish. Har bir raqam aniq bir marta qo'shilgan deb o'ylaymiz.
Bundan tashqari, biz so'rovlarning butun ketma-ketligi bizga oldindan ma'lum, ya'ni. vazifa oflayn.
Qarorning g'oyasi quyidagicha. Har bir so'rovga navbat bilan javob berish o'rniga, keling, raqamni takrorlang va ushbu raqam qaysi so'rovga javob bo'lishi kerakligini aniqlaymiz. Buning uchun biz ushbu raqamni qo'shgandan so'ng birinchi javobsiz so'rovni topishimiz kerak - bu so'rov, uning javobi raqam ekanligini tushunish oson.
Shunday qilib, bu erda chiziq segmentlarini bo'yash muammosiga o'xshash g'oya olinadi.
Agar biz evristik darajadan voz kechsak va har bir elementda o'ng tomonga eng yaqin so'rovga havolani saqlasak va qo'shilgandan keyin ushbu havolalarni saqlab qolish uchun yo'lni siqishni ishlatsak, har bir so'rov bo'yicha o'rtacha echim olishimiz mumkin.
Bundan tashqari, agar biz evristik darajadan foydalansak va har bir to'plamda u tugagan joyning raqamini saqlasak (echimning oldingi versiyasida havolalar doimo faqat o'ng tomonga qarab ketganligi sababli avtomatik ravishda erishilgan narsa uchun) echimini olishingiz mumkin. , endi do'kon kerak bo'ladi).
Oflayn o'rtacha uchun LCA (daraxtdagi eng kam tarqalgan ajdod) ni topish algoritmi
Tarjanning LCA-ni o'rtacha onlayn rejimida topish algoritmi tegishli maqolada tasvirlangan. Ushbu algoritm soddaligi bilan boshqa LCA qidirish algoritmlari bilan yaxshi taqqoslanadi (ayniqsa optimal Farah-Colton-Bender algoritmi bilan taqqoslaganda).
DSU-larni to'plamlarning aniq ro'yxati sifatida saqlash. Ushbu fikrni turli xil ma'lumotlar tuzilmalarini birlashtirishda qo'llash
DSUni saqlashning muqobil usullaridan biri bu har bir to'plamni o'z a'zolarining aniq saqlangan ro'yxati sifatida saqlashdir. Shu bilan birga, har bir element o'z to'plamining vakili (etakchisi) bilan aloqani saqlab qoladi.
Bir qarashda, bu ma'lumotlar samarasiz tuzilishga o'xshaydi: ikkita to'plamni birlashtirganda, biz bitta ro'yxatni ikkinchisining oxiriga qo'shishimiz kerak, shuningdek ikkita ro'yxatning birining barcha elementlari uchun etakchini yangilashimiz kerak.
Ammo shuni ko'rsatadiki, yuqorida tavsiflanganga o'xshash vaznli evristikadan foydalanish asimptotikani sezilarli darajada kamaytirishi mumkin: elementlar bo'yicha so'rovlarni bajarish uchun.
Og'irlikdagi evristika shuni anglatadiki, biz har doim ikkala to'plamning kichikini kattaroqiga qo'shamiz. Bir to'plamni boshqasiga qo'shishni qo'shilgan to'plamning kattaligi tartibida amalga oshirish oson va rahbarni qidirish ushbu saqlash usuli bilan vaqt talab etadi.
So'rovni bajarish uchun asimptotikani isbotlaylik. Ixtiyoriy elementni tuzatamiz va birlashma operatsiyalari unga qanday ta'sir qilganini ko'rib chiqamiz. Element birinchi marta ta'sirlanganda, biz uning yangi to'plamining hajmi hech bo'lmaganda bo'lishini ta'kidlashimiz mumkin. Ikkinchi marta ishlaganda, u hech bo'lmaganda kattalikka tushib qoladi deb bahslashish mumkin (chunki biz kattaroqqa kichikroq to'plam qo'shamiz). Va shunga o'xshash narsalar - biz elementga birlashma operatsiyalari maksimal darajada ta'sir qilishi mumkin. Shunday qilib, barcha vertikallar yig'indisida bu har bir so'rov uchun bitta ortiqcha - isbotlanishi kerak bo'lgan narsa.
Amalga oshirishga misol keltiraylik:
vector lst[MAXN];
int parent[MAXN];
void make_set (int v) {
lst[v] = vector (1, v);
parent[v] = v;
}
int find_set (int v) {
return parent[v];
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (lst[a].size() < lst[b].size())
swap (a, b);
while (!lst[b].empty()) {
int v = lst[b].back();
lst[b].pop_back();
parent[v] = a;
lst[a].push_back (v);
}
}
}
Bundan tashqari, kichikroq to'plam elementlarini kattaroq qismga qo'shish g'oyasi DSUdan tashqarida, boshqa muammolarni hal qilishda ishlatilishi mumkin.
Masalan, quyidagi muammoni ko'rib chiqing: har bir bargiga raqam berilgan daraxt berilgan (har xil barglarda bir xil son bir necha marta bo'lishi mumkin). Daraxtning har bir tuguni uchun uning kichik daraxtidagi aniq sonlar sonini aniqlash kerak.
Xuddi shu fikrni ushbu muammoga qo'llash orqali siz quyidagi echimni topishingiz mumkin: keling, daraxt orqali chuqurlik bo'ylab harakatlanishni boshlaymiz, bu ko'rsatkichni raqamlarga qaytaradi - bu vertexning pastki daraxtidagi barcha raqamlar ro'yxati. So'ngra, hozirgi tepalikka javob olish uchun (agar u, albatta, agar u barg bo'lmasa), ushbu vertikalning barcha bolalaridan birinchi chuqurlik bo'ylab o'tishni chaqirishingiz va olinganlarning barchasini bitta o'lchamga birlashtirishingiz kerak. hozirgi tepalik uchun javob bo'ladi. Bir nechtasini samarali tarzda birlashtirish uchun yuqorida tavsiflangan usulni qo'llang: biz ikkita to'plamni birlashtiramiz, shunchaki kichik to'plamning bitta elementini kattaroq qismga qo'shamiz. Natijada, biz bitta yechimni topamiz, chunki bitta elementni qo'shish amalga oshiriladi.
DSUlarni aniq daraxt tuzilishini saqlagan holda saqlang. To'xtatish. O'rtacha onlayn rejimida grafikada ko'priklarni topish algoritmi
Disjoint set tizimining ma'lumotlar tuzilmasining kuchli qo'llanilishlaridan biri shundaki, u bir vaqtning o'zida siqilgan va siqilmagan daraxt tuzilmalarini saqlashga imkon beradi. Siqilgan inshoot yordamida daraxtlarni tezda birlashtirish va ikkita tepalik bir daraxtga tegishli yoki yo'qligini tekshirish uchun ishlatilishi mumkin, siqilmagan struktura yordamida berilgan ikkita tepalik orasidagi yo'lni topish yoki daraxt tuzilishining boshqa o'tishi uchun foydalanish mumkin.
Amalga oshirilganda, bu DSU uchun odatdagi siqilgan ajdodlar qatoriga qo'shimcha ravishda bizda oddiy, siqilmagan ajdodlar qatori bo'ladi. Bunday massivni asimptotikani hech qanday yomonlashtirmasligi aniq: undagi o'zgarishlar faqat ikkita daraxt birlashganda va faqat bitta elementda sodir bo'ladi.
Boshqa tomondan, amalda qo'llanganda, ko'pincha ikkita daraxtni belgilangan chekka bilan bog'lashni o'rganish kerak, bu ularning ildizlaridan chiqib ketishi shart emas. Bu shuni anglatadiki, biz daraxtlardan birini ko'rsatilgan tepada qayta osib qo'yishdan boshqa ilojimiz yo'q, shunda biz ushbu daraxtni boshqasiga qo'shib, shu daraxtning ildizini qo'shilgan qirraning ikkinchi uchiga bolalar vertikasi qilib qo'yamiz. .
Bir qarashda, haddan tashqari to'xtatib turish juda qimmatga tushadi va asimptotikani ancha yomonlashtiradi. Darhaqiqat, daraxtni tepalikka qayta osib qo'yish uchun biz hamma joydan va ko'rsatkichlarni yangilab, bu tepadan daraxtning ildizigacha borishimiz kerak.
Ammo, aslida, hamma narsa yomon emas: bitta ittifoqning asimptotikasini o'rtacha qiymatiga tenglashtirish uchun shunchaki kichikroq bo'lgan ikkita daraxtning birini osib qo'yish kifoya.
Qo'shimcha ma'lumot olish uchun (shu jumladan, asimptotikaning dalillari) onlayn ko'prik qidirish algoritmiga qarang.
Tarixiy retrospektiv
Ma'lumotlar tarkibi "disjoint set system" nisbatan uzoq vaqtdan beri ma'lum bo'lgan.
Ushbu inshootni daraxtlar o'rmoni shaklida saqlash usuli aftidan birinchi bo'lib Galler va Fisher tomonidan 1964 yilda tasvirlangan (Galler, Fisher "Yaxshilangan ekvivalentlik algoritmi"), ammo asimptotikani to'liq tahlil qilish ancha kechroq amalga oshirildi.
Yo'lning qisqarishi va unifikatsiya evristikasi McIlroy va Morris tomonidan va mustaqil ravishda Tritter tomonidan ishlab chiqilgan ko'rinadi.
Bir muncha vaqt davomida Hopkroft va Ullman tomonidan 1973 yilda berilgan o'rtacha hisobda bitta operatsiya uchun faqat taxmin ma'lum bo'lgan (Hopcroft, Ullman "Set-merging algomthms") - mana takrorlangan logaritma (bu asta-sekin o'sib boruvchi funktsiya, ammo baribir emas teskari Ackermann funktsiyasi kabi sekin).
Birinchi marta teskari Ackermann funktsiyasi qaerda ekanligini taxmin qilishni Tarjan 1975 yilgi maqolasida olgan (Tarjan "Yaxshi, lekin chiziqli bo'lmagan birlashma algoritmining samaradorligi"). Keyinchalik 1985 yilda u va Leuven ushbu vaqtinchalik bahoni bir necha xil darajadagi evristika va yo'llarni siqish usullari uchun qo'lga kiritdi (Tarjan, Lyuven "Set Union Algoritmlarning eng yomon holati").
Va nihoyat, Fredman va Saks 1989 yilda qabul qilingan hisoblash modelida, ajratilgan to'plamlar tizimining har qanday algoritmi kamida o'rtacha ishlashi kerakligini isbotladilar (Fredman, Saks "Dinamik ma'lumotlar tuzilmalarining hujayra tekshiruvi murakkabligi").
Shu bilan birga, shuni ham ta'kidlash kerakki, bu vaqtinchalik bahoga qarshi chiqadigan va yo'lni siqish va darajadagi birlashma evristikasi bilan ajralib turadigan to'siq tizimi o'rtacha ishlaydi, deb ta'kidlaydi: Zhang "Union-Find Problem is Lineer", Vu, Otoo "A" Yo'lni siqish bilan "Union-Find" ning o'rtacha ishi murakkabligini oddiyroq isboti ".
Onlayn sudyalar
Disjoint set tizimi yordamida echilishi mumkin bo'lgan muammolar ro'yxati:
• TIMUS # 1671 "Anansi Internet" [qiyinchilik: past]
• CODEFORCES 25D "Yo'llar nafaqat Berlendda" [qiyinchilik: o'rta]
• TIMUS # 1003 "Paritet" [qiyinchilik: o'rta]
• SPOJ # 1442 "Zanjir" [qiyinchilik: o'rta]
Foydalanilgan adabiyotlar
• Tomas Kormen, Charlz Leyzerson, Ronald Rivest, Klifford Sh Algoritim tushunchasi .

Xulosa
Men Kesishmaydigan to`plamlar uchun ma’lumotlar tuzilmasi haqida mustaqil ish qildim . Bu mustaqil ishni tayyorlsh maboyinida juda qiziqarli ma`lumotlarga ega bo`dim.