الگوریتم A* (انگلیسی : A* Search Algorithm)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
الگوریتم A* (انگلیسی : A* Search Algorithm) :
📌 معرفی
الگوریتم A* (A-star) یک الگوریتم جستجوی آگاهانه (Informed Search) است که به طور گسترده برای یافتن کوتاه ترین مسیر در گراف ها استفاده می شود. این الگوریتم ترکیبی از الگوریتم دیکسترا (که هزینه مسیر طی شده را در نظر می گیرد) و جستجوی حریصانه بهترین اول (Greedy Best-First Search) (که یک هیوریستیک را در نظر می گیرد) است. A* با استفاده از یک تابع ارزیابی
\[ f(n) = g(n) + h(n) \]کار می کند.
📐 تابع ارزیابی
\[ g(n) \]
: هزینه واقعی مسیر از گره شروع تا گره فعلی n.
\[ h(n) \]
: هزینه تخمینی (هیوریستیک) از گره n تا گره هدف. هیوریستیک باید قابل قبول (Admissible) باشد، یعنی هرگز هزینه واقعی را بیش تخمین نزند.
\[ f(n) = g(n) + h(n) \]
: هزینه تخمینی مسیر از شروع تا هدف که از n عبور می کند.
🔧 ویژگی ها
A* با یک هیوریستیک قابل قبول، همیشه کوتاه ترین مسیر را پیدا می کند (بهینگی).
کارایی A* به کیفیت هیوریستیک بستگی دارد. یک هیوریستیک خوب می تواند فضای جستجو را به شدت کاهش دهد.
کاربردها: مسیریابی در نقشه ها (GPS)، بازی های کامپیوتری (یافتن مسیر برای کاراکترها)، رباتیک.
