|
Маvzu: Grаflаrdа eng qisqа yo`l mаsаlаsi
|
| Sana | 07.03.2024 | | Hajmi | 286.45 Kb. | | #168528 |
Bog'liq Grafik Mustaqil ish тема, pirls-xalqaro-tadqiqoti, Bеta-yemirilish turlari, Документ, LABORATORIYA ISHI №3, Gidroelektrostansiyalar uslubiy qo\'llanma sirtqi23, Bolalar adabiyoti fani hamda uning maqsad va vazifalari, BAYONNOMA O\'RNAK, 32, 1, File, 653216, evolyucion, HARF, tolalarning-turlari Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti Urganch filiali Telekommunikatsiya texnologiyalari yunalishi 972-21 guruh Maʼlumotlar tuzilmasi va algoritmlar fanidan Mustaqil ish
Topshirdi: Normuminov.M Qabul qildi: Qutliyev.S
Маvzu: Graflarda еng qisqa yo'lni aniqlashning Deykstra algoritmlari. REJA - 1.1. Masalaning qo`yilishi.
- 1.2. Masalani yechish algoritmi.
- 1.3. Deykstra algoritmi asosida eng qisqa yo`lni aniqlash.
Tayanch iboralar Eng qisqa yo`l, Deykstra algoritmi, doimiy belgi, boshlang`ich qiymat, yo`l, masofa, tugun, yoy, yoy vazni.
Graflar ixtiyoriy sistemaning topologiyasini ko`rish imkonini beradi. Graflar nazariyasi asosida turli nazariy va amaliy masalalarni yеchish mumkin. Amaliy masalalardan biri 2 ta tugun va tugunlar orasidagi eng qisqa yo`lni topish masalasidir. Bunda bir necha tugunlar va yoylardan iborat graf berilgan bo`ladi. Yoylarning vazni matritsa shaklida quyidagicha beriladi:
Ixtiyoriy 2 tugun orasidagi eng qisqa yo`lni topish masalasini yеchishni turli usullari mavjud. Bularga barcha
yo`llarni bir chekkadan qarab chiqish (prostoy), optimallashning Bellman prinsipi, va
Deykstra usullari
kiradi. Ulardan eng samaralisi Deykstra usulidir. Bu usul
belgilar qo`yishga bo`lgan musbat
graflarning tugunlariga vaqtinchalik asoslangandir. Bunda yoylarning vazni sonlardan iborat bo`ladi.
Masalani yеchish algoritmi.
Deykstra algoritmi quyidagi bosqichlardan iborat bo`ladi:
- Graf tugunlariga qonuniyatga ko`ra
keyinchalik
doimiy
ma’lum belgiga
vaqtinchalik
belgilashlar
almashtiriladigan qo`yiladi:
- Grafning boshlang`ich tuguniga 0 qiymat, qolganlariga esa vaqtinchalik cheksiz belgisi qo`yiladi, ya’ni:
Shu bilan birga quyidagi belgilashlardan ham foydalanamiz:
Yuqorida bajarilgan vaqtinchalik belgilashlardan eng kichigi tanlab olinib doimiy belgi etib belgilanadi. Bu holat har bitta tugunning doimiy belgisi qo`yilguniga qadar davom ettiriladi. Bajarilayotgan har bitta qadamda albatta bitta tugun doimiy belgi oladi. Navbatdagi qadam doimiy belgi olgan tugundan davom etadi. Keyingi tugunlar to`plamini aniqlashda qaralayotgan tugundan chiqayotgan yoylar olinadi. Bunda berilgan misolda nechta tugun bo`lsa, qadamlar soni ham shuncha bo`ladi. Har qadamda har bitta holat natijasi jadvalga qayd qilib boriladi.
Formula yordamida hisoblanib olingan natijalarni solishtirishda yuqoridagi qadamlarda vaqtinchalik belgi olgan tugunlarni ham e’tiborga olish kerak bo`ladi. Jadval quyidagi tartibda tuzib olinadi: Jadvalning qatorlariga qadamlar ketma- ketligi, ustunlarga esa berilgan misoldagi barcha tugunlar nomi, oxirgi ustundan bitta oldingi ustunga doimiy belgi olgan tugun nomi, oxirgi ustunga esa belgi olgan (shu qadam uchun) tugunning kattaligi kiritiladi. Jadvaldagi ustunlar va qatorlar soni berilgan misoldagi tugunlar sonidan kelib chiqadi.
olgan tugunlar ketma-ketligi va kattaliklar
Jadvalning oxirgi ikkita ustunidagi doimiy belgi
eng
qisqa yo`l ni beradi.
tugungacha
Quyida berilgan grafdagi tugundan
bo`lgan eng qisqa yo`lni toping.
Algoritmni bajarish tartibi Foydalaniladigan adabiyotlar - Siddiqov I.H., Xalmatov D.A., Hushnazarova D.R.
Tizimlar nazariyasi. Darslik. Toshkent, 2020 yil.
- Певзнер Л.Д., Чураков Е.П. Математические основы теории систем. –М.: Издательство: Высшая школа, 2009.
- Павлов С.Н. Теория систем и системный анализ. - Томск: ТМЦДО, 2013. - 134 с.
- Niklas Luxmann, Introduction to systems theory. Polity, 2012.
- Kamran Iqbal. Fundamental Engineering
Optimization Methods. 1 st edition. ©2013.
- Качала В.В. Основы теории систем и системного
анализа. –М.: Изд-во: Горячая Линия - Телеком,
2007.
E’TIBORINGIZ UCHUN RAHMAT!
|
| |
