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

مهم نیست که شما می‎خواهید از کدام زبان برنامه نویسی برای پیاده سازی این الگوریتم استفاده کنید، فقط گام به گام با ما پیش بیایید و فقط سعی کنید که الگوریتم «آ-ستاره» را کاملاً دقیق بفهمید.

گربه‎ی مسیریاب

تصور کنید که ما یک بازی داریم که در آن گربه‎ای می‎خواهد مسیری را برای رسیدن به یک تکه استخوان پیدا کند.
شاید از خود بپرسید که یک گربه چرا باید به دنبال یک تکه استخوان باشد؟!
خوب! گربه‎ی بازیِ ما بسیار حیله‎گر است و می‎خواهد با جمع کردن استخوان‎ها و دادن آن‎ها به سگ‎ها، از چنگال آن‎ها در امان بماند!
فرض کنید گربه‎ی موجود در تصویر زیر می‎خواهد کوتاه‎ترین مسیر برای رسیدن به استخوان را پیدا کند:

متأسفانه گربه نمی‎تواند مستقیماً از محل فعلی خود به طرف استخوان حرکت کند، چون در مقابلش یک دیوار قرار دارد و گربه‎ی ما هم یک روح نیست تا از دیوار عبور کند!
از طرف دیگر، گربه‎ی بازی ما خیلی تنبل است و می‎خواهد که کوتاه‎ترین راه را پیدا کند.
اما ما چگونه می‎توانیم الگوریتمی بنویسیم که کوتاه‎ترین مسیری را که گربه می‎تواند به سمت استخوان بپیماید، پیدا کند؟ اینجاست که از «آ-ستاره» کمک می‎گیریم!

ساده کردن حوزه‎ی جستجو

در گام نخست باید حوزه‎ی جستجو را به چیزی که مدلسازی ریاضی آن آسان باشد نزدیک کنیم.
مثلاً می‎توانیم حوزه‎ی جستجو را پیکسل‎بندی کنیم؛ اما در شرایط فعلی این کاملاً غیرضروری است و فقط کار ما را سخت می‎کند پس بهتر است به چیز ساده‎تری فکر کنیم مثلاً تقسیم‎بندی صفحه به مربع‎های هم اندازه و تا حد ممکن بزرگ. البته می‎توان واحدهای مختلفی برای تقسیم‎بندی صفحه (مثل مثلث یا شش‎ ضلعی) به کار برد اما مربع آسان‎ترین و بهترین گزینه‎ای است که می‎توان برای این بازی انتخاب کرد.
با این تقسیم‎بندی می‎توانیم حوزه‎ی جستجو را تبدیل به یک آرایه‎ی دو بعدی کنیم که مانند یک نقشه از حوزه‎ی جستجو، همه چیز را در اختیار ما می‎گذارد. مثلاً اگر سطح یک نقشه‎ی 25 در 25 از کاشی‎ها را در نظر بگیریم، حوزه‎ی جستجوی ما یک آرایه‎ی دوبعدی متشکل از 625 مربع خواهد بود. حالا اگر در همین نقشه، بخواهیم از واحد پیکسل استفاده کنیم، حوزه‎ی جستجوی ما تبدیل به یک آرایه‎ی دوبعدی متشکل از 640000 مربع خواهد شد (هر کاشی 32×32 پیکسل است)!
بهتر است پس از تقسیم‎بندیِ مربعیِ حوزه‎ی جستجو از آن یک عکس بگیریم که حالا به یک صفحه با (6×7 کاشی =) 42 کاشی مربعی‎شکل تبدیل شده است:

لیست‎های باز و بسته

حالاً که حوزه‎ی جستجو را به شکل ساده‎تری درآوردیم، زمان بحث در مورد الگوریتم آ-ستاره رسیده است.
گربه‎ی ما علاوه بر این که تنبل است، حافظه‎ی چندان خوبی هم ندارد، بنابر این ما به دو لیست نیاز داریم:
1.    یکی برای فهرست کردن تمام مربع‎هایی که تصور می‎شود کوتاه‎ترین مسیر را به دست دهند که آن را لیست باز می‎نامیم.
2.    دیگری برای فهرست کردن مربع‎هایی که دیگر لازم نیست مورد ارزیابی قرار گیرند که آن را لیست بسته می‎نامیم.
گربه با اضافه کردن موقعیت فعلی‎اش به لیست بسته، کارش را شروع می‎کند. (ما نقطه‎ی شروع را A می نامیم.) سپس از میان مربع‎های همسایه‎اش ، آن‎هایی را که قابل تردد هستند به لیست باز اضافه می‎کند.
این تصویر نمونه‎ای از چیزی است در بالا بیان شد، البته اگر گربه در محیطی باز و بدون مانع قرار داشته باشد (مربع‎های با حاشیه‎ی سبزرنگ همان لیستِ باز هستند):

