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

ALGORITMLAR VA AMALGA OSHIRISH
A* optimal yoʻnalishni topish uchun evristik algoritm
Ushbu tadqiqotning asosiy muammosi – Toshkent shahar mintaqasidagi foydalanuvchilar tomonidan kiritilgan boshlangʻich nuqtadan maqsad nuqtasigacha eng maqbul yechimni qanday topishdir. Olingan yechim A * algoritmining aspektlarini amalga oshirish uchun masofa va xarajat jihatlarini koʻrib chiqish natijasidir, lekin u koʻproq masofa aspektlariga qaratilgan.
Jamoat transportidan foydalangan holda izlash muammosining bir misoli quyidagi rasmda koʻrsatilganidek, boshlanish nuqtasi (Chorsu)dan maqsad (Bodomzor) nuqtasiga yoʻnaltirishdir:
1-rasmdagi masalaning h qiymatini aniqlash uchun har bir tugundagi kenglik va uzunlik koordinatalaridan foydalangan holda 1-tenglamani hisoblash uchun olingan toʻgʻri chiziq uzunligini 1-jadvalda koʻrish mumkin. Jadvaldagi maqsadgacha masofani Haversine formulasidan hisoblab topiladi.



1-rasm. Izlash xaritasi misoli

1-jadval. Har bir chorrahaning maqsadgacha boʻlgan toʻgʻri chiziq uzunligi

№	Tugun nomlari	Maqsad tugunigacha masofa (m)
1	Chorsu	4170
2	Xadra	3870
3	Gʻ.Gulom m	3250
4	Transport agentligi	2860
5	A.Navoiy muzeyi	3040
6	Oʻrda	2510
7	Mustaqillik	2290
8	Yulduz	1760
9	Yunusobod hokimiyati	1030
10	Geolograzvedka	396
11	Matonat yodgorligi	1870
12	Navruz bogʻi	2180
13	Markaz 6	1260
14	Zufiyaxonim k.	1950
15	Akademik litsey	2590
16	Sebzor	2880
17	Bahor k.	1770
18	Bilimgoh	1380
19	Semashko i.	537
20	Bodomzor	0

2
-rasmda A * algoritmi bilan boshlangʻich nuqta Chorsudan maqsad Bodomzor tuguniga qadar amalga oshirilgan hisob-kitob namunasi keltirilgan. Xadradan boshlab va eng yaxshi tugunlarni koʻrib chiqiladi. Eng kichik F qiymatiga ega boʻlgan tugun oʻzining barcha vorislarini ochadi va maqsad tugunni topish uchun eng kichik F qiymatiga ega boʻlgan tugunni qidiradi. A * algoritmi izlashni optimallashtirishi mumkin, chunki A * algoritmi ikkita xarajatlarni hisobga oladi, ya’ni maqsad va sarflangan xarajatlar smetasi.

2

-rasm. Muammoni yechish qadamlari
Oxirgi kesishgandan soʻng, ota-ona tugunini tekshirish uchun orqaga qaytishni bajaradi va ota-ona teng boshlangʻich kesishmasini topadi. Kerakli toʻlovlarni hisoblash uchun hal qilish chorrahasini ketma-ket kuzatib borish va jamoat transportining necha marta oʻzgarishini hisoblash orqali tekshirish kerak. Ushbu muammoning optimal varianti: Chorsu->Xadra->A.Navoiy muzeyi->Transport agentligi->Navruz bogʻi-> Matonat yodgorligi-> Markaz 6->Semashko i.->Geolograzvedka->Bodomzor.


Amalga oshirish
Toshkent shahri jamoat transporti katta avtobus, kichik avtobus, marshrutka, metro va elektrobus transportidan iborat. Ushbu ilovada foydalaniladigan jamoat transporti yoʻnalishlari uchun ma’lumot Toshkent shahri transport boshqarmasi saytidan olingan. Ushbu tadqiqotda jamoat transporti orqali oʻtadigan har bir chorraha tugun sifatida belgilanadi. Dastlabki holatdan x tugungacha boʻlgan xarajatlar uchun haqiqiy masofa va tashish tezligi. Hisoblash uchun x tugunining narxi 2-tenglamadan olingan manzilgacha boʻlgan masofa hisoblanadi. Xarita uchun Google xaritasining raqamli xaritasi ishlatiladi. Kesishmaning barcha koordinatalari ma’lumotlar bazasida saqlanadi. 4-rasmda jamoat transporti marshrutlarini qidirish dasturi tasvirlangan.

3-rasm. A * algoritmi blok sxemasi
Izlash natijalari A * algoritmiga juda bogʻliq boʻlib, algoritm boshlangʻich nuqtadan maqsad nuqtasiga qadar eng past chorrahaning taxminiy ogʻirligi (g belgisi bilan belgilanadi) bilan kesishishni topish orqali ishlaydi.
Maqsadga erishish uchun ogʻirlik (h belgisi bilan belgilanadi). Marshrutda f (x) qiymati eng kichik boʻlgan va jamoat transportida borish mumkin boʻlgan tutashma bor, birinchi navbatda ota-ona tugunlari ishlab chiqiladi.
Agar maqsad tugun topilgan boʻlsa, dastur eng maqbulini tashkil etuvchi bir qator kesishmalarni olish uchun har bir tugunning ota-onasiga qaytishni amalga oshiradi.