a-star alqoritmi



facebook twitter əjdaha lazımdı   googllalink

    1. 1968-ci ildə Peter Hart, Nils J. Nilsson və Bertram Raphael tərəfindən hazırlanan axtarış alqoritmidir. əsasən hədəfə qədər ən qısa yolun tapılmasında istifadə olunur (bax: pathfinding). alqoritmin müxtəlif versiyaları kompyuter oyunlarında, robotlarda istifadə olunur. kifayət qədər sürətli alqoritmadır, tək zəif cəhəti həddindən çox əməli yaddaş işlətməsidir.
    bir qədər başa salmağa çalışım bu alqoritmi. deməli bütün xəritə damalara bölünür. damalar üç kateqoriyaya ayrılır. baxılmamış damalar, baxılmış damalar, bunlar openlist adı verilən siyahıda saxlanılır, əməliyyatı tamamlanmış damalar, bunlar isə closelistdə saxlanılır. əvvəlcə agent * öz ətrafındakı damalara nəzər salır. əgər bu damalarda maneə yoxdusa onda onlar üçün aşağıdakı dəyərləri hesablayır:
    1. başlanğıc damasından bu damaya qədər gəlmək üçün tələb olunan xərci.
    2. bu damadan hədəfə qədər olan məsafəni.
    daha sonra yuxarıdakı iki dəyəri toplayır. dama üçün bu dəyəri f olaraq yadda saxlayır. bundan sonra nəzər yetirilən hər damaya hansı damadan gəldiyini qeyd edir və onu openlistə əlavə edir. başlanğıc damasının bütün qonşularına nəzər salındıqdan sonra onu closelistə əlavə edir. növbəti addım olaraq openlistdən ən yaxşı f dəyəri olan damanı seçir və yuxarıdakı əməliyyatları davam elətdirir. nəticədə algoritma nə vaxtsa hədəfə gəlib çatır, əgər bu ümumiyyətlə mümkündürsə. və qeyd etmək istərdim ki, ən optimal yolla gəlib çatır. təbii ki, əgər belə bir optimal yol varsa. algoritmanı iş başında görmək üçün aşağıdakı videoya baxa bilərsiniz:
    (youtube: )


sən də yaz!