|
O'zbekiston respublikasi raqamli texnologiyalar
|
| bet | 2/2 | | Sana | 25.05.2024 | | Hajmi | 337,56 Kb. | | #253425 |
Bog'liq Algoritmlarni loyihalash 25.05(Maruza)Kruskal algoritmi.
Ushbu algoritm 1956 yili Kruskal tomonidan ishlab chiqilgan.
Faraz qilamiz, V = {1, 2, .... n} tugunlar to‘plamidan iborat va E qirralar to‘plamida aniqlangan s narx funksiyasi bilan berilgan G=(V, E) bog‘langan graf bo‘lsin. Kruskal algoritmida G graf uchun minimal narxli daraxtlar skeletini qurish G grafning faqat n ta tugunlaridan tashkil topgan va qirralari bo‘lmagan T=(V, ø) grafdan boshlanadi. Shunday qilib, har bir tugun bog‘langan (o‘zi-o‘zi bilan) komponent hisoblanadi. Algoritm bajarilishi vaqtida bog‘langan komponentlar naboriga ega bo‘lamiz, asta-sekin birlashtirib daraxtlar skeletini tashkillashtiramiz.
Asta-sekin o‘suvchi bog‘langan komponentlarni qurishda E to‘plamdan qirralar ularning narxi o‘sishi tartibida navbatma-navbat tekshiriladi. Agar navbatdagi qirra turli komponentlardagi ikkita tugunni birlashtirsa, u holda bu qirra T grafga qo‘shiladi. Agar bu qirra bitta komponentning ikkita tugunini birlashtirsa, u tashlab yuboriladi, chunki uning bog‘langan komponentga qo‘shilishi sikl hosil bo‘lishiga olib keladi. G grafning barcha tugunlari bitta komponentga tegishli bo‘lsa, T minimal narxli daraxtlar skeletini qurish bu graf uchun tugaydi.
Bo'lib tashla va hukmronlik qil" nimani anglatadi
Dasturlashda, bo'lib tashla va hukmronlik qil — bu algoritmik paradigma bo'lib, bu paradigmaning asosiy g'oyasi algoritmik masalalarni bosh masalaga o'xshash kichik qismlarga bo'lib tashlab, ularni rekursiv hal qilishdan iborat.
Bu paradigmada masala qismlarga bo'linganligi sababli, qism masalalar bosh masalaga qaraganda kichikroq bo'lishi va bu bo'linish to'xtashi uchun asos holat bo'lishi kerak (Rekursiya esingizga tushib ketmadimi?). Barcha turdagi bo'lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo'ladi:
Bo'lib tashlash bosqichi. Bunda bosh masala huddi shu masalaga o'xshash kichikroq masalalarga bo'lib chiqiladi.
Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi.
Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib birlashtirib chiqiladi va bu bosh masala yechimi bo'ladi.
Shu sababli, bo'lib tashla hukmronlik qil paradigmasini 3 ta jumla bilan eslab qolish mumkin: bo'lib tashla, hukmronlik qil, birlashtir. Boshida tushunish ozroq qiyin bo'lishi tabiiy, shuning uchun bu paradigma g'oyasini tasvirlab berishga harakat qilamiz.
1-masala
Belgilardan iborat massiv berilgan. Massivni Quick sort algoritmi bo’yicha saralang
2-masala. Butun sonlardan iborat bir o’lchovli massiv berilgan. “Bo’lib tashla va hkmronlik qil” prinsipidan foydalanib eng katta qiymatini toppish dasturini tuzing.
Int a[]={23,45,34,14,25,43,53,26,33}
Max_element = 53
3-masala. Quyidagi graf uchun Xasislik algoritmlaridan foydalanib eng kichik daraxtni hosil qiling.
|
| |
