الگوریتم *A

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

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

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

از جستجوی ابتدا بهترین استفاده می‌کند و کوتاه‌ترین مسیر را بین دو گره مبدأ و مقصد داده شده به وسیله گره‌های دیگر می‌یابد. این روش با ترکیب هزینه رسیدن به گره و هیوریستیک یا تخمین هزینه رسیدن از گره م تا هدف گره‌ها را ارزیابی می‌کند:

از آنجایی که هزینه مسیر از گره شروع به گره و هزینه تخمینی ارزان‌ترین مسیر از به هدف است، داریم:

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

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

 1  function A*(start,goal)
 2      closedset:= the empty set  // The set of nodes already evaluated.
 3      openset:= {start}    // The set of tentative nodes to be evaluated,
 4                           // initially containing the start node
 5      came_from:= the empty map // The map of navigated nodes.
 6 
 7      g_score[start]:= 0 // Cost from start along best known path.
 8      h_score[start]:= heuristic_cost_estimate(start, goal)
 9      f_score[start]:= g_score[start] + h_score[start] // Estimated total cost
10                                                       // from start to goal through y.
11 
12      while openset is not empty
13          x:= the node in openset having the lowest f_score[] value
14          if x = goal
15              return reconstruct_path(came_from, came_from[goal])
16 
17          remove x from openset
18          add x to closedset
19          foreach y in neighbor_nodes(x)
20              if y in closedset
21                  continue
22              tentative_g_score:= g_score[x] + dist_between(x,y)
23 
24              if y not in openset
25                  add y to openset
26                  tentative_is_better:= true
27              else if tentative_g_score <g_score[y]
28                  tentative_is_better:= true
29              else
30                  tentative_is_better:= false
31 
32              if tentative_is_better = true
33                  came_from[y]:= x
34                  g_score[y]:= tentative_g_score
35                  h_score[y]:= heuristic_cost_estimate(y, goal)
36                  f_score[y]:= g_score[y] + h_score[y]
37 
38      return failure
39 
40  function reconstruct_path(came_from, current_node)
41      if came_from[current_node] is set
42          p:= reconstruct_path(came_from, came_from[current_node])
43          return (p + current_node)
44      else
45          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* به آرگومان آن بستگی دارد. در بدترین حالت، تعداد گره‌های فضای جستجوی درون تراز هدف، نسبت به طول راه حل، نمایی می‌باشد. در صورتی که خطای تابع آروین سریع تر از لگاریتم هزینه واقعی رشد کند رشد نمایی اتفاق می‌افتد. به عبارت دیگر شرط رشد به صورت نمایی جزئی به این صورت است که:

که در آن هزینه واقعی رسیدن از گره به هدف است.

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

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

مشارکت‌کنندگان ویکی‌پدیا. «A* search algorithm». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۸ مهٔ ۲۰۱۹.

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