الگوریتم جستجوی آ*

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از الگوریتم جستجوی A*)
پرش به: ناوبری، جستجو

در علوم کامپیوتر، الگوریتم A* یک الگوریتم کامپیوتری است که به طور وسیع در پیمایش گراف و یافتن مسیر بین دو نقطه که گره نامیده می‌شوند، مورد استفاده قرار می‌گیرد. به علت عملکرد و دقت بالای این الگوریتم استفاده گسترده‌ای از آن می‌شود. پیتر ای هارت (به انگلیسی: Peter E. Hart)، نیلز نیلسون (به انگلیسی: Nils Nilsson) و برترام رافائل (به انگلیسی: Bertram Raphael) اولین کسانی بودند که آن را در سال ۱۹۶۸ میلادی شرح دادند. این الگوریتم درواقع تعمیمی از الگوریتم دیکسترا می‌باشد. A* با استفاده از آروین(heuristic) عملکرد بهتری نسبت به زمان به دست می‌آورد.[۱]

توضیح[ویرایش]

از جستجوی اولین بهترین استفاده می‌کند و کوتاه ترین مسیر را بین دو گره مبدا و مقصد داده شده به وسیله گره‌های دیگر می‌یابد.
این روش با ترکیب g(n) هزینه رسیدن به گره n و h(n) هزینه رسیدن از گره nم تا هدف گره‌ها را ارزیابی می‌کند:

f(n)= g(n) + h(n)

از آنجایی که g(n) هزینه مسیر از گره شروع به گره n و h(n) هزینه تخمینی ارزان ترین مسیر از n به هدف است، داریم:

f(n) = هزینه برآورد ارزان ترین راه حل از طریق n

بنابراین اگر به دنبال ارزان ترین راه حل هستیم، اولین کار معقول امتحان گره‌ای است که کمترین مقدار h(n)+g(n) را داراست. مشخص می‌شود که این راهبرد کاملاً معقولانه‌است. اگر تابع آروین h(n) شرایط خاصی داشته باشد. جستجوی A* هم کامل و هم بهینه‌است.
اگر A* همراه با الگوریتم جستجوی درخت استفاده شود، آنگاه تحلیل بهینگی آن بسیار ساده و سر راست می‌شود. A* بهینه‌است اگر h(n) یک آروین قابل قبول باشد. یعنی h(n) هرگز هزینه رسیدن به هدف را بیش از اندازه واقعی برآورد نکند. این آروین‌ها ذاتاً بهینه هستند زیرا آنها فکر می‌کنند که هزینه راه حل مسئله کمتر از مقدار واقعی آن است. از آنجا که g(n) هزینه رسیدن به n را به طور دقیق نشان می‌دهد، می‌توان بلافاصله نتیجه گرفت که f(n) هرگز هزینه واقعی راه حلی که از n می‌گذرد را اضافه برآورد نمی‌کند.[۲]

شبه کد[ویرایش]

شبه کد زیر الگوریتم را توصیف می‌کند:[۳]

 function A*(start,goal)
     closedset:= the empty set  // The set of nodes already evaluated.
     openset:= {start}    // The set of tentative nodes to be evaluated,
                          // initially containing the start node
     came_from:= the empty map // The map of navigated nodes.
 
     g_score[start]:= 0 // Cost from start along best known path.
     h_score[start]:= heuristic_cost_estimate(start, goal)
     f_score[start]:= g_score[start] + h_score[start] // Estimated total cost
                                                      // from start to goal through y.
 
     while openset is not empty
         x:= the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from, came_from[goal])
 
         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score:= g_score[x] + dist_between(x,y)
 
             if y not in openset
                 add y to openset
                 tentative_is_better:= true
             else if tentative_g_score <g_score[y]
                 tentative_is_better:= true
             else
                 tentative_is_better:= false
 
             if tentative_is_better = true
                 came_from[y]:= x
                 g_score[y]:= tentative_g_score
                 h_score[y]:= heuristic_cost_estimate(y, goal)
                 f_score[y]:= g_score[y] + h_score[y]
 
     return failure
 
 function reconstruct_path(came_from, current_node)
     if came_from[current_node] is set
         p:= reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node

مثال[ویرایش]

یک مثال از الگوریتم A* در عمل این است که گره‌ها را شهرهایی فرض کنیم که با جاده‌هایی به هم وصل شده‌اند و h(x) فاصله مستقیم تا نقطه هدف باشد:[۴]
An example of A star (A*) algorithm in action (nodes are cities connected with roads, h(x) is the straight-line distance to target point) Green: Start, Blue: Target, Orange: Visited

کلید: سبز:شروع؛ آبی: هدف؛ نارنجی: گره ملاقات شده.

پیچیدگی[ویرایش]

پیچیدگی زمان الگوریتم A* به آرگومان آن بستگی دارد. در بدترین حالت، تعداد گره‌های فضای جستجوی درون تراز هدف، نسبت به طول راه حل، نمایی می‌باشد. در صورتی که خطای تابع آروین سریع تر از لگاریتم هزینه واقعی رشد کند رشد نمایی اتفاق می‌افتد. به عبارت دیگر شرط رشد به صورت نمایی جزئی به این صورت است که:

|h(x) - h^*(x)| \le O(\log{h^*(x)})

که در آن h^*(x) هزینه واقعی رسیدن از گره n به هدف است.

زمان محاسبه، نقطه ضعف اصلی A* نیست. از آنجا که این الگوریتم، تمامی گره‌های تولید شده را در حافظه نگهداری می‌کند معمولاً بیشتر از آنکه وقت کم بیاورد، حافظه کم می‌آورد. به همین دلیل A* در مورد بسیاری از مسائل بزرگ، عملی نیست.

منابع[ویرایش]

  1. ویکی‌پدیا انگلیسی
  2. راسل، استوارت. جی، و پیتر نورویک. رویکردی نوین در هوش مصنوعی، ترجمه سعید راحتی، چاپ سیزدهم. مشهد: دانشگاه امام رضا(ع)، ۱۳۸۹ ۹۷۸-۶۰۰-۵۶۵۰-۰۶-۸.
  3. ویکی‌پدیا انگلیسی
  4. ویکی‌پدیا انگلیسی

پیوند به بیرون[ویرایش]