Algoritmlarni loyhalash ”fanidan mustaqil ishi qabullagan: ass. M. A. Artikbayev Bajargan: J. M. Sadullayev Nukus-2024 Mavzu: Xoffman daraxtlari. Reja

Download 118,78 Kb.
bet	1/5
Sana	16.05.2024
Hajmi	118,78 Kb.
	#238888

1 2 3 4 5

Bog'liq
Sadullayev Javlonbek Algaritmlarni loyhalash

Algoritmlarni loyhalash ”fanidan MUSTAQIL ISHI Qabullagan: ass.M.A.Artikbayev Bajargan: J.M.Sadullayev
Xoffman daraxtlari.

O‘ZBEKISTAN RESPUBLIKASI RAQAMLI TEXNOLOGIYALARI
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALAR UNIVERSITETI NUKUS FILIALI
“Kompyuter injiniring” fakulteti Kompyuter Injiniringi yo‘nalishi
3-kurus 1001-21 guruh (Sirtqi) talabasi
Sadullayev Javlonbekning
“Algoritmlarni loyhalash ”fanidan

MUSTAQIL ISHI

Qabullagan: ass.M.A.Artikbayev Bajargan: J.M.Sadullayev

Nukus-2024
Mavzu: Xoffman daraxtlari.
Reja:
1.Xoffman daraxtlari.
2. Kruskal Algoritmi.
3. Prima algoritmi.
4.Xulosa

Xoffman daraxtlari. Bizga ma’lumki, hozirda aholi punktlari orasidagi yo`llarni, aloqa tarmoqlari kanallarini, suv, gaz uzatish va kanalizasiya quvurlarini loyixalashda axboro tyoki moddiy resurslarni uzatish harajatlari bilan bog`liq masalalar yuzaga keladi. Bunday masalalarni matematik modellashtirishda graflar nazariyasidan foydalanish va matematik modellar bo`yicha eng yaxshi variantini tahlil qilish va optimal variantlarini tanlash mumkin bo`ladi. Ushbu yondashuvning qulayligi shundaki, biz masalaning fizik parametrlariga vaqtincha e’tibor bermasdan turib, matematik masalani yechishimiz va shundan so`ng dastlabki masalaga qaytib, olingan natijalarini berilgan masalaga mos ravishda tahlil qilishimiz mumkin.
Bizga bog`langan, yo`naltirilmagan graf berilgan bo`lib, uning qirralari ma’lum vaznlarga ega bo`lsin. Vaznlar - bu shunday sonlarki, ular berilgan qirralarning chekka uchlari orasidagi masofasini bildiradi, bu qirra bo`ylab xarakatlanishda transport xarajatlarini yoki boshqa xarajatlarni anglatadi. “Xasisalgoritmlar” nomi bilan birlashtirilgan algoritmlar grafning shunday A va D uchlari orasidagi marshrutni (yo`nalishni) topishga qaratilganki, u eng arzon (engkamxarajatli) bo`lishi kerak. Tabiiyki, bunday masalalarni yechishda biz avval A va D uchlari orasidagi barcha mumkin bo`lgan yo`nalishlarni aniqlab, shundan so`ng ushbu yo`nalishlarni eng kam xarajatliligin itanlaymiz.
Ushbu turdagi ma’lum masalalardan biri “kommivoyajer masalasi” bo`ladi. Agar biror grafni tasavvur qilsak va uning uchlari qaysidir tashkilotning bo`limlarini va qirralari esa shu bo`limlar orasidagi yo`lini anglatsa,u xolda kommivoyajer–ushbu tashkilotning xodimi, hamma bo`limlarni aylanib chiqib, yana o`zining idorasiga qaytishi kerak bo`ladi. Bunda u eng kam xarajatli yo`nalishni tanlashi kerak bo`ladi. Boshqacha qilib aytganda kommivoyajer grafda eng kam xarajatli Gamilton siklini tanlashi kerak.
Shunga o`xshash ko`plab masalalar biror kommunikasiya tarmoqlari bilan bog`liq graf uchun ham vujudga kelishi mumkin. Shuning uchun dastlabki ishlanmalarni oldindan xozirlab qo`yish maqsadga muvofiq bo`lib, ular asosida masala yechimi tezlashib boradi. Buning uchun barilgan graf asosida eng arzon (kamxarajatli) graf qurilib, bu graf ostov daraxti deyiladi. Keyinroq ko`ramizki, bu daraxt minimal marshrutlar topishda effektiv vosita bo`ladi. Ostov daraxti qurish usullarining birini tasvirlashga o`tamiz.

Download 118,78 Kb.

1 2 3 4 5

Download 118,78 Kb.