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

الگوریتم *A

کلاس	الگوریتم جستجو
ساختمان داده	گراف (ساختار داده)
کارایی بدترین حالت	${displaystyle O(|E|)=O(b^{d})}$
پیچیدگی فضایی	${displaystyle O(|V|)=O(b^{d})}$

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

تاریخچه[ویرایش]

تصویری از ربات شیکی

الگوریتم A* به عنوان بخشی از پروژه [ربات شیکی] ساخته شد. هدف این پروژه ساخت یک ربات متحرک بود که بتواند کاری های خودش را برنامه ریزی کند. نیلز نیلسون الگوریتم پیماینده گراف را برای برنامه ریزی حرکت شیکی معرفی کرد. این الگوریتم از یک تابع هیوریستیک به نام ${displaystyle h(n)}$ استفاده می‌کند که تخمین فاصله گره ${displaystyle n}$ تا هدف است. در این الگوریتم اصلا از تابع ${displaystyle g(n)}$ که فاصله گره شروع تا ${displaystyle n}$ را نشان می‌دهد استفاده‌ای نمی‌شود. برترام رافائل پیشنهاد استفاده از جمع هر دو این توابع را داد (${displaystyle g(n)+h(n)}$). پیتر هارت مفاهیمی که امروزه با نام‌های [قابل قبول] و [یکپارچه] شناخته می‌شوند را ابداع کرد. در ابتدا A* برای پیدا کردن مسیر با کمترین هزینه (هزینه مسیر، جمع هزینه‌های یال‌هایش است) طراحی شده بود. اما امروزه مشخص شده که از این الگوریتم میتواند برای پیدا کردن مسیر بهینه در تمامی مسائلی که شروط Cost-Algebraic ^[۱] را دارند، استفاده شود.

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

مثال از نقشه آلمان همراه مقادیر h در تمام شهر ها. (وورتسبورگ هدف است.

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

${displaystyle f(n)=g(n)+h(n)}$

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

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

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

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

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

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

 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}$ چند گره، پیاده‌سازی به نحوی باشد که آخرین گره ورودی اولین گره خروجی باشد (LIFO)، الگوریتم مشابه جستجو عمق اول عمل می‌کند و از جستجوی مسیرهای بهینه با هزینه یکسان جلوگیری می‌کند.

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

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

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

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

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

در این مثال تمامی شماره ها اشتباه هستند و ${displaystyle h=15}$ می‌شود

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

تابع هیوریستیک منهتن

تابع هیوریستیک اقلیدسی

تابع هیوریستیک چبیشف

تابع هیوریستیک اکتایل

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

خصوصیات[ویرایش]

خاتمه و کامل بودن[ویرایش]

در گراف هایی که محدود هستند و یال‌هایشان وزن نامنفی دارند الگوریتم A* کامل است و خاتمه می‌یابد، یعنی اگه مسیری از گره شروع به هدف موجود باشد این الگوریتم آن را پیدامی‌کند. اگر گراف نامحدود باشد تنها در صورتی که یک جواب موجود باشد و برای تمامی یال ها یک حد پایین برای وزن موجود باشد مثل ${displaystyle varepsilon }$ (${textstyle d(x,y)>varepsilon >0}$قابل قبول بودن[ویرایش]

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

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

بهره وری بهینه (Optimal efficiency)[ویرایش]

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

اگر ${displaystyle f^{*}}$ هزینه‌ی کوتاه‌ترین مسیر به هدف باشد و ${displaystyle A’}$ یک الگوریتم دیگر باشد که شروعش با ${displaystyle A^{*}}$ یکی بوده است و هیوریستیکش هم یکی باشد و بهینه هم باشد (همواره مسیر بهینه را پیدا کند).${displaystyle A’}$ در این مسئله مسیری مثل ${displaystyle p’}$ را که توسط ${displaystyle A^{*}}$ باز شده را باز نمی‌کند. (${displaystyle cost(p’)+h(p’)$)
حال اگر یک مسئله دیگر باشد دقیقا مشابه این مسئله با این تفاوت که ${displaystyle p’}$ یک فرزند دارد که خود هدف است و مثلا نامش ${displaystyle p”}$ است. در این حالت ${displaystyle f}$ خود هزینه است و هیوریستیک دقیق است. در این مسئله ${displaystyle A’}$، مسیر ${displaystyle p’}$ را باز نمی‌کند. یعنی جوابی که در نهایت پیدا می‌کند بیشتر از هزینه ${displaystyle p”}$ می‌شود که این متناقض با بهینه بودن ${displaystyle A’}$ است. درنتیجه ${displaystyle A^{*}}$ یک الگوریتم optimally efficient است.

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

پیچیدگی زمانی[ویرایش]

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

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

که ${displaystyle b^{*}}$ در این رابطه ضریب انشعاب موثر است. هر چه هیوریستیک بهتر باشد این ضریب کمتر است و پیچیدگی زمانی بهتر.

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

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

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

پیچیدگی فضایی الگوریتم A* تقریبا برابر با سایر الگوریتم‌های جستجوی گراف است زیرا تمام گره های باز شده را در حافظه نگه‌می‌دارد. از این رو زمان محاسبه، نقطه ضعف اصلی A* نیست و معمولاً بیشتر از آنکه وقت کم بیاورد، حافظه کم می‌آورد. به همین دلیل 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}$ شبیه به الگوریتم حریصانه است در واقع اگر ${displaystyle g}$ در A* صفر باشد یک الگوریتم حریصانه می‌شود. از نظر در نظر گرفتن ${displaystyle g}$ شبیه به الگوریتم دکسترا است در واقع اگر ${displaystyle h}$ در A* صفر باشد مشابه دکسترا عمل می‌کند.

از طرفی الگوریتم 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