حالا گربه باید مشخص کند که کدام یک از این مربع‎ها در کوتاه‎ترین مسیر قرار دارند، اما چگونه؟
خوب، در الگوریتم آ-ستاره این کار با اختصاص دادن امتیاز به هر مربع انجام می‎پذیرد که به آن امتیازدهی می‎گوییم.

امتیازدهی به مسیر

ما به هر مربع یک امتیاز که حاصل جمع G+H است، اختصاص می‎دهیم:
• G اندازه‎ی حرکت از نقطه‎ی شروع مسیر تا مکان فعلی است. با این حساب برای مربع همسایه‎ی نقطه‎ی A ، این مقدار برابر 1 خواهد بود و هرچقدر که از نقطه‎ی آغازِ حرکت دورتر شویم، مقدار G افزایش خواهد یافت.
• H تخمین ما از فاصله‎ی مربعی که اکنون در آن قرار داریم تا نقطه‎ی پایان مسیر (که از این پس آن را B می نامیم) است. این عدد لزوماً مقدار واقعی نیست چون ما هنوز مسیر را نپیموده‎ایم تا مقداد دقیق آن را بفهمیم بلکه فقط یک حدس است.
شاید بپرسید که منظور از «اندازه‎ی حرکت» چیست؟ خوب، در این بازی ما بسیار ساده است – صرفاً تعداد مربع‎هایی است که از روی آن‎ها عبور کرده ایم.
به هر حال باید به یاد داشته باشید که نحوه‎ی محاسبه‎ی G و H متناسب با شرایط بازی می‎تواند متفاوت باشد. مثلاً:
• اگر شما مجاز به حرکت‎های قطری (اُریب) باشید، باید اندازه‎ی حرکت مربوط به حرکت‎های قطری را اندکی بیشتر از حرکت‎های مستقیم (بالا، چپ، پایین و راست) در نظر بگیرید.
• اگر در بازی شما عوارض و موانع طبیعی مختلفی وجود دارد باید اندازه‎ی حرکت را برای عبور از باتلاق، دریاچه و هر مانعی که عبور از آن مشکل‎تر است، بیشتر در نظر بگیرید.
این‎ها همگی مفاهیم کلّی بودند – حالا وقت دقیق شدن در جزئیات محاسبه‎ی G و H است.

درباره‎ی G بیشتر بدانید

به یاد بیاورید که G اندازه‎ی حرکت (و به طور خاص در بازی ما، تعداد مربع‎های پیموده شده) از نقطه‎ی شروع حرکت یعنی A تا موقعیت کنونی است.
برای محاسبه‎ی G در یک مکان خاص از مسیر ، ما باید G مربوط به موقعیت مادر آن (یعنی آخرین مربعی که از آن گذشته‎ایم و به اینجا رسیده‎ایم) را در نظر بگیریم و یک واحد به آن اضافه کنیم. با این دستورالعمل، G مربوط به هر مربع، تعداد مربع‎هایی است که از نقطه‎ی شروع یعنی A تا موقعیت کنونی از روی آن‎ها عبور کرده‎ایم.
به عنوان مثال، نمودار زیرین دو مسیر متفاوت را به سوی دو تکه استخوان متفاوت نشان می‎دهد که مقادیر G مربوط به هر مربع موجود در مسیر روی خود آن مربع نوشته شده است:

درباره‎ی H بیشتر بدانید

