prima deykstra algoritimi

DOCX 32 стр. 159,4 КБ Бесплатная загрузка

32 стр.

FaylHub.uz

Скачать через Telegram

Размер 159,4 КБ

Тип файла DOCX

Страницы 32

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1 / 32

o‘zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti teleradio eshittirish va mobil aloqa fakulteti algoritm va matematik modellashtirish kafedrasi algoritmlarni loyihalash fanidan mustaqil ishi cal 021 (810-21) guruh talabasi bajardi: hamidxonov ahrorxo’ja tekshirdi: begimov o’ktam. toshkent -2023 mavzu: prima deykstra algoritimi. uni vaqt bo'yicha baholash reja: 1. algoritmning maqsadi va tushunchasi haqida tushuntirish 2. deykstra algoritmi qanday ishlaydi? 3.deykstriyaning eng qisqa yo’l algoritmi. 4. primning minimal tejamkor daraxti (mst). 5. prim algoritmi qanday ishlaydi? uni vaqt bo'yicha baholash 6. xulosa 7. foydalanilgan adabiyotlar mundarija: 1. algoritmning maqsadi va tushunchasi haqida tushuntirish………….. 4 2. deykstra algoritmi qanday ishlaydi?................................................ ….. 5 3.deykstriyaning eng qisqa yo’l algoritmi................................................ 6 4. primning minimal tejamkor daraxti (mst)......................................... 17 5. prim algoritmi qanday ishlaydi? .................................................................. 20 6. xulosa …………………………………………………………………... 30 7. foydalanilgan adabiyotlar …………………………………………….. 31 1. algoritmning maqsadi va tushunchasi haqida tushuntirish algoritmning maqsadi, belgilangan vazifani hal qilish uchun qadam-qadam ilgari sotilgan jarayonlarni …

2 / 32

ma'lumotlar yaratilishi kerak va ular o'zaro bog'liq bo'lishi kerak.algoritmlar maqsadga erishishning eng yaxshi usuli bo'lib, ulardan foydalanuvchi tomonidan aniqlanadigan narsalar o'zgartirilib turishi mumkin. algoritmning tushunchasi barcha amaliyotlarimizni yo'lga qo'ydi va ko'proq avtomatlashtirilgan dasturlash jarayoniga erishishimizni ta'minladi. prima-dijkstra algoritmi, bir grafda minimum ostova ag‘lini topish uchun ishlatiladigan bir algoritm hisoblanadi. bu algoritm, grafda eng qisqa yo‘lni topish uchun dijkstra algoritmini va minimum ostova ag‘lini topish uchun prima algoritmini birgalikda qo‘llaydi. algoritm berilgan grafda minimum ostova ag‘lini topishdir. minimum ostova ag‘li, grafning barcha tugallanishlarini o‘z ichiga oladi va barcha tugallanishlar uchun yagona qo‘llanishni yaratadi. bu qo‘llanishlar yordamida, minimum ostova ag‘liga tegishli barcha tugallanishlar uchun eng kam miqdorda bo‘lgan to‘plamni topish mumkin. algoritmning tushunchasi esa, bir nukta orqali grafning boshlang‘ich tugallanishlari va ularning miqdorlarini hisoblashdan iborat. dijkstra algoritmi yordamida, boshlang‘ich nuktadan boshlab qolgan barcha nuktalarga olib boriladi va ulardan eng kam miqdorda bo‘lgan tugallanishni topish uchun ishlatiladi. bu tugallanishlar prima algoritmi yordamida qo‘shiladi …

3 / 32

bo‘lgan tugallanishni topish uchun ishlatiladi. algoritmda har bir tugallanish uchun bo‘shlik miqdorini hisoblash uchun vaqt xarajatlari ishlatiladi. har bir tugallanish uchun bo‘shlik miqdorini aniqlash uchun, boshlang‘ich tugallanish nuktasi orqali qolgan barcha nuktalarga olib boriladi va ulardan eng kam miqdorda bo‘lgan tugallanish tanlanadi. tanlangan tugallanishning miqdori tugallanish nuktasi orqali barcha nuktalarga yetib borish vaqtida aniqlanadi. algoritmda, barcha nuktalarga olib borish uchun grafning to‘g‘ri uzluksiz bo‘lganligini tekshirish uchun dfs yoki bfs kabi qo‘llanmalar ishlatilmaydi. bu sababli dijkstra algoritmi orqali eng qisqa yo‘l topish uchun ishlatiladigan vaqt xarajatlari katta bo‘lmaydi. algoritmdan kutiladigan natijalar, boshlang‘ich tugallanish nuktasidan barcha nuktalarga eng kam miqdorda borish uchun zarur bo‘lgan bo‘shlik miqdorlarini aniqlaydi. bu natijalarga asosan, grafda eng qisqa yo‘l yoki minimum ostova ag‘lini topish mumkin. grafikadagi manba va vertexni berilgan holda, berilgan grafikdagi manbadan vertikalgacha bo'lgan eng qisqa yo'llarni toping. 3.deykstriyaning eng qisqa yo’l algoritmi. dijkstraning algoritmi primning minimal daraxtni qisqartirish algoritmiga juda o'xshaydi . prim's mst …

4 / 32

ami) to'plamini yarating . dastlab, ushbu to'plam bo'sh. 2) kirish grafigidagi barcha uchlarga masofa qiymatini bering. barcha masofa qiymatlarini infinite sifatida boshlang. manba cho'qqisi uchun masofa qiymatini 0 sifatida belgilang, shunda u avval tanlanadi. 3) sptset- da barcha vertikal qismlar mavjud emas ... a) sptset-da bo'lmagan u uchini tanlangva minimal masofa qiymatiga ega. …. b) sptset-ga u qo'shing . …. c) u-ning barcha yon vertikallari masofa qiymatini yangilang. masofa qiymatlarini yangilash uchun barcha qo'shni vertikalar bo'ylab takrorlang. har bir qo'shni vertex uchun v, agar u (manbadan) masofa qiymati va uv qirrasi og'irligi v masofa qiymatidan kichik bo'lsa, v ning masofa qiymatini yangilang.quyidagi misol bilan tushunaylik. o'rnatilgan sptset dastlab bo'sh va vertikal chiziqlarga berilgan masofalar {0, inf, inf, inf, inf, inf, inf, inf}, bu erda inf cheksizdir. endi minimal masofa qiymatiga ega vertexni tanlang. vertex 0 tanlangan, uni sptset-ga qo'shing . shunday qilib sptset {0} bo'ladi. 0-ni sptset- ga qo'shgandan so'ng …

5 / 32

verteksni tanlang (sptset-da emas). vertex 6 tanlangan. endi sptset {0, 1, 7, 6} bo'ladi. 6-sonli qo'shni vertikallarning masofa qiymatlarini yangilang. 5 va 8-vertexlarning masofa qiymati yangilanadi. biz yuqoridagi amallarni sptset berilgan grafikning barcha uchlarini o'z ichiga olguncha takrorlaymiz . va nihoyat, biz quyidagi eng qisqa yo'l daraxti (spt) olamiz. spt tarkibiga kiruvchi uchlari to'plamini ifodalash uchun sptset [] boolean massividan foydalanamiz. agar sptset [v] qiymati to'g'ri bo'lsa, v vertex sptga kiritilgan, aks holda emas. array dist [] barcha vertikallarning eng qisqa masofa qiymatlarini saqlash uchun ishlatiladi. // a c++ program for dijkstra's single source shortest path algorithm. // the program is for adjacency matrix representation of the graph #include #include // number of vertices in the graph #define v 9 // a utility function to find the vertex with minimum distance value, from // the set of vertices not yet included in shortest path tree int mindistance(int dist[], bool sptset[]) …

Хотите читать дальше?

Скачайте все 32 страниц бесплатно через Telegram.

Скачать полный файл

О "prima deykstra algoritimi"

o‘zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti teleradio eshittirish va mobil aloqa fakulteti algoritm va matematik modellashtirish kafedrasi algoritmlarni loyihalash fanidan mustaqil ishi cal 021 (810-21) guruh talabasi bajardi: hamidxonov ahrorxo’ja tekshirdi: begimov o’ktam. toshkent -2023 mavzu: prima deykstra algoritimi. uni vaqt bo'yicha baholash reja: 1. algoritmning maqsadi va tushunchasi haqida tushuntirish 2. deykstra algoritmi qanday ishlaydi? 3.deykstriyaning eng qisqa yo’l algoritmi. 4. primning minimal tejamkor daraxti (mst). 5. prim algoritmi qanday ishlaydi? uni vaqt bo'yicha baholash 6. xulosa 7. foydalanilgan adabiyotlar mundarija: 1. algoritmning maqsadi va tushunchasi haqida tushuntir...

Этот файл содержит 32 стр. в формате DOCX (159,4 КБ). Чтобы скачать "prima deykstra algoritimi", нажмите кнопку Telegram слева.

Теги: prima deykstra algoritimi DOCX 32 стр. Бесплатная загрузка Telegram