O‘zbekiston Respublikasi Oliy va o‘rta maxsus ta’lim vazirligi Toshkent Axborot Texnalogiyalar Unversiti “ttkt” Fakultiti Aborot xafsizligi (sohalari buyich) Mavzu

O‘zbekiston Respublikasi Oliy va o‘rta maxsus ta’lim vazirligi
Toshkent Axborot Texnalogiyalar Unversiti “TTKT” Fakultiti
Aborot xafsizligi (sohalari buyich)



Mavzu: Ma’lumotlarni xeshlash algoritmlari

212-Guruh talabasi
Bajardi: Ulashev Vohidjon


Tekshirdi: Ibrohimova Z
Samarqand- 2023-yil


Graflarda eng qisqa yo‘lni aniqlash masalalari. Graflarda eng qisqa yo‘lni aniqlash algoritmlari tahlili.


Tabii, graflarda eng qisqa yo‘lni aniqlash masalalari va algoritmlari haqida batafsil gaplashamiz.


1. Breadth-First Search (BFS - Eniqlikning oldinga qo'yilishi):
- BFS, odatda to'g'ri yo'lda yurishni izlash uchun ishlatiladigan oddiy bir qidiruv algoritmi hisoblanadi.
- Bu algoritm bir boshlang'ich tugmani tanlash orqali boshlanadi va kerakli barcha tugmalarni bir-birini tarqatayotgan tartibda tekshiradi.
- BFS, grafdagi eng qisqa yo'li topishda ishlatiladi. Ammo agar grafdagi barcha yo'llar o'zaro teng bo'lsa, BFS eng qisqa yo'lni topishi mumkin emas.


2. Dijkstra's Algorithm:
- Dijkstra algoritmi, grafda eng qisqa yo'li topish uchun odatda ishlatiladi.
- Bu algoritm bir boshlang'ich tugmaning orqali boshlanadi va boshlang'ich tugmaning etrafidagi eng yaqin tugmalarni tanlaydi.
- Tugma va uzunliklarni saqlab olish uchun bir yig'indini va tugmani saqlab olish uchun boshqa bir yig'indini ishlatadi.
- Dijkstra algoritmi, pozitiv bo'lgan grafiklarda ishlaydi va eng qisqa yo'li topishda yaxshi natijalarni ta'minlaydi.


3. Bellman-Ford Algorithm:
- Bellman-Ford algoritmi, eng qisqa yo'li topish uchun qo'llaniladigan algoritmlardan biridir, ammo bu algoritm negativ uzunliklarga ega bo'lgan grafiklarda ham ishlaydi.
- Algoritm boshlang'ich tugma orqali boshlanadi va boshlang'ich tugmaning etrafidagi barcha tugmalarga bo'lgan eng qisqa yo'li aniqlanadi.
- Bellman-Ford algoritmi, negativ dengizlarni aniqlayishi va ularning mavjudligida natijalarni to'g'ri bildirishi mumkin.


4. A* Algorithm:
- A* algoritmi, eng qisqa yo'li topish uchun ishlatiladigan heuristik qidiruv algoritmidir.
- Bu algoritm Dijkstra algoritmasiga o'xshash ravishda ishlaydi, ammo har bir tugma uchun bir bashorat qiymati (heuristik) qo'llanadi.
- Heuristik qiymati, tugmalar orasidagi eng yaqin masofani ifodalaydi.
- A* algoritmi, to'g'ri heuristik funktsiyalardan foydalanilganda yaxshi natijalar berishi mumkin.


Bu algoritmalardan har biri, grafdagi eng qisqa yo'li aniqlash uchun xususiy usullarni taklif etadi. Algoritmani tanlash, grafingizdagi xususiyatlarga, uzunliklarga va talablarga bog'liq bo'ladi.