|
Referat tekshirdi: Vaffoyev Sunnatillo Mustaqil ish
|
| bet | 1/4 | | Sana | 18.05.2024 | | Hajmi | 221,49 Kb. | | #243271 | | Turi | Referat |
Bog'liq Algoritm-Referat 1, Arxivlashtirish dasturi bilan ishlash reja Kirish. Fayllarni ar, Zulfiya, Tohirjon2, Zavqiddin AL-M1
O‘ZBEKISTON RESPUBLIKASI
RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI NURAFSHON FILIALI
“Kompyuter injiniringi” fakulteti
Guruh nomi: 710-22.
F.I.SH: Qilichev Bahrombek
Fan: Algoritm va loyihalash
REFERAT
Tekshirdi: Vaffoyev Sunnatillo
Mustaqil ish
Variant-12
Graflarni eng arzon tayanch daraxtini qurishda Kruskal xasis algoritmi
Reja:
Kruskal algoritmiga kirish.
Daraxtlarni o'z ichiga olgan va minimal bo'lgan daraxtlar.
Kruskal algoritmining ochko'z yondashuvi.
Kruskal algoritmini bosqichma-bosqich bajarish.
Boshqa Minimal Spanning Daraxt Algoritmlari bilan solishtirish.
Kruskal algoritmiga kirish
Kruskal algoritmi quyidagi tartibda ishlaydi:
Barcha graf qo'shimchalari qimmati bo'yicha saralangan.
Algoritm boshlang'ich darajada bo'lgan bo'ylgan ro'yxatni qo'shimchalarga ochadi.
Har bir qo'shimchani qo'shish uchun, uni qanday tug'unlar bilan ulashishini tekshiradi.
Agar qo'shimcha o'zini grafdagi uzluksizlik tizimi yaratmasa, uni qo'shib olamiz va grafimizni daraxtning tizimi bilan boshqarish uchun ishlatiladigan bo'ylgan qo'shimchalar ro'yxatiga qo'shamiz.
Bu jarayon hamma qo'shimchalarni biriktirish va grafdagi barcha tug'unlarni bog'laydigan eng kichik tizimni olish bilan takrorlanadi.
Algoritmdi barcha qo'shimchalarni qo'shishdan so'ng, grafimiz daraxt tizimi bo'lgan va minimum tashqi qo'shimchalarning miqdori eng kam bo'lgan daraxtni quriladi.
Kruskal algoritmi og'irlikdagi, yo'naltirilmagan grafikning minimal oraliq daraxtini (MST) topish uchun asosiy va keng qo'llaniladigan texnikadir. 1956 yilda kompyuter olimi Jozef Kruskal tomonidan ishlab chiqilgan ushbu ochko'z algoritm ushbu klassik grafik nazariyasi muammosini hal qilishda soddaligi va samaradorligi bilan mashhur. MST - bu asl grafikning pastki grafigi bo'lib, u barcha cho'qqilarni minimal umumiy chekka og'irligi bilan bog'laydi, shu bilan birga tsikllar yo'qligini ta'minlaydi.
Kruskal algoritmining markazida, agar u tsikl yaratmasa, o'sib borayotgan MSTga eng arzon mavjud chekkani iterativ ravishda qo'shish g'oyasi yotadi. Bu jarayon barcha cho'qqilar ulangunga qadar davom etadi, natijada optimal minimal kenglik daraxti olinadi. Algoritmning ochko'z tabiati va aniq belgilangan qadamlari uni tarmoqni optimallashtirishdan tortib transportni rejalashtirishgacha va undan tashqarida keng ko'lamli ilovalar uchun jozibador tanlovga aylantiradi.
|
| |
