“xasis” algoritmlar. Kruskal algoritmi. Prima algoritmi. Xoffman daraxtlari

“XASIS” ALGORITMLAR. KRUSKAL ALGORITMI.PRIMA ALGORITMI.XOFFMAN DARAXTLARI.

BAJARDI : ISROILOVA SHIRIN

REJA: 1. Xasis algoritmlari 2. Kruskal algoritmi 3. Prima algoritmi 4. Xoffman daraxtlari

Xasis algoritm - bu har bir bosqichda mahalliy maqbul qarorlar qabul qilishdan iborat bo'lgan yakuniy echimi ham maqbul deb taxmin qilingan algoritmdir. Agar muammoning tuzilishi “matroid” tomonidan o'rnatilsa, ochko'z algoritmdan foydalanish global maqbullikka olib kelishi ma'lum.
Xasis algoritmlarni «qisqa ko'rish», shuningdek, «tuzatib bo'lmaydigan» sifatida tavsiflash mumkin. Ular faqat "maqbul pastki tuzilishga" ega bo'lgan muammolar uchun idealdir. Shunga qaramay, ko'plab oddiy muammolar uchun eng yaxshi mos keladigan algoritmlar ochko'z algoritmlardir. Shunisi e'tiborga loyiqki, ochko'z algoritmni tanlash algoritmi sifatida qidirish yoki tarmoq bilan bog'langan algoritmning ustuvorliklarini belgilash uchun foydalanish mumkin. Ochko'z algoritm uchun bir nechta o'zgarishlar mavjud:
Xasis algoritmlarni «qisqa ko'rish», shuningdek, «tuzatib bo'lmaydigan» sifatida tavsiflash mumkin. Ular faqat "maqbul pastki tuzilishga" ega bo'lgan muammolar uchun idealdir. Shunga qaramay, ko'plab oddiy muammolar uchun eng yaxshi mos keladigan algoritmlar ochko'z algoritmlardir. Shunisi e'tiborga loyiqki, ochko'z algoritmni tanlash algoritmi sifatida qidirish yoki tarmoq bilan bog'langan algoritmning ustuvorliklarini belgilash uchun foydalanish mumkin. Ochko'z algoritm uchun bir nechta o'zgarishlar mavjud:
-Sof ochko'z algoritmlar
-Ortogonal ochko'z algoritmlar
-Tinchlantiruvchi ochko'z algoritmlar
Kruskal algoritmi. Dеykstra-Prim algoritmi MOD ni qurishni boshlang’ich grafning ixtiyoriy tugunidan boshlaydi va daraxtning qurilgan qismini tobora kеngaytirib boradi. Ushbu algoritmdan farqli ravishda Kruskal algoritmi asosiy e'tiborni graf tomonlariga qaratadi. Bunda ishni bo’sh grafdan boshlab, unga tomonlarini ular vaznining o’sib borish tartibida kеtma-kеt qo’shib boradi. Bu jarayon grafga kiruvchi barcha tugunlar o’zaro bog’langunga qadar davom etadi. Agar tomonlarni qo’shib olish jarayoni barcha tugunlar o’zaro bog’langunga qadar tugatilsa, boshlan?ich grafning to’liq bog’lanmagan ekanligi kеlib chiqadi. Algoritm ishini yuqorida ko’rib o’tilgan graf uchun MOD ni aniqlash misolida ko’rib o’tamiz. Ishni eng kichik vaznli DF tomondan boshlaymiz. Boshlang’ich garf v rasmda ifodalangan.
Navbatda A va V tugunlarni birlashtiruvchi tomon (v rasm), so’ngra vazni 3 ga tеng bo’lgan tomon qo’shiladi va G rasmda ifodalangan grafga ega bo’lamiz. Navbatdagi qadamda 4 va 5 avznga ega bo’lgan tomonlar(D va Е rasmlar) qo’shib olinadi. Natijada qo’shilmagan faqat G tugun qoladi. Kеyingi qadamda vazni 6 ga tеng tomonlarni qayta ishlash kеrak bo’ladi. Vazni 6 ga tеng bo’lgan to’rtta tomondan ikkitasini qoldiramiz. Natijada qaysi ikki tomonning qoldirilishiga bo?liq holda J yoki Z rasmlarda ifodalangan MOD lardan biriga ega bo’lamiz.
Jozef Kruskal tomonidan ishlab chiqilgan algoritm Amerika matematik jamiyati ishida 1956 yilda paydo bo'lgan. Kruskal algoritmini uchta oddiy qadam bilan ifodalash mumkin.
N tugunli grafik va har bir qirraning tegishli og'irligi hisobga olinsa,
1. Butun grafikning eng kichik og'irligi bo'lgan yoyni tanlang va daraxtga qo'shing va grafikdan o'chiring.
2. Qolganlardan, tsikl hosil qilmaydigan tarzda, eng kam vaznli chekkani tanlang. Daraxtga chekkasini qo'shing va grafikdan o'chiring. (Ikki yoki undan ortiq minimallar mavjud bo'lsa, birini tanlang)
3. Jarayonni 2 -bosqichda takrorlang.
Bu usulda algoritm eng kam qirrali bilan boshlanadi va har bir tsiklda har bir chekkani tanlashda davom etadi. Shuning uchun algoritmda grafikni ulash shart emas. Kruskal algoritmining vaqt murakkabligi O (logV)
Prim algoritmi haqida batafsil Algoritmni 1930 yilda chex matematikasi Voytox Yarnik, keyinroq mustaqil ravishda 1957 yilda kompyuter olimi Robert C. Prim tomonidan ishlab chiqilgan. 1959 yilda Edsger Dijkstra tomonidan qayta kashf qilingan. Algoritm uchta asosiy bosqichda ifodalanishi mumkun; N tugunlari va har bir qirraning tegishli og'irligi bilan bog'langan grafikni hisobga olgan holda, 1. Grafikdan ixtiyoriy tugunni tanlang va uni T daraxtiga qo'shing (bu birinchi tugun bo'ladi) 2. Daraxtdagi tugunlarga ulangan har bir qirraning og'irligini ko'rib chiqing va minimalini tanlang. T daraxtining boshqa uchidagi chekka va tugunni qo'shing va qirrani grafikdan olib tashlang. (Ikki yoki undan ortiq minimallar mavjud bo'lsa, birini tanlang) 3. Daraxtga n-1 qirralari qo'shilmaguncha, 2-qadamni takrorlang. Bu usulda daraxt bitta ixtiyoriy tugun bilan boshlanadi va har bir tsikl bilan shu tugundan boshlab kengayadi. Demak, algoritm to'g'ri ishlashi uchun grafik bog'langan grafik bo'lishi kerak. Prim algoritmining asosiy shakli O (V 2 ) vaqt murakkabligiga ega.
Kruskal va Prim algoritmi o'rtasidagi farq nima?
• Prim algoritmi tugun bilan boshlanadi, Kruskal algoritmi chekka bilan boshlanadi.
• Prim algoritmlari bir tugundan ikkinchisigacha cho'zilgan, Kruskal algoritmi esa qirralarning joylashuvi oxirgi bosqichga asoslanmagan tarzda tanlangan.
• Prim algoritmida grafik bog'langan grafik bo'lishi kerak, Kruskal esa uzilgan grafiklarda ham ishlashi mumkin.
• Prim algoritmining vaqt murakkabligi O (V 2 ), Kruskalning vaqt murakkabligi O (logV).