الگوریتم ای استار
در علوم کامپیوتر، الگوریتم A* یک الگوریتم مسیریابی است که برای پیمایش و یافتن مسیر در گراف استفاده می‌شود. به علت کامل بودن، بهینه بودن (یافتن جواب بهینه) و سرعت مناسب این الگوریتم، استفاده گسترده‌ای از آن می‌شود. مشکل اصلی این الگوریتم استفادهٔ زیاد از حافظه است که باعث می‌شود در بسیاری از مسائل عملی ضعیف تر از سایر الگوریتم‌ها عمل کند. پیتر ای هارت (به انگلیسی: Peter E. Hart)، نیلز نیلسون (Nils Nilsson) و برترام رافائل (Bertram Raphael) اولین کسانی بودند که آن را در سال ۱۹۶۸ میلادی شرح دادند. این الگوریتم در واقع تعمیمی از الگوریتم دیکسترا می‌باشد که با استفاده از روش‌های فرا ابتکاری عملکرد بهتری در زمینه جستجو بدست آورده‌است.
الگوریتم A* به عنوان بخشی از پروژه ] ساخته شد. هدف این پروژه ساخت یک ربات متحرک بود که بتواند کاری‌های خودش را برنامه‌ریزی کند. نیلز نیلسون الگوریتم پیماینده گراف را برای برنامه‌ریزی حرکت شیکی معرفی کرد. این الگوریتم از یک تابع هیوریستیک به نام formula_1 استفاده می‌کند که تخمین فاصله گره formula_2 تا هدف است. در این الگوریتم اصلاً از تابع formula_3 که فاصله گره شروع تا formula_2 را نشان می‌دهد استفاده‌ای نمی‌شود. برترام رافائل پیشنهاد استفاده از جمع هر دو این توابع را داد (formula_5). پیتر هارت مفاهیمی که امروزه با نام‌های و شناخته می‌شوند را ابداع کرد. در ابتدا A* برای پیدا کردن مسیر با کمترین هزینه (هزینه مسیر، جمع هزینه‌های یال‌هایش است) طراحی شده بود. اما امروزه مشخص شده که از این الگوریتم می‌تواند برای پیدا کردن مسیر بهینه در تمامی مسائلی که شروط Cost-Algebraic را دارند، استفاده شود.
A* یک ]، یا یک جستجوی ابتدا بهترین است، که یعنی از یک گره مشخص (گره شروع) جستجو را آغاز می‌کند و هدفش پیدا کردن یک مسیر به گره نهایی یا هدف است که کمترین هزینه را دارد. این روش با ترکیب formula_3 هزینه رسیدن به گره formula_2 و formula_1 هیوریستیک یا تخمین هزینه رسیدن از گره formula_2م تا هدف گره‌ها را ارزیابی می‌کند:formula_10از آنجایی که formula_3 هزینه مسیر از گره شروع به گره formula_2 و formula_1 هزینه تخمینی ارزان‌ترین مسیر از formula_2 به هدف است، داریم:formula_15 = هزینه برآورد ارزان‌ترین راه حل از طریق nبنابراین اگر به دنبال ارزان‌ترین راه حل هستیم، اولین کار معقول امتحان گره‌ای است که کمترین مقدار formula_16 را داراست. مشخص می‌شود که این راهبرد کاملاً معقولانه‌است. اگر تابع آروین formula_1 قابل قبول و جستجو درختی باشد الگوریتم بهینه است. اما اگر جستجوی گراف باشد علاوه برای قابل قبول بودن لازم است تا یکپارچه نیز باشد.اگر A* همراه با الگوریتم جستجوی درخت استفاده شود، آنگاه تحلیل بهینگی آن بسیار ساده و سر راست می‌شود. A* بهینه‌است اگر formula_1 یک آروین قابل قبول باشد؛ یعنی formula_1 هرگز هزینه رسیدن به هدف را بیش از اندازه واقعی برآورد نکند. این آروین‌ها ذاتاً بهینه هستند زیرا آن‌ها فکر می‌کنند که هزینه راه حل مسئله کمتر از مقدار واقعی آن است. از آنجا که formula_3 هزینه رسیدن به formula_2 را به‌طور دقیق نشان می‌دهد، می‌توان بلافاصله نتیجه گرفت که formula_15 هرگز هزینه واقعی راه حلی که از formula_2 می‌گذرد را اضافه برآورد نمی‌کند.
پیاده‌سازی معمول A* از یک صف اولویت‌دار استفاده می‌کند تا گره‌های دارای کمترین هزینه برآورد شده را در هر مرحله برای باز کردن انتخاب کند. در هر مرحله، گره با کمترین formula_24 از صف حذف می‌شود، سپس تابع formula_24 همسایه‌های آن گره به روز رسانی می‌شود و در نهایت همسایه‌ها به صف اضافه می‌شوند. جستجو زمانی به پایان می‌رسد که یا مسیری از گره شروع به هدف یافت نمی‌شود، به عبارت دیگر صف خالی می‌شود و دیگری گره‌ای برای باز کردن وجود ندارد. یا به گره هدف می‌رسد که در این صورت مقدار formula_24 همان کمترین هزینه است برای رسیدن به گره هدف، زیرا تابع formula_27 در هدف به علت قابل قبول بودن ۰ است.
شبه کد زیر الگوریتم را توصیف می‌کند:
کارهای زیادی برای بهبود عملکرد این الگوریتم می‌توان انجام داد. یکی از این کارها نحوهٔ انتخاب گره‌های با هزینه‌های یکسان از صف اولویت است. اگر در شرایط تساوی formula_24 چند گره، پیاده‌سازی به نحوی باشد که آخرین گره ورودی اولین گره خروجی باشد (LIFO)، الگوریتم مشابه جستجو عمق اول عمل می‌کند و از جستجوی مسیرهای بهینه با هزینه یکسان جلوگیری می‌کند.
اگر به جز هزینه کمینه خود مسیر هم مورد سؤال باشد، لازم است که در هر گره یک اشاره‌گر به پدر آن گره وجود داشته باشد که با پایان جستجو بتوان مسیر را با دنبال کردن اشاره‌گرها یافت. اما در این حالت باید از حضور چند نمونه از یک گره در صف جلوگیری شود. یک روش این است که اگر گره خواست به صف اضافه شود ولی در صف حضور داشت، به جای اضافه‌کردن مجدد آن، اشاره‌گر پدر و هزینهٔ گره موجود در صف، بروزرسانی گردد. این کار توسط صف‌هایی که بر اساس هرم دودویی ساخته شده‌اند به تنهایی ممکن نیست ولی می‌توان با کمک گرفتن از جدول درهم‌سازی برای ذخیره مکان گره در هرم بروزرسانی را انجام داد. همچنین روش‌های دیگری مثل استفاده از هرم فیبوناچی برای ساخت صف اولویت نیز قابل استفاده هستند.
یک مثال از الگوریتم A* در عمل این است که گره‌ها را شهرهایی فرض کنیم که با جاده‌هایی به هم وصل شده‌اند و formula_29 فاصله اقلیدسی نقطهٔ x تا نقطه هدف باشد:
"کلید:" سبز:شروع؛ آبی: هدف؛ نارنجی: گره ملاقات شده.
مثالی دیگر برای A* مسئله n-puzzle است که در آن هدف مرتب‌سازی پازل است به نحوی که اعداد به ترتیب مرتب شوند. برای این مسئله یک تابع هیوریستیک نسبتاً ساده می‌تواند تعداد خانه‌هایی باشد که در مکان اشتباه قرار دارند. همچنین g تعداد حرکت‌هایی می‌شود که تا حالا انجام شده‌است. در چند مثال زیر تأثیر تابع هیوریستیک در پیدا کردن مسیر بهینه قابل مشاهده است.
کلید: سبز پر رنگ:شروع -- قرمز: هدف -- آبی: خانه‌های دیده شده -- سبز کم رنگ: خانه‌های همسایه.
در گراف‌هایی که محدود هستند و یال‌هایشان وزن نامنفی دارند الگوریتم A* کامل است و خاتمه می‌یابد، یعنی اگه مسیری از گره شروع به هدف موجود باشد این الگوریتم آن را پیدا می‌کند. اگر گراف نامحدود باشد تنها در صورتی که یک جواب موجود باشد و برای تمامی یال‌ها یک حد پایین برای وزن موجود باشد مثل formula_30 (formula_31)، تضمین می‌شود که الگوریتم خاتمه بیابد.
یک الگوریتم جستجو قابل قبول است اگر تضمین شود که یک جواب بهینه پیدا می‌کند. در الگوریتم A* اگر تابع formula_27 قابل قبول باشد الگوریتم قابل قبول است. یک اثبات شهودی برای این مسئله به صورت زیر است:
وقتی جستجو به پایان می‌رسد، الگوریتم یک جواب پیدا کرده‌است که هزینه‌اش از تمام مسیرهای دیگر کمتر مساوی است. وقتی هیوریستیک قابل قبول است یعنی یک حد پایینی از مقدار واقعی را دارد پس برای هر مسیر مقدارش کمتر از مقدار واقعی نیست و A* آن مسیرهایی را که کمینه نیستند را در نظر نمی‌گیرد. با این کار امکان ندارد که مسیری در نظر گرفته نشود اگر هزینه کمتری داشته باشد.
یک الگوریتم Optimal efficient است اگر به ازای هر مسئله در یک مجموعه از مسائل و هر الگوریتم در یک مجموعه از الگوریتم‌های جایگزین، گره‌هایی که باز می‌کند یک زیرمجموعه از گره‌هایی باشد که الگوریتم جایگزین باز می‌کند. بررسی کامل optimal efficiency الگوریتم A* توسط رینا دچر (Rina Dechter) و جودیا پرل (Judea Pearl) انجام شده‌است. ولی یک اثبات نسبتاً کوتاه از این موضوع به شرح زیر است:
اگر formula_33 هزینهٔ کوتاه‌ترین مسیر به هدف باشد و formula_34 یک الگوریتم دیگر باشد که شروعش با formula_35 یکی بوده‌است و هیوریستیکش هم یکی باشد و بهینه هم باشد (همواره مسیر بهینه را پیدا کند).formula_34 در این مسئله مسیری مثل formula_37 را که توسط formula_35 باز شده را باز نمی‌کند. (formula_39) حال اگر یک مسئله دیگر باشد دقیقاً مشابه این مسئله با این تفاوت که formula_37 یک فرزند دارد که خود هدف است و مثلاً نامش formula_41 است. در این حالت formula_24 خود هزینه است و هیوریستیک دقیق است. در این مسئله formula_34، مسیر formula_37 را باز نمی‌کند؛ یعنی جوابی که در نهایت پیدا می‌کند بیشتر از هزینه formula_41 می‌شود که این متناقض با بهینه بودن formula_34 است. درنتیجه formula_35 یک الگوریتم optimally efficient است.
پیچیدگی زمانی الگوریتم A* به تابع هیوریستیک آن بستگی دارد. در بدترین حالت، تعداد گره‌های فضای جستجوی درون تراز هدف، نسبت به طول راه حل، نمایی می‌باشد. که در این رابطه formula_48 ضریب انشعاب می‌باشد و formula_49 عمق جواب بهینه می‌باشد.
تعداد گره‌هایی که در الگوریتم باز می‌شود به صورت زیر است:
formula_50
که formula_51 در این رابطه ضریب انشعاب مؤثر است. هر چه هیوریستیک بهتر باشد این ضریب کمتر است و پیچیدگی زمانی بهتر.
در صورتی که محیط جستجو درخت باشد و یک گره هدف وجود داشته‌باشد و خطای تابع آروین سریع تر از لگاریتم هزینه واقعی رشد نکند (عبارت ریاضی در پایین آمده‌است)، پیچیدگی زمانی چندجمله‌ای خواهد بود:
formula_52
که در آن formula_53 هزینه واقعی رسیدن از گره formula_2 به هدف است.
پیچیدگی فضایی الگوریتم A* تقریباً برابر با سایر الگوریتم‌های جستجوی گراف است زیرا تمام گره‌های باز شده را در حافظه نگه‌می‌دارد. از این رو زمان محاسبه، نقطه ضعف اصلی A* نیست و معمولاً بیشتر از آنکه وقت کم بیاورد، حافظه کم می‌آورد. به همین دلیل A* در مورد بسیاری از مسائل بزرگ، عملی نیست و جایگزین‌های بهتری مثل ] برایش آمده‌اند.
در طول سالها انواع مختلفی از A* معرفی شده‌است که چند مورد آن به شرح زیر است:
همچنین می‌توان از A* به صورت یک الگوریتم جستجوی دوجهته استفاده کرد که البته نیاز به کمی تغییرات دارد.
الگوریتم A* چیزی بین الگوریتم حریصانه و الگوریتم دکسترا است. از نظر در نظر گرفتن formula_27 شبیه به الگوریتم حریصانه است در واقع اگر formula_56 در A* صفر باشد یک الگوریتم حریصانه می‌شود. از نظر در نظر گرفتن formula_56 شبیه به الگوریتم دکسترا است در واقع اگر formula_27 در A* صفر باشد مشابه دکسترا عمل می‌کند.
از طرفی الگوریتم A* خود یک نمونه از برنامه‌نویسی پویا است.
الگوریتم A* در مسائل مسیریابی در بازی‌های کامپیوتری کاربرد گسترده‌ای دارد. همچنین در برنامه‌ریزی عصبی زبانی (NLP)، گرامر مستقل از متن تصادفی (PCFG) و مطالبی از این دست نیز کاربرد دارد.
کتاب – نوشته استوارت راسل و پیتر نورویگ – ترجمه سعید راحتی، چاپ سیزدهم. مشهد: دانشگاه امام رضا (ع)، ۱۳۸۹ ۹۷۸-۶۰۰-۵۶۵۰-۰۶-۸.
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