Mavzu: Graf daraxtini qurish va murakkablik darajasini baholash usullari



Download 0,79 Mb.
bet3/4
Sana03.05.2023
Hajmi0,79 Mb.
#934724
1   2   3   4
Bog'liq
Algaritm loyihalash

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.767doi: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 yangiliklari33 (2): 34–47. CiteSeerX 10.1.1.172.1005doi:10.1145/564585.564599.

  10. William I. Gasarch"The Second P=?NP poll" (PDF). SIGACT yangiliklari. 74.


Download 0,79 Mb.

Do'stlaringiz bilan baham:
1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish