در علوم کامپیوتر، الگوریتم 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 هستند، امّا شما میتوانید آنها را به راحتی به هر زبان دیگری ترجمه کنید:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
<span style="font-size: 12pt; color: #000000;">[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)</span> |
نظرات ثبت شده بدون دیدگاه