به یاد بیاورید که H اندازه‎ی حرکت تخمینی (یعنی تعداد مربع‎های باقیمانده) از موقعیت فعلی تا نقطه‎ی پایان مسیر یعنی B است.
هر چقدر که اندازه‎ی حرکت تخمینی به اندازه‎ی واقعی نزدیک‎تر باشد، مسیر نهایی درست‎تر خواهد بود. اگر این مقدار تخمینی مورد استفاده قرار نگیرد، ممکن است مسیر نهایی کوتاه‎ترین مسیر نباشد (البته شاید نزدیک به آن باشد). این موضوع بسیار پیچیده است و از این رو در این مقاله پوشش داده نخواهد شد.
برای این که کارمان را ساده کنیم از «روش فاصله‎ی منهتن» (که با نام‎های «طول منهتن» یا «فاصله‎ی بلوکی شهری» هم شناخته می‎شود) استفاده می‎کنیم که بدون در نظر گرفتن موانع و عوارض طبیعی موجود در مسیر، فقط فاصله‎ی افقی و عمودی از نقطه‎ی فعلی تا رسیدن به نقطه‎ی نهایی یعنی B را حساب می‎کند.
به عنوان مثال، تصویر زیر چگونگی استفاده از «فاصله‎ی بلوکی شهری» را در محاسبه‎ی H نشان می‎دهد (که مقدار آن با رنگ سیاه در مربع مربوطه نوشته شده است):

الگوریتم آ-ستاره

حالا که متوجه شدید چگونه باید امتیاز هر مربع را محاسبه کنیم (که از این به بعد آن را F می‎نامیم و برابر با G+H است)، وقت آن است که ببینیم الگوریتم آ-ستاره چگونه کار می‎کند.
گربه‎ی ما کوتاه‎ترین مسیر را با تکرار کردن مراحل زیر پیدا خواهد کرد:
1. مربعی که کم‎ترین امتیاز را در لیست باز دارد را در نظر می‎گیریم. از این پس این مربع را S می‎نامیم.
2. S را از لیست باز حذف می‎کنیم و به لیست بسته اضافه می‎کنیم.
3. به ازای هر مربعِ T که در همسایگی S قرار دارد:
1. اگر T در لیستِ بسته است: آن را نادیده بگیر. (کاری به کارش نداشته باش.)
2. اگر T در لیستِ باز نیست: آن را به لیست باز اضافه کن و امتیازش (F) را محاسبه کن.
3. اگر T در لیستِ باز است: بررسی کن که با در نظر گرفتن S به عنوان موقعیت مادر و محاسبه‎ی مجددِ G ، آیا امتیازِ F آن کاهش می‎یابد؟ اگر پاسخ مثبت است، امتیاز آن را به روز کن و موقعیتِ مادر آن را نیز به روز کن.
اگر هنوز هم کمی سردرگم هستید، نگران نباشید چون از این پس با یک مثال و گام به گام پیش خواهیم رفت تا نحوه‎ی عملکرد این الگوریتم را عیناً مشاهده کنید!

مسیر گربه

بگذارید با همان مثالِ گربه‎ی تنبل خودمان و مسیرش به سوی تکه استخوان پیش برویم.
در نمودارهای زیر، مقادیرِ F = G + H مطابق با نکات زیر داخل هر مربع نوشته شده‎اند:
F (امتیاز مربع مربوطه): گوشه‎ی چپ و بالا
G (مسافت پیموده شده از A تا مربع مربوطه): گوشه‎ی چپ و پایین
H (مسافت تخمینی از مربع مربوطه تا B): گوشه‎ی راست و بالا
همچنین، پیکان‎های موجود در هر مربع، جهت حرکتی که برای رفتن به آن مربع نیاز است را نشان می‎دهد.
در نهایت، در هر مرحله، مربع‎های سرخ‎رنگ نشان دهنده‎ی موارد موجود در لیست بسته هستند و مربع‎های سبزرنگ نشان دهنده‎ی موارد موجود در لیست باز هستند.
بسیار خوب، حالا شروع می‎کنیم:

گام اوّل:
در گام اوّل، گربه‎ی ما از میان مربع‎های مجاور مکان کنونی یعنی A ، مربع‎هایی را که مسدود نیستند شناسایی کرده و امتیازِ F آن‎ها را محاسبه می‎کند و سپس آن‎ها را به لیست باز اضافه می‎کند:

شما می‎توانید ببینید که مقدار H برای هر مربع نوشته شده است (دو تا از آن‎ها 6 هستند و یکی 4). من پیشنهاد می‎کنم که از همان روش شمارش مربع‎ها با توجه به «فاصله‎ی بلوکی شهری» استفاده کنید تا متوجه شوید که چه می‎شود.
همچنین توجه داشته باشید که مقدارِ F (در گوشه‎ی چپ و بالا) صرفاً حاصل جمع G+H است (که در گوشه‎های پایینی نوشته شده‎اند).

گام دوم:
در گام بعدی، گربه‎ی ما مربعی که کم‎ترین مقدار F را دارد، انتخاب کرده و آن را به لیست بسته اضافه می‎کند، از لیست باز حذف می‎کند و مربع‎های مجاور این مربع جدید (که کم‎ترین F را داشته است) را شناسایی می‎کند.

مربعی که کمترین امتیاز را دارد همان مربعی است که مقدارِ F آن برابر 5 است. گربه تلاش می‎کند که تمام مربع‎های مجاور را به لیستِ باز اضافه کند (و امتیاز آن‎ها را محاسبه کند)، اما باید توجه داشته باشید که او نمی‎تواند مکان قبلی خودش را (که هم اکنون در لیستِ بسته قرار دارد) یا موانع موجود در مسیر مانند مربع‎های هاشور خورده را (که قابل تردد نیستند) به لیست باز اضافه کند.
توجه کنید که برای مربع‎های جدیدی که به لیست باز افزوده می‎شوند، مقدارِ G به اندازه‎ی یک واحد افزایش پیدا می‎کند چون این مربع‎ها 2 کاشی دورتر از نقطه‎ی شروع هستند. برای اطمینان از مقدار H هم می‎توانید از شمارش «فاصله‎ی بلوکی شهری» استفاده کنید.

گام سوم:
دوباره مربعی که کمترین مقدار F (یعنی 5) را داراست انتخاب کرده و روند پیشین را تکرار می‎کنیم:

در این مرحله تنها یک کاشی می‎تواند به لیست باز اضافه شود، چون دوتا از کاشی‎های همسایه مسدود هستند و یکی هم در لیستِ بسته قرار دارد.

گام چهارم:
حالا با یک وضعیت جالب مواجه شده‎ایم. همان‎گونه که در تصویر قبلی مشاهده کردید، 4 مربع با مقدارِ F یکسان (یعنی 7) موجودند؛ الآن چه باید کرد؟!
راه حل‎های مختلفی برای این وضعیت وجود دارد اما ساده‎ترین و در عین حال سریع‎ترین راه این است که آخرین مربعی که به لیستِ باز اضافه شده است را برای حرکت بعدی انتخاب کنیم:

این بار دو کاشی قابل تردد در همسایگی وجود دارد که امتیاز آن‎ها را حساب می‎کنیم.

گام پنجم:
دوباره مربعی که کمترین مقدار F (یعنی 7) را داراست و آخر از همه به لیستِ باز افزوده شده است انتخاب می‎کنیم:

در این مرحله فقط یک مربعِ قابلِ تردد به لیست باز اضافه می‎شود. داریم نزدیک می‎شویم!

گام ششم:
دیگر خودتان روند کار را یاد گرفته‎اید! مطمئنم که می‎توانید گام بعدی را حدس بزنید:

تقریباً رسیده‎ایم، امّا این بار مشاهده می‎کنید که دو مسیر وجود دارد که هر دو طول یکسانی دارند و کوتاه‎ترین مسیر هستند که می‎توانیم یکی از آن‎ها را انتخاب کنیم تا به استخوان برسیم:

در مثال ما 2 مسیر مختلف به عنوان کوتاه‎ترین مسیر وجود دارند:
6 – 5 – 4 – 3 – 2 – 1
7 – 5 – 4 – 3 – 2 – 1
فرقی نمی‎کند که کدام‎یک از آن‎ها را انتخاب کنیم، این موضوع در اجرای واقعی الگوریتم در هنگام کدنویسی در نظر گرفته می‎شود.

گام هفتم:
بگذارید مسیر را از طریق یکی از این دو مربع ادامه دهیم:

حالا استخوان در لیستِ باز است!

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

سپس تنها کاری که الگوریتم باید انجام دهد این است به عقب برگردد و مسیر نهایی را شناسایی کند.

یک گربه‎ی معمولی

در مثال فوق، ما می‎بینیم که وقتی گربه به دنبال کوتاه‎ترین مسیر می‎گشت، غالباً بهترین مربع را انتخاب می‎کرد (آن مربعی که در راستای کوتاه‎ترین مسیرِ آینده‎اش قرار داشت) – انگار که او یک گربه‎ی طالع‎بین بود.
اما چه می‎شد اگر گربه‎ی ما نمی‎توانست آینده را ببیند و همواره اوّلین مربعی را که به لیست اضافه می‎شد انتخاب می‎کرد؟
شکل زیر نشان می‎دهد که اگر این فرایند را طی می‎کردیم چه مربع‎هایی را مورد بررسی قرار می‎دادیم. شما مشاهده می‎کنید که در این حالت گربه‎ی ما مربع‎های بیشتری را امتحان می‎کند، امّا باز هم کوتاه‎ترین مسیر را پیدا می‎کند (نه دقیقاً همان مسیری که قبلاً پیدا کرده بود امّا مسیر دیگری با طول یکسان پیدا می‎کند):

مربع‎های سرخ‎رنگ در نمودار فوق لزوماً کوتاه‎ترین مسیر را نشان نمی‎دهند، آن‎ها فقط مربع‎هایی را نشان می‎دهند که در مراحل مختلف به عنوانِ مربعِ S در نظر گرفته شده‎اند.
من توصیه می‎کنم که به نمودار بالایی نگاه کنید و سعی کنید که همگام با آن پیش بروید. این بار در هر چندراهی «بدترین» مسیر را برای رفتن انتخاب کنید. خواهید دید که باز هم با پیمودن کوتاه‎ترین مسیر به انتها می‎رسید!
شما می‎بینید که اگر مربعِ «اشتباه» را دنبال کنید، مشکلی پیش نمی‎آید و شما با کوتاه‎ترین مسیر به انتها می‎رسید هرچند که باید روند الگوریتم را بیشتر تکرار کنید.
در اجرا، ما مربع‎ها را با توجه به الگوریتم زیر به لیستِ باز اضافه می‎کنیم:
مربع‎های همسایه به این ترتیب در نظر گرفته می‎شوند: بالا/چپ/پایین/راست
یک مربع پس از تمام مربع‎هایی که امتیاز یکسانی با آن دارند به لیستِ باز افزوده می‎شود (بنابر این اوّلین مربعی که اضافه می‎شود اولّین مربعی است که گربه انتخاب می‎کند).
این یک نمودار برای عقب‎گرد و بازخوانی مسیر است:

کوتاه‎ترین مسیر با شروع از نقطه‎ی مقصد و عقب رفتن از یک مربع مادر به مربع مادر دیگر ساخته می‎شود (مثلاً: در مربعِ مقصد می‎بینیم که پیکانِ داخلِ آن به سمت راست است پس مربعِ مادرِ آن در سمت چپ قرار دارد).
برای نتیجه‎گیری می‎توانیم فرایندی را که گربه طی می‎کند به صورت شبهِ‎کدِ زیر خلاصه کنیم. کدهای زیر به زبان Objective-C هستند، امّا شما می‎توانید آن‎ها را به راحتی به هر زبان دیگری ترجمه کنید:

[openList add:originalSquare]; // start by adding the original position to the open list
do {
 currentSquare = [openList squareWithLowestFScore]; // Get the square with the lowest F score
 
 [closedList add:currentSquare]; // add the current square to the closed list
 [openList remove:currentSquare]; // remove it to the open list
 
 if ([closedList contains:destinationSquare]) { // if we added the destination to the closed list, we've found a path
 // PATH FOUND
 break; // break the loop
 }
 
 adjacentSquares = [currentSquare walkableAdjacentSquares]; // Retrieve all its walkable adjacent squares
 
 foreach (aSquare in adjacentSquares) {
 
 if ([closedList contains:aSquare]) { // if this adjacent square is already in the closed list ignore it
 continue; // Go to the next adjacent square
 }
 
 if (![openList contains:aSquare]) { // if its not in the open list
 
 // compute its score, set the parent
 [openList add:aSquare]; // and add it to the open list
 
 } else { // if its already in the open list
 
 // test if using the current G score make the aSquare F score lower, if yes update the parent because it means its a better path
 
 }
 }
 
} while(![openList isEmpty]); // Continue until there is no more available square in the open list (which means there is no path)