Shahar transportlariDa optimal yoʻnalishni tanlovchi axborot tizimining mobil naqlini yaratish

TAHLIL VA USLUBIYAT
A. Izlash algoritmlari
Izlash algoritmi izlashda optimal yechimni qanday tanlashni koʻrib chiqadigan algoritmdir [1,2]. Har bir izlash algoritmida maqsad holatiga erishish uchun rivojlanish tugunlari nuqtai nazaridan farq mavjud. Oʻlchovlarni izlash algoritmlari uchun toʻrtta mezon mavjud[2]:
1. Toʻliqlik: algoritmlar albatta yechim topa oladimi?
2. Vaqt murakkabligi: algoritm yechim topish uchun qancha vaqtni oladi?
3. Resurs murakkablik: izlashni amalga oshirish uchun qancha xotira kerak?
4. Optimallik: algoritm eng yaxshi yechimni topa oladimi?
Hatto eng yaxshi izlash algoritmi ham barcha turdagi holatlar yoki muammolar uchun mos boʻla olmaydi. Koʻrib chiqilayotgan masalalarning ehtiyojlariga mos keladigan izlash algoritmlarini tanlash zarur.
Axborotsiz izlash va informatsion izlash yoki evristik izlash boʻlgan tugunni ishlab chiqish usuliga asoslangan ikkita izlash usuli mavjud [3,4,5]. Axborotsiz - bu izlashni joriy holatdan maqsad holatiga erishishga yoʻnaltira oladigan axborotsiz yechim izlaydi, algoritm faqat maqsad holatini aniqlay oladi[1,2,5].
Axborotli izlash - bu eng yaxshi yechimni topish uchun izlash jarayoniga rahbarlik qiladigan davlat makonini izlash muammosini tanlab olish strategiyasidir [1,2,3]. Axborotli izlash koʻpincha evristik izlash deb ham ataladi, chunki maqsadga erishish holatiga erishish uchun tarmoqlarni tanlash qoidalaridan foydalanadi, ehtimol qabul qilingan yoki koʻpincha evristik funksiya deb ataladigan muammoni hal qiladi[4,6,7].


B. A* algoritmi
A* algoritmi dastlabki holatdan boshlab, soʻngra grafik orqali maqsad sari optimal yoʻlni yaratadi. Algoritm axborotlashgan izlash texnikasidan foydalanadigan yoʻlni topish algoritmi sifatida tasniflanadi. A * algoritmi joriy holatning maqsad holatiga evristik funksiyaga ega boʻlgan yoʻl narxini hisoblashdan tashqari, boshlangʻich holatdan hozirgi holatgacha boʻlgan yoʻlning narxini ham hisobga oladi [1]. Shunday qilib, yoʻl olingan boʻlsa va arzonroq boshqa yoʻl mavjud boʻlsa, lekin maqsad holatidan koʻrinadigan pozitsiyani ta’minlaydigan boʻlsa, tanlangan yangi yoʻl shunchalik past boʻladi. Bu algoritm 1-tenglama asosida evristik qiymatni hisoblab chiqadi [1].
f(x) = g (x) + h(x) (1)
Bu yerda: f(x): baholash funksiyasi, g(x): boshlangʻich holatdan hozirgacha x tuguniga chiqarilgan xarajatlar, h(x): x tugunidan maqsadga erishish uchun taxminiy xarajat.
A * algoritmining printsiplari f (x) qiymati eng past boʻlgan tugunni topish orqali boshlangʻich holatdan maqsad tugungacha boʻlgan eng qisqa yoʻlni topishdir. A * izlash jarayonining har bir bosqichida eng yuqori ustuvorlikka ega boʻlgan tugunni tanlanadi. Bu har bir tugunda adekvat boʻlgan f (x) baholash funksiyasini qoʻllash orqali amalga oshiriladi. f (x) qiymati qanchalik past boʻlsa, ustuvorlik shunchalik yuqori. Agar bitta tugun maqsad boʻlsa, toʻxtatiladi. Agar yoʻq boʻlsa, tugunni tanlashni yana bajariladi.


C. Geografik koordinatalar
Xaritada an’anaviy boʻylama (vertikal) va koʻndalang (gorizontal) chiziqlar mavjud boʻlib, ular yerdagi joyning oʻrnini aniqlashga yordam beradi. Uzunlik va kenglik chiziqlari orasidagi kesishma xaritalar koordinatalari deb ataladi. Uzunlik-kenglik koordinatalari tizimi aniqlovchi ikkita komponentdan iborat, xususan:
1. Yuqoridan pastgacha (vertikal) shimolni yerning janubiy qutbi bilan bogʻlaydigan chiziqlar, shuningdek, kenglik deb ham ataladi.
2. Ekvatorga parallel gorizontal chiziq, shuningdek, uzunlik deb ham ataladi. Ikki koordinata orasidagi masofani 2-tenglamadagi kabi [9] Haversine formulasidan foydalanib hisoblanadi.
d=R * c (2)
Bu yerda: d - R birligiga koʻra tanlangan ikki nuqta orasidagi masofa, R - yerning radiusi 6371 (km)[9].
c qiymatini olish uchun 3 tenglamadan foydalanish kerak.

Bu yerda a 4, 5 va 6 tengliklardan aniqlanadi:


Bu yerda Lat1 boshlangich nuqta kengligi, Lat2 maqsad nuqta kengligi

Bu yerda Lon1 boshlangich nuqta uzunligi, Lon2 maqsad nuqta uzunligi