Mavzu: Bog‘langan graflarga marshrutlar, ularni narxi bo‘yicha baholash. “Xasis” algoritmlar. Eng qisqa marshrutni aniqlash algoritmi. Uni variantlar soni bo`yicha hajmini baholash. Maqsad



Download 157,85 Kb.
bet1/3
Sana03.05.2023
Hajmi157,85 Kb.
#934915
  1   2   3
Bog'liq
12-амалий иш (1)


12-Amaliy ish
Mavzu: Bog‘langan graflarga marshrutlar, ularni narxi bo‘yicha baholash. “Xasis” algoritmlar. Eng qisqa marshrutni aniqlash algoritmi. Uni variantlar soni bo`yicha hajmini baholash.
Maqsad: Talabalar graf uchun minimal narxli daraxtlar skeletini qurish algoritmini o’rganishi, Kruskal va Primo algoritmlarini bilan ishlashni o‘rganishi, bu algoritmlar haqida bilim va ko‘nikmalarga ega bo‘lishi hamda mustaqil masalalar yechishi va shu masalaga mos algoritmlar qura olishi kerak.
Amaliy ishini bajarish uchun zarur jihozlar. Zarur dasturiy ta’minot (C++ dasturlash tili kompilyatori, matn muharriri) o‘rnatilgan personal kompyuter, amaliy ishini bajarish bo‘yicha (ushbu) uslubiy ko‘rsatma
Zarur nazariy ma’lumotlar.
Kruskal algoritmi.
Ushbu algoritm 1956 yili Kruskal tomonidan ishlab chiqilgan. Faraz qilamiz, V = {1, 2, .... n} tugunlar to‘plamidan iborat va E qirralar to‘plamida aniqlangan s narx funksiyasi bilan berilgan G=(V, E) bog‘langan graf bo‘lsin. Kruskal algoritmida G graf uchun minimal narxli daraxtlar skeletini qurish G grafning faqat n ta tugunlaridan tashkil topgan va qirralari bo‘lmagan T=(V, ø) grafdan boshlanadi. Shunday qilib, har bir tugun bog‘langan (o‘zi-o‘zi bilan) komponent hisoblanadi. Algoritm bajarilishi vaqtida bog‘langan komponentlar naboriga ega bo‘lamiz, asta-sekin birlashtirib daraxtlar skeletini tashkillashtiramiz.
Asta-sekin o‘suvchi bog‘langan komponentlarni qurishda E to‘plamdan qirralar ularning narxi o‘sishi tartibida navbatma-navbat tekshiriladi. Agar navbatdagi qirra turli komponentlardagi ikkita tugunni birlashtirsa, u holda bu qirra T grafga qo‘shiladi. Agar bu qirra bitta komponentning ikkita tugunini birlashtirsa, u tashlab yuboriladi, chunki uning bog‘langan komponentga qo‘shilishi sikl hosil bo‘lishiga olib keladi. G grafning barcha tugunlari bitta komponentga tegishli bo‘lsa, T minimal narxli daraxtlar skeletini qurish bu graf uchun tugaydi.
Primo algoritmi
Ushbu algoritm dastlab 1930 yilda chesh matematigi Voysex Yarnik tomonidan taklif etilgan. Keyin Robert Primo tomonidan 1957 yilda qayta ko’rib chiqilgan va ulardan tashqari E. Deykstra tomonidan 1959 yilda ishlab chiqilgan.
Kruskal algoritm "ochko'z" algoritm anglatadi. o'sha mohiyati - har qadamda eng yuqori g'alaba. Har doim emas, "ochko'z" algoritmlarni muammo uchun eng yaxshi yechim beradi. a nazariyasi aniq vazifalar, ularning qo'llash ular optimal yechim berish, deb ko'rsatib, bor. Bu matroids nazariyasi hisoblanadi. Kruskal algoritmi shu kabi muammolari bilan bog'liq.
Algoritm kirishiga yo’naltirilmagan og’irlikka ega bo’lgan graf uzatiladi.

  1. Boshida istalgan tugun olinadi va unga tegishli bo’lgan eng kam vaznga ega insident yoy topiladi. Topilgan yoy va unga tegishli tugunlar daraxtni shakllantira boshlaydi.

  2. Keyin bir uchi bilan daraxtga tegishli bo’lgan tugunlariga tutashgan va ikkinchi uchi esa tutashmagan boshqa yoylar xam tekshiriladi. Ulardan og’irligi kami tanlanadi.

  3. Xar bir qadamdagi yoy daraxtga qo’shilib boraveradi. Daraxtning balandligi xam 1 taga oshib boraveradi. Grafning barcha tugunlari ko’rib chiqilmaguncha algoritm davom etaveradi.

Algoritm natijasi bo’lib minimal narxli daraxt skeleti xisoblanadi. E’tibor qaratish lozimki, minimal narxli daraxtlarni hosil qilishda xalqa paydo bo’lishiga yo’l qo’ymaslik kerak.

Amaliy topshiriqlari va


ish davomida ishlab chiqiladigan dasturning to‘liq namunasi.

Download 157,85 Kb.

Do'stlaringiz bilan baham:
  1   2   3




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