Mavzu: Graf daraxtini qurish va murakkablik darajasini baholash usullari

Dasturi

Grafik daraxtini yaratishda ushbu sinfdan foydalanish uchun siz GraphTree sinfining yangi namunasini yaratishingiz, add_node() usuli yordamida tugunlarni yaratishingiz va add_node() ga birinchi argument sifatida ota-tugunni o'tkazish orqali ularni bir-biriga bog'lashingiz mumkin.
Yuqoridagi kod yordamida oddiy grafik daraxtini qanday yaratishingiz mumkinligiga misol:

Ushbu misolda biz 0 qiymatiga ega ildiz tugunli daraxt va mos ravishda 1 va 2 qiymatli ikkita tugunli tugunni yaratdik. 2-tugunda 3 va 4 qiymatlari bo'lgan ikkita tugun mavjud. Kattaroq daraxt tuzilishini yaratish uchun shu tarzda daraxtga tugunlarni qo'shishni davom ettirishingiz mumkin.
Metod1
Metod2
Metod3
plot_tree sklearn.tree modulidagi funktsiya bo'lib, qaror daraxtini chizish uchun ishlatilishi mumkin. Ko'rsatilgan namunalar soni mavjud bo'lishi mumkin bo'lgan har qanday sample_weights bilan o'lchanadi. Vizualizatsiya avtomatik ravishda eksa o'lchamiga mos keladi. Renderlash1 hajmini boshqarish uchun plt.figure ning figsize yoki dpi argumentlaridan foydalanishingiz mumkin.

Mana plot_tree dan qanday foydalanishga misol:

Python-da igraph kutubxonasi yordamida daraxt grafigini yaratish misoli:

Ushbu kod 25 ta burchakli daraxt yaratadi va har bir tepada 2 ta bola bor. Daraxt grafigini qurishning murakkabligi ishlatiladigan maxsus algoritmga va kiritilgan ma'lumotlarning hajmiga bog'liq. Bunday holda, daraxtni qurishning murakkabligi O (n), bu erda n - uchlari soni.

Xulosa

Grafik daraxtini qurish murakkab tizimni ierarxik tuzilma sifatida ifodalashni o'z ichiga oladi, bu erda har bir komponent tugun va ular orasidagi bog'lanishlar qirralardir. Grafik daraxtini qurishning turli usullari mavjud, jumladan, yuqoridan pastga, pastdan yuqoriga va ierarxik klasterlash. Grafik daraxtidagi murakkablik darajasini uning chuqurligini, daraja taqsimotini va klasterlash koeffitsientini o'lchash orqali baholash mumkin. Bundan tashqari, markazlashtirilganlik va modullik kabi tarmoq choralari grafik daraxtining tuzilishi va murakkabligi haqida tushuncha berishi mumkin. Grafik daraxtini yaratish usullarini tushunish va uning murakkablik darajasini baholash ijtimoiy tarmoqlar, biologik tizimlar va transport tarmoqlari kabi murakkab tizimlarni tahlil qilish uchun muhimdir.

Foydalanilgan adabiyotlar

1. 
   R. E. Ladner "On the structure of polynomial time reducibility," ACM jurnali 22, pp. 151–171, 1975. Corollary 1.1. ACM site.
   
2. 
   Fortnow, Lance (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ: Princeton University Press. ISBN 9780691156491.
   
3. 
   Kuk, Stiven (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. 151-158 betlar.
   
4. 
   L. A. Levin (1973). "Универсальные задачи перебора" (rus tilida). 9 (3) (Problems of Information Transmission ed.): 115–116.
   
5. 
   Fortnov, Lans (2009). "The status of the P ga qarshi NP muammo " (PDF). ACM aloqalari. 52 (9): 78–86. CiteSeerX 10.1.1.156.767. doi:10.1145/1562164.1562186. Arxivlandi asl nusxasi (PDF) 2011 yil 24 fevralda. Olingan 26 yanvar 2010.
   
6. 
   NSA (2012). "Letters from John Nash" (PDF).
   
7. 
   Hartmanis, Juris. "Gödel, von Neumann, and the P = NP muammo " (PDF). Nazariy kompyuter fanlari bo'yicha Evropa assotsiatsiyasining Axborotnomasi. 38: 101–107.
   
8. 
   Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.
   
9. 
   William I. Gasarch (Iyun 2002). " P=?NP poll" (PDF). SIGACT yangiliklari. 33 (2): 34–47. CiteSeerX 10.1.1.172.1005. doi:10.1145/564585.564599.
   
10. 
    William I. Gasarch. "The Second P=?NP poll" (PDF). SIGACT yangiliklari. 74.