|
Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari
|
| bet | 4/4 | | Sana | 25.11.2022 | | Hajmi | 128.09 Kb. | | #31757 |
Bog'liq Mamasoiyev Farxod Diskret tuzilmalari maruza[1]Bulkhead algoritmi-grafikani chetlab o'tish algoritmi, bu mumkin bo'lgan yo'llarning ketma-ket izlanishiga asoslangan.
Qisqa natijalar:
Bugungi kunda eng qisqa yo'lni topish dolzarb vazifadir.
Graflarda eng qisqa yo'lni topishning eng samarali algoritmlari Dijkstra algoritmi, Floyd algoritmi va Bulkhead algoritmlarini o'z ichiga oladi. Ushbu algoritmlar juda oz sonli vertikalar uchun samarali.
Dijkstra algoritmini amalga oshirishda dastlabki tepadan eng qisqa yo'llar allaqachon ma'lum bo'lgan ko'plab vertikalar qurilgan. Quyidagi qadamlar optimal yo'llarning uzunligini saqlab, mavjud bo'lgan to'siqlarga bir tepalikka qo'shilishga asoslangan.
Dijkstra algoritmining murakkabligi vertikani topish usuliga, shuningdek, ko'plab turg'un cho'qqilarni saqlash usuli va uzunliklarni yangilash usuliga bog'liq.
Floyd usuli, qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan eng qisqa yo'l boshqa eng qisqa yo'llardan iboratligiga asoslanadi.
Agar grafik qo'shni matritsasi bilan ifodalangan bo'lsa, Floyd algoritmining ishlash vaqti o(n3) tartibiga ega.
Bulkhead algoritmlar optimal yechim topish uchun algoritmlar bor.
To'lqin algoritmi kenglikdagi qidiruvga asoslangan va ikki bosqichdan iborat: to'lqin tarqalishi va teskari harakat.
Keng qidirish usuli bilan qidirish, qaytib kelish bilan solishtirganda, ma'lumotni saqlash uchun ko'proq yordamchi xotira talab qiladi, biroq u tezroq ishlaydi, chunki bir xil tepalikka bir martadan ko'proq tashrif buyurilmaydi.
Xulosa:
Men ushbu Mustaqil ishini bajarish mobaynida eng qisqa yo'llarini topish algoritmlarini bu yo’llar kimlar tomonida oylab topilganini bu yo’llarni nima sababdan oylab topilganini bu yo’llarni turlarini o’rgandim.
Foydalanilgan adabiyotlar:
Абрамов С.А. Лекции о сложности алгоритмов.- М.: МЦНМО, 2009.- 256 с.
Дональд Кнут Искусство программирования, том 1. Основные алгоритмы— 3-е изд. — М.: «Вильямс», 2006. — С. 720.
Кнут В. Искусство программирования. Т.3. Сортировка и поиск. – 2-е изд. - Издательский дом “Вильямс”, 2000.
Вирт Н. Алгоритмы и структуры данных. Пер. с англ. – М.: Мир, 1989. – 360.
Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992.
|
| |
