10.1. Minimal qoldiq daraxtlar. Minimal oraliq daraxti (MST) yoki minimal og‘irlik oralig‘i daraxti bir-biriga bog‘langan, chekka og‘irligi bo‘lgan yo‘naltirilmagan grafikning chekkalarining kichik to‘plami bo‘lib, u barcha cho‘qqilarni bir-biriga bog‘laydi, hech qanday aylanishlarsiz va chekkaning mumkin bo‘lgan minimal umumiy og‘irligi bilan.[1] Ya'ni, u chekka og'irliklari yig'indisi imkon qadar kichik bo'lgan yoyilgan daraxtdir.[2] Umuman olganda, har qanday chekka og'irlikdagi yo'naltirilmagan grafik (ulanish shart emas) minimal o'rmonga ega bo'lib, u bog'langan komponentlar uchun minimal kenglikdagi daraxtlarning birlashmasi hisoblanadi.
Minimal kenglikdagi daraxtlar uchun ko'plab foydalanish holatlari mavjud. Masalan, telekommunikatsiya kompaniyasi yangi mahallada kabel yotqizmoqchi. Agar kabelni faqat ma'lum yo'llar (masalan, yo'llar) bo'ylab ko'mib tashlash cheklangan bo'lsa, u holda bu yo'llar bilan bog'langan nuqtalarni (masalan, uylar) o'z ichiga olgan grafik mavjud bo'ladi. Ba'zi yo'llar qimmatroq bo'lishi mumkin, chunki ular uzunroq yoki kabelni chuqurroq ko'mishni talab qiladi; bu yo'llar kattaroq og'irlikdagi qirralar bilan ifodalanadi. Valyuta chekka og'irligi uchun maqbul birlikdir - uchburchak tengsizligi kabi oddiy geometriya qoidalariga bo'ysunish uchun chekka uzunliklariga hech qanday talab yo'q. Ushbu grafik uchun chiziqli daraxt hech qanday tsiklga ega bo'lmagan, lekin baribir har bir uyni bog'laydigan yo'llarning kichik to'plami bo'ladi; bir nechta keng tarqalgan daraxtlar bo'lishi mumkin. Minimal kenglikdagi daraxt eng kam umumiy xarajatga ega bo'lib, kabelni yotqizish uchun eng arzon yo'lni ifodalaydi.
7.1 Ochko’z algoritmlar.
Ochko'z algoritm - bu hozirgi vaqtda mavjud bo'lgan eng yaxshi variantni tanlash orqali muammoni hal qilish uchun yondashuv. Hozirgi eng yaxshi natija umumiy optimal natijaga olib keladimi, tashvishlanmang.Tanlov noto'g'ri bo'lsa ham, algoritm hech qachon oldingi qarorni o'zgartirmaydi. U yuqoridan pastga yondashuvda ishlaydi.Ushbu algoritm barcha muammolar uchun eng yaxshi natijani bermasligi mumkin. Buning sababi shundaki, u har doim global eng yaxshi natijaga erishish uchun mahalliy eng yaxshi tanlovga boradi.Biroq, agar muammo quyidagi xususiyatlarga ega bo'lsa, algoritmni har qanday muammo bilan ishlatish mumkinligini aniqlashimiz mumkin:
1. Greedy Choice mulki
Agar tanlangan oldingi bosqichlarni qayta ko'rib chiqmasdan, har bir bosqichda eng yaxshi tanlovni tanlash orqali muammoning optimal echimini topish mumkin bo'lsa, muammoni ochko'zlik bilan hal qilish mumkin. Bu xususiyat ochko'z tanlov mulki deb ataladi.
2. Optimal quyi tuzilma
Agar muammoning optimal umumiy yechimi uning kichik muammolarining optimal yechimiga mos kelsa, u holda muammoni ochko'z yondashuv yordamida hal qilish mumkin. Bu xususiyat optimal pastki tuzilma deb ataladi.
Ochko'zlik yondashuvining afzalliklari
Algoritmni tasvirlash osonroq.
Bu algoritm boshqa algoritmlarga qaraganda yaxshiroq ishlashi mumkin (lekin hamma hollarda emas).
