eng qisqa yo'lni topish algoritmlari

PPTX 41 стр. 2,4 МБ Бесплатная загрузка

41 стр.

FaylHub.uz

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

Размер 2,4 МБ

Тип файла PPTX

Страницы 41

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

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

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

1 / 41

презентация powerpoint eng qisqa yo‘lni topish algoritmlari. dijskrta algoritmi. ford-bellman algoritmi. vaznli graf vaznli graf - bu shunday graf, barcha qirralar vaznga (qiymat) ega bo‘lgan grafdir. qo‘shnilik matrisasi (vazn uchun) a b c d e f a 0 1 ∞ ∞ ∞ 2 b 1 0 5 1 ∞ ∞ c 3 5 0 2 1 ∞ d ∞ 1 2 0 4 ∞ e ∞ ∞ 1 4 0 5 f 2 ∞ ∞ ∞ 5 0 vaznli graf пусть дан граф g дугам которого приписаны веса (стоимости), задаваемые матрицей c = [cij]. элементы cij матрицы весов с могут быть положительными, отрицательными или нулями. для упрощения и наглядности в нашей лекции мы будем рассматривать матрицы весов содержащие только положительные элементы. 2 vaznli grafga oid misollar 3 qisqa yo‘lni topish masalasi eng qisqa yo‘lni topish masalasi: berilgan boshlang'ich tugun s ϵ x dan yakuniy t ϵ x tugungacha bo‘lgan eng …

2 / 41

nazariyasining asosiy vositalaridir. ular bizga graf tugunlari orasidagi yo‘llarni topishga imkon beradi, jumladan tarmoqlarni marshrutlash, robotlar harakatini rejalashtirish, transport marshrutini optimallashtirish va boshqalar kabi turli ilovalarda foydalidir. kenglik bo’yicha qidirish(bfs) algoritmi chuqurlik bo’yicha qidirish (dfs) algoritmi dijkstra algoritmi algoritm a* bellman-ford algoritmi floyd-uorshall algoritmi li algoritmi (to'lqinlarni qidirish algoritmi) iddfs (iterativ deepening depth-first search) algoritmi поиск пути на графе. нам поставлена следующая задача. у нас есть непустой граф g=(v,e). это множество вершин (v) и множество связей между ними (e). нам требуется найти путь между вершинами s=s1 и t=s8 графа (s не совпадает с t). этот путь должен содержать минимальное количество промежуточных вершин (ребер). т.е. путь должен быть оптимальным. 5 qisqa yo‘lni topishning eng mashhur algoritmlari quyidagilar: dekstra algoritmi bellman-ford algoritmi tartiblash algoritmlari to‘lqin algoritmi. указанные алгоритмы легко выполняются при малом количестве вершин в графе. при увеличении их количества задача поиска кратчайшего пути усложняется. 6 edsger dijkstra edsger dijkstra - gollandiyalik …

3 / 41

katta ahamiyatga ega hisoblanadi. u turli sohalarda, jumladan, telekommunikatsiya, transport, logistika, ma'lumotlarni tahlil qilish va boshqa ko‘plab sohalarda qo‘llaniladi. dijkstra o‘z maqolasini nashr etganidan beri ushbu algoritmning ko‘plab modifikatsiyalari ishlab chiqildi va graflardagi eng qisqa yo‘lni topish uchun ko‘plab boshqa algoritmlar yaratildi. dijkstra algoritmi 1-qadam. birinchi tugundan boshqa barcha tugunlarga cheksizlikka teng vazn, birinchi tugunga esa 0 qiymat qo‘yiladi. 2-qadam. barcha tugunlar tanlanmagan holatda bo‘ladi. 3-qadam. birinchi tugun joriy tanlangan deb e'lon qilinadi. 4-qadam. barcha tanlanmagan tugunlarning vazni formula bo‘yicha qayta hisoblab chiqiladi: w(v) - tanlanmagan v tugunning eski vazni, w(u) - joriy tugun u ning vazni, w(u, v) - joriy tugun u bilan tanlanmagan v tugunni bog'lovchi qirraning vazni. so’ngra tanlanmagan v tugunning vazni qayta hisoblashdan keyin eski vazndan minimal qiymat sifatida aniqlanadi w(v) va joriy tugun w(u) vazni va w(u, v) qirraning vazni yig'indisi. yangi_vazn(v) = min(w(v), w(u) + w(u, v)) 5-qadam. tanlanmagan tugunlar orasida eng kam vazndagi …

4 / 41

горитм считает для каждой вершины маршрут, и, если он оказывается кратчайшим, выделяет вершину. весом данной вершины становится вес пути. для всех соседей данной вершины алгоритм также рассчитывает вес, при этом ни при каких условиях не выделяя их. алгоритм заканчивает свою работу, дойдя до конечной вершины, и весом кратчайшего пути становится вес конечной вершины. 9 formal tavsif manfiy vaznga ega bo‘lmagan hamda sirtmoqsiz vaznli yo‘naltirilgan graf g(x,e) berilgan bo’lishi kerak. grafning (g) ba'zi s tugunlaridan ushbu grafning oxirgi t tuguniga (yoki barcha boshqa tutunlariga) eng qisqa yo‘llarni toppish kerak. no formal tavsif x ning har bir tuguniga belgi beriladi - bu tugundan boshlang'ich tugungacha bo‘lgan minimal ma'lum masofa. algoritm bosqichma-bosqich ishlaydi - har bir bosqichda u bitta tugunga "tashrif buyuradi" va belgilarni qisqartirishga harakat qiladi. algoritm barcha tugunlarga tashrif buyurilgandan so‘ng tugaydi. misol x1 tugundan qolgan barcha tugunlargacha bo‘lgan eng qisqa masofalarni toping. рассмотрим выполнение алгоритма на примере графа, показанного на …

5 / 41

ую, то есть 0 + 7 = 7. это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7. аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й. 14 все соседи вершины 1 проверены. текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал э. дейкстра). вычеркнем её из графа, чтобы отметить, что эта вершина посещена. второй шаг. шаг алгоритма повторяется. снова находим «ближайшую» из непосещенных вершин. это вершина 2 с меткой 7. снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. соседями вершины 2 являются вершины 1, 3 и 4. 15 первый (по порядку) сосед вершины 2 — вершина 1. но она уже посещена, поэтому с 1-й вершиной ничего не делаем. следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не …

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

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

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

О "eng qisqa yo'lni topish algoritmlari"

презентация powerpoint eng qisqa yo‘lni topish algoritmlari. dijskrta algoritmi. ford-bellman algoritmi. vaznli graf vaznli graf - bu shunday graf, barcha qirralar vaznga (qiymat) ega bo‘lgan grafdir. qo‘shnilik matrisasi (vazn uchun) a b c d e f a 0 1 ∞ ∞ ∞ 2 b 1 0 5 1 ∞ ∞ c 3 5 0 2 1 ∞ d ∞ 1 2 0 4 ∞ e ∞ ∞ 1 4 0 5 f 2 ∞ ∞ ∞ 5 0 vaznli graf пусть дан граф g дугам которого приписаны веса (стоимости), задаваемые матрицей c = [cij]. элементы cij матрицы весов с могут быть положительными, отрицательными или нулями. для упрощения и наглядности в нашей лекции мы будем рассматривать матрицы весов содержащие только положительные …

Этот файл содержит 41 стр. в формате PPTX (2,4 МБ). Чтобы скачать "eng qisqa yo'lni topish algoritmlari", нажмите кнопку Telegram слева.

Теги: eng qisqa yo'lni topish algorit… PPTX 41 стр. Бесплатная загрузка Telegram