الگوریتم ای استار

الگوریتم A* به عنوان بخشی از پروژه [[[:en:Shakey the robot|ربات شیکی]]] ساخته شد. هدف این پروژه ساخت یک ربات متحرک بود که بتواند کاری‌های خودش را برنامه‌ریزی کند. نیلز نیلسون الگوریتم پیماینده گراف را برای برنامه‌ریزی حرکت شیکی معرفی کرد. این الگوریتم از یک تابع هیوریستیک به نام ${\displaystyle h(n)}$

A* یک [[[:en:Search algorithm#Informed search|جستجوی آگاه]]]، یا یک جستجوی ابتدا بهترین است، که یعنی از یک گره مشخص (گره شروع) جستجو را آغاز می‌کند و هدفش پیدا کردن یک مسیر به گره نهایی یا هدف است که کمترین هزینه را دارد. این روش با ترکیب ${\displaystyle g(n)}$

از آنجایی که ${\displaystyle g(n)}$

بنابراین اگر به دنبال ارزان‌ترین راه حل هستیم، اولین کار معقول امتحان گره‌ای است که کمترین مقدار ${\displaystyle h(n)+g(n)}$

پیاده‌سازی معمول A* از یک صف اولویت‌دار استفاده می‌کند تا گره‌های دارای کمترین هزینه برآورد شده را در هر مرحله برای باز کردن انتخاب کند. در هر مرحله، گره با کمترین ${\displaystyle f}$

شبه کد

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

 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

نکات پیاده‌سازی

کارهای زیادی برای بهبود عملکرد این الگوریتم می‌توان انجام داد. یکی از این کارها نحوهٔ انتخاب گره‌های با هزینه‌های یکسان از صف اولویت است. اگر در شرایط تساوی ${\displaystyle f}$

اگر به جز هزینه کمینه خود مسیر هم مورد سؤال باشد، لازم است که در هر گره یک اشاره‌گر به پدر آن گره وجود داشته باشد که با پایان جستجو بتوان مسیر را با دنبال کردن اشاره‌گرها یافت. اما در این حالت باید از حضور چند نمونه از یک گره در صف جلوگیری شود. یک روش این است که اگر گره خواست به صف اضافه شود ولی در صف حضور داشت، به جای اضافه‌کردن مجدد آن، اشاره‌گر پدر و هزینهٔ گره موجود در صف، بروزرسانی گردد. این کار توسط صف‌هایی که بر اساس هرم دودویی ساخته شده‌اند به تنهایی ممکن نیست ولی می‌توان با کمک گرفتن از جدول درهم‌سازی برای ذخیره مکان گره در هرم بروزرسانی را انجام داد. همچنین روش‌های دیگری مثل استفاده از هرم فیبوناچی برای ساخت صف اولویت نیز قابل استفاده هستند.

یک مثال از الگوریتم A* در عمل این است که گره‌ها را شهرهایی فرض کنیم که با جاده‌هایی به هم وصل شده‌اند و ${\displaystyle h(x)}$

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

مثالی دیگر برای A* مسئله n-puzzle است که در آن هدف مرتب‌سازی پازل است به نحوی که اعداد به ترتیب مرتب شوند. برای این مسئله یک تابع هیوریستیک نسبتاً ساده می‌تواند تعداد خانه‌هایی باشد که در مکان اشتباه قرار دارند. همچنین g تعداد حرکت‌هایی می‌شود که تا حالا انجام شده‌است.

در چند مثال زیر تأثیر تابع هیوریستیک در پیدا کردن مسیر بهینه قابل مشاهده است.

کلید: سبز پر رنگ:شروع -- قرمز: هدف -- آبی: خانه‌های دیده شده -- سبز کم رنگ: خانه‌های همسایه.

خاتمه و کامل بودن

در گراف‌هایی که محدود هستند و یال‌هایشان وزن نامنفی دارند الگوریتم A* کامل است و خاتمه می‌یابد، یعنی اگه مسیری از گره شروع به هدف موجود باشد این الگوریتم آن را پیدا می‌کند. اگر گراف نامحدود باشد تنها در صورتی که یک جواب موجود باشد و برای تمامی یال‌ها یک حد پایین برای وزن موجود باشد مثل ${\displaystyle \epsilon }$

قابل قبول بودن

یک الگوریتم جستجو قابل قبول است اگر تضمین شود که یک جواب بهینه پیدا می‌کند. در الگوریتم A* اگر تابع ${\displaystyle h}$

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

بهره‌وری بهینه (Optimal efficiency)

یک الگوریتم Optimal efficient است اگر به ازای هر مسئله در یک مجموعه از مسائل و هر الگوریتم در یک مجموعه از الگوریتم‌های جایگزین، گره‌هایی که باز می‌کند یک زیرمجموعه از گره‌هایی باشد که الگوریتم جایگزین باز می‌کند. بررسی کامل optimal efficiency الگوریتم A* توسط رینا دچر (Rina Dechter) و جودیا پرل (Judea Pearl) انجام شده‌است. ولی یک اثبات نسبتاً کوتاه از این موضوع به شرح زیر است:

اگر ${\displaystyle f^{\ast }}$

پیچیدگی زمانی

پیچیدگی زمانی الگوریتم A* به تابع هیوریستیک آن بستگی دارد. در بدترین حالت، تعداد گره‌های فضای جستجوی درون تراز هدف، نسبت به طول راه حل، نمایی می‌باشد. O(b) که در این رابطه ${\displaystyle b}$

تعداد گره‌هایی که در الگوریتم باز می‌شود به صورت زیر است:

که ${\displaystyle b^{\ast }}$

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

که در آن ${\displaystyle h^{\ast }(x)}$

پیچیدگی فضایی

پیچیدگی فضایی الگوریتم A* تقریباً برابر با سایر الگوریتم‌های جستجوی گراف است زیرا تمام گره‌های باز شده را در حافظه نگه‌می‌دارد. از این رو زمان محاسبه، نقطه ضعف اصلی A* نیست و معمولاً بیشتر از آنکه وقت کم بیاورد، حافظه کم می‌آورد. به همین دلیل A* در مورد بسیاری از مسائل بزرگ، عملی نیست و جایگزین‌های بهتری مثل [[[:en:Iterative deepening A*|IDA*]]] برایش آمده‌اند.

در طول سالها انواع مختلفی از A* معرفی شده‌است که چند مورد آن به شرح زیر است:

• Anytime A*
• Block A*
• D*
• Field D*
• Fringe
• Fringe Saving A* (FSA*)
• Generalized Adaptive A* (GAA*)
• Incremental heuristic search
• Iterative deepening A* (IDA*)
• Jump point search
• Lifelong Planning A* (LPA*)
• Simplified Memory bounded A* (SMA*)
• Theta*

همچنین می‌توان از A* به صورت یک الگوریتم جستجوی دوجهته استفاده کرد که البته نیاز به کمی تغییرات دارد.

الگوریتم A* چیزی بین الگوریتم حریصانه و الگوریتم دکسترا است. از نظر در نظر گرفتن ${\displaystyle h}$

از طرفی الگوریتم A* خود یک نمونه از برنامه‌نویسی پویا است.

الگوریتم A* در مسائل مسیریابی در بازی‌های کامپیوتری کاربرد گسترده‌ای دارد. همچنین در برنامه‌ریزی عصبی زبانی (NLP)، گرامر مستقل از متن تصادفی (PCFG) و مطالبی از این دست نیز کاربرد دارد.

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

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

https://web.archive.org/web/20200413111416/http://qiao.github.io/PathFinding.js/visual/

https://web.archive.org/web/20190327234234/https://www.cs.ubc.ca/~kevinlb/teaching/cs322%20-%202008-9/Lectures/Search5.pdf

https://web.archive.org/web/20191118193559/http://how2examples.com/artificial-intelligence/tree-search