Mustaqil ish-1 Mavzu: Graf daraxtini qurish va murakkablik darajasini baholash usullari Guruh

Graf daraxtini qurish
Grafik daraxtini yaratish uchun siz quyidagi amallarni bajaramiz:
1. Ildiz tugunini tanlang. Ushbu tugun daraxtingizning boshlang'ich nuqtasi bo'ladi.
2. Ildiz tuguniga to'g'ridan-to'g'ri bog'langan bog'langan tugunlar to'plamini tanlang.
Bular ildiz tugunining bolalari bo'ladi.
3. Har bir kichik tugun uchun 2-bosqichni takrorlang, lekin ildiz tugunini va uning
asosiy tugunlarini ulangan tugunlar to'plamidan chiqarib tashlang.
4. Butun daraxtni qurmaguningizcha har bir tugun uchun 3-bosqichni takrorlang.
Grafik daraxtini qurish misoli:
1. Ildiz tugun sifatida A tugunini tanlang.
2. B, C va D tugunlari to'g'ridan-to'g'ri A tuguniga bog'langan. Bular A tugunining
bolalari bo'ladi.
3. B tugunlari uchun E va F tugunlari to'g'ridan-to'g'ri bog'langan, ammo A tugunini va
C va D tugunlarini to'plamdan chiqarib tashlaydi. C tugunlari uchun G tugunlari

---

to'g'ridan-to'g'ri ulanadi, lekin to'plamdan A, B va D tugunlarini istisno qiladi. D
tugunlari uchun H va I tugunlari to'g'ridan-to'g'ri bog'langan, ammo A, B va C
tugunlarini to'plamdan chiqarib tashlaydi.
4. Butun daraxtni qurmaguningizcha har bir tugun uchun 3-bosqichni takrorlang.
Olingan grafik daraxti quyidagicha ko'rinadi:
```
A
/| \
B C D
/| / | \
E F G H I

---

---

---

Men ushbu rasm bilan bog'liq muammomni tasvirlashni boshlayman: bu erda rasm
tavsifini kiriting
Rasmda biz ba'zi nuqtalarni (qora nuqta) ko'rishimiz mumkin. Men qilmoqchi bo'lgan
narsa birinchi navbatda barcha nuqtalarni saqlash va keyin tugun nuqtalarini va uchi
nuqtalarini (qizil nuqta) topishdir. Bundan tashqari, qizil chiziqlar orasidagi
burchaklarni topish uchun bu qizil nuqtalarni to'g'ri chiziqlar bilan (qora nuqtalar
bo'ylab) bog'lash mumkinligini tekshirishim kerak.
Men buni etarlicha aniq tushuntirdimmi yoki yo'qligini bilmayman, lekin men
daraxt/grafikni qo'llashim va qizil nuqtalar ulanganligini tekshirish uchun yo'lni
topishim kerak deb o'yladim.
Asosan, men shunday bir narsa bilan boshladim:
class Point {
public:

---

int x;
int y;
vector
 neighbors;
Point(void);
Point(int x, int y);
}
vector
 allPoints;
Barcha nuqtalarni allPoints vektorida saqlaydigan joy. Har bir nuqta uchun men uning
barcha qo'shnilarini tekshiraman ([x+1,y], [x-1,y], [x+1,y+1], [x-1, y+1], ... ) va ularni
ushbu nuqta uchun qo'shnilar vektorida saqlang.
Keyin, qo'shnilar vektorining o'lchamiga ko'ra, men Nuqta tugun (3 yoki undan ortiq
qo'shni), uchi (1 qo'shni) yoki oddiy bir nuqta (2 qo'shni) ekanligini aniqlayman.
Va bu erda men yo'l topishni qanday amalga oshirishni bilmayman (masalan, uchi
nuqtasidan eng yaqin tugun nuqtasiga yo'l bor-yo'qligini tekshirish uchun) qism keladi.
Bundan tashqari, mening "daraxt" tasvirim yaxshi yoki yo'qligini bilmayman (ehtimol
bunday emas). Shunday qilib, agar kimdir menga xohlagan narsaga erishishimga
yordam bersa, bu ajoyib bo'lar edi.
P.S. Men C++ (va OpenCV) va VS2010 da yozyapman.
Tahrirlash:

---

Bu haqiqiy dasturda shunday ko'rinadi (qizil chiziqlar men tomonidan bo'yoqqa
botiriladi, lekin men erishmoqchi bo'lgan narsam):
Ko'pgina real jarayonlar nosimmetrik bo'lmagan namunaviy kosmik tuzilmalarni o'z
ichiga oladi. Bunday jarayonlarga misollarni ko'pincha sog'liqni saqlash, tibbiyot,
xavflarni tahlil qilish va politsiyada topish mumkin (qarang: Collazo
va boshqalar. (2018)). Bunday nosimmetrikliklar tizimli nol va tizimli mavjudligi
sababli paydo bo'lishi mumkin
boshqa o'zgaruvchi(lar)ni amalga oshirish sharti bilan o'zgaruvchining namunaviy
fazosida etishmayotgan qiymatlar (birgalikda strukturaviy nosimmetrikliklar).
Strukturaviy nol nolni kuzatishni bildiradi
nolga teng bo'lmagan kuzatuvda hisoblash o'zgaruvchisi yoki toifali o'zgaruvchining
toifasi uchun chastotalar
tanlab olish cheklanishidan ko'ra mantiqiy imkonsizlikdir (masalan, kunlar yoki miqdor
past, o'rta,

---

teetotallers tomonidan spirtli ichimliklarni yuqori iste'mol qilish). Strukturaviy
etishmayotgan qiymat - bu kuzatuvlar
yo'qolgan, chunki ular shaxslar/birliklarning bir qismi uchun aniqlanmagan (masalan,
kasallikka chalingan, ammo operatsiya qilinmagan shaxslarning operatsiyadan keyingi
sog'lig'i bilan bog'liq o'zgaruvchilar). Qanday qilib buni ko'rish oson
nosimmetrikliklar kontekstga xos shartli mustaqilliklarni keltirib chiqarishi mumkin,
ular mustaqillikdir.
X y Y|Z = z1, lekin X 6y Y|Z = z2 ko'rinishdagi munosabatlar, bu erda y ehtimollik
mustaqilligini bildiradi va vertikal chiziq o'ng tomonda shartli o'zgaruvchilarni
ko'rsatadi. Aslida, kontekstga xos
Mustaqillik muntazam ravishda ko'plab ilovalarda tabiiy ravishda paydo bo'ladi (Chjan
va Poole, 1999).
Bayes tarmoqlari (BNs) kabi grafik modellar assimetriklikni to'liq tasvirlay olmaydi.
jarayonlar. Ular, birinchi navbatda, bu jihatdan to'sqinlik qiladilar, chunki ular jarayon
tavsifini a ga majburlaydilar
a priori aniqlangan o'zgaruvchilar to'plami. Haqiqatan ham, BN metodologiyalarini
kattalashtirish uchun
muammolar, yaxshi BN dasturiy ta'minot bitta shartli ehtimollik jadvalining qismlarini
nusxalash funktsiyalarini o'z ichiga oladi
1
Shenvi va Smit
boshqasiga. Shunday qilib, BNlar o'zlarining shartli ehtimollik jadvallari ichida
ehtimolliklarni belgilash orqali kontekstga xos mustaqilliklarni bilvosita o'rnatadilar.
Biroq, bu tizimli ma'lumot hech qachon

---

topologiyalarida aniq ifodalangan. Ushbu mustaqilliklarni ochish uchun ularning
standart ko'rinishiga va/yoki xulosa chiqarishga jiddiy o'zgartirishlar kiritish (odatda
qandaydir shakldagi daraxtlar) talab qilinadi.
jarayon (Boutilier va boshq., 1996; Zhang va Poole, 1999; Jabbari va boshq., 2018).
Bundan tashqari, strukturaviy
nollar ham ularning shartli ehtimollik jadvallarida yashiringan.
Chain Voqealar Grafiklari (CEGs) - ehtimollik grafik modellari oilasi, ularning
grafiklari
vakillik strukturaviy nosimmetrikliklar va kontekstga xos shartli mustaqilliklarni aniq
ko'rsatadi
(Collazo va boshq., 2018). CEGlar alohida holat sifatida cheklangan diskret BN sinfini
o'z ichiga oladi (Smit va
Anderson, 2008). Ular voqealar ketma-ketligi orqali jarayonning rivojlanishini
tasvirlash uchun tabiiy va intuitiv ramka ishini ta'minlaydigan voqea daraxtlaridan
qurilgan. Garchi o'lchami bir
hodisalar daraxti jarayonning evolyutsiyasida ishtirok etadigan hodisalar soni bilan
chiziqli ravishda ortadi
katta murakkab jarayonlar uchun noqulay bo'lishi mumkin, ammo ular statistik uchun
osondir
domen ekspertining tabiiy tildagi tavsiflaridan shaffof tarzda chiqaring. Strukturaviy
o'rnatish
Hodisalar daraxti ichidagi nosimmetrikliklar shunchaki tegishli novdani chizmaslik
masalasidir
daraxt (Shenvi va boshq., 2018). Biroq, saqlab qolgan holda, hodisa daraxtining yanada
ixcham vakilligi

---

uning xossalari va shaffofligi maqsadga muvofiqdir. CEG bunday ixcham vakillikni
ta'minlaydi. Shuning uchun
Bu, ayniqsa tibbiyot (Barclay va boshq., 2013), sog'liqni saqlash (Shenvi va boshq.,
2018), sud-tibbiyot kabi asosiy sohalarda sezilarli nosimmetrikliklar ko'rsatadigan
jarayonlar uchun kuchli modellashtirish vositasidir.
(Collazo va boshq., 2018), bu erda mutaxassislar ko'pincha jarayonlarning voqealarga
asoslangan tavsiflarini taklif qilishadi.
CEGni olish uchun voqea daraxti birinchi navbatda uchlarini bo'yash orqali bosqichli
daraxtga aylantiriladi
uning tuzilishidagi simmetriyalarni ifodalaydi. Keyinchalik ta'minlash uchun bosqichli
daraxtning uchlari birlashtiriladi
CEG grafigi ko'rinishida ushbu simmetriyalarning yanada ixcham tasviri. Bunday
transformatsiya natijasida ko'pincha kichikroq cho'qqilar va qirralarning tartibiga ega
bo'lgan ancha sodda grafik paydo bo'ladi.
hosil qiluvchi daraxtga qaraganda. Hodisalar daraxti singari, CEG ham jarayonni
ketma-ketlikda tasvirlaydi
hodisalar va shu tariqa strukturaviy nosimmetrikliklarni grafik tasvirlash qobiliyatini
meros qilib oladi. CEG taqdimoti ayniqsa foydalidir, chunki turli xil yashirin shartli
mustaqilliklar, shu jumladan
daraxtning rang berish naqshlari ichida yashiringan kontekstga xos tabiatni to'g'ridan-
to'g'ri o'qish mumkin
uning topologiyasi kesmalar va nozik kesmalar deb ataladigan hodisalar to'plamidan
foydalangan holda (Smit va Anderson, 2008).
Endi CEG uchun bir nechta tez o'rganish algoritmlari mavjud (Friman va Smit, 2011;
Silander va

---

Leong, 2013 yil; Kouell va Smit, 2014). Ushbu algoritmlarning chiqishi bosqichli
daraxtdir. Sahnalashtirilgan
daraxt odatda ni ifodalashdan oldin ahamiyatsiz bo'lmagan o'zgarishlar ketma-
ketligidan o'tishi kerak
CEG grafigi. Aslida, CEG o'zining bosqichli daraxti bilan o'ziga xos tarzda aniqlanadi
va biz sahnalashtirilganligini ko'rsatamiz
daraxt bo'lishi mumkin