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