#algo

A* (A-star) algorithm

Qanday muammoni yechadi: A* o’zining ikkita nuqta orasidagi eng qisqa yo’lni Dijkstra’s algorithm ga solishtirganda effektivroq va tezroq topib berishi bilan ajralib turadi. Tezroq ishlashiga asosiy sababi bir nuqtaga kelish tan narxi (masofasi or whatever) va destination pointga yetib borishning taxminiy narxlarini to’g’ri combine qilib qaror qilishidadir. Aynan shu taxmin qilishi heuristic deb yuritiladi. Tezliklarini solishtirish uchun ushbu videoga refer qiling.

Problem: NxM grid berilgan. Agar (i, j) katakda ‘.’ bo’lsa bu katak bo’sh, ‘#’ esa bu katak band deganini bildiradi. (start_x, start_y) katakdan (end_x, end_y) katakka borishning eng qisqa yo’lini topish kerak.

Yechim: A* ning yechimi Dijkstra amakinikidan uncha farq qilmaydi. Ochiq va yopiq set bor. Ochiq set bu - yurish uchun kandidat kataklarimiz va ularga yurish costlari. Yopiq set esa biz kirib bo’lgan va qayta process qilishni hoxlamaydigan kataklar. Dijkstrada qo’shni kataklarga yurishni shunchaki yurish masofasi yoki narxlarini yig’indisi orqali ifodalasak, A* da heuristic functionimiz qanday implement qilinganiga qarab bu logika istalganicha bo’lishi mumkin. Lekin, klassik holatda quyidagi ko’rinishda bo’ladi: shu katakkacha kelish narxi + destinationgacha yetib borish taxminiy narxi. Shuning uchun tepada takidlaganimdek, A* da ko’p narsa heuristics qanday yozilganiga bog’liq. Misol uchun, ushbu holatda heuristic functionni manhattan distance deb qarashingiz mumkin.

Note: Ba’zi hollarda average run timeni yaxshilash uchun bir necha xil hueristic function yozib, current state qandayligiga qarab mos keladiganini ishlatish ham o’rinli bo’ladi.

Learn Algorithms With ULUGBEK