الگوریتم *A ای استار — راهنمای جامع همراه با مثال

در این بخش از آموزش های درس هوش مصنوعی به الگوریتم *A می رسیم. در این آموزش الگوریتم جستجوی ای استار را همراه با مثال و چگونگی پیمایش آموزش خواهیم داد. الگوریتم A Star که معمولاً با نماد *A نمایش داده می شود، جزو یکی از الگوریتم های جستجو است. در ادامه با ما همراه باشید تا این الگوریتم را با یکدیگر بررسی کنیم.

مقدمه

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

روش جستجوی در الگوریتم *A ای استار

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

f(n)=g(n)+ h(n)

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

• اولاً تابع تخمین h(n) باید مقداری کمتر از هزینه واقعی رفتن از گره n به گره هدف را داشته باشد.
• برای یک مسأله می توان توابع تخمین متفاوتی را در نظر گرفت ولی بصورت تجربی می توان گفت تابع که خروجی عددی بزرگ تری دارد. نتیجه بهتری خواهد داشت. (منظور از نتیجه بهتر تعداد گره های تولید شده در فرایند حل مسأله و سرعت رسیدن به جواب می باشد).

بررسی عملکرد الگوریتم *A

حال عملکرد این الگوریتم *A را در قالب یک مثال بررسی می کنیم.  فرض کنید می خواهیم در نقشه کشور رومانی کوتاه ترین مسیر بین دو شهر آراد به بخارست را با الگوریتم *A بدست آوریم.

مقادیر نوشته شده بر روی یال ها هزینه واقعی برای جابجایی بین دو شهر و یا به عبارت دیگر در این مسئله فاصله دو شهر است. در جدول زیر فاصله تخمینی هر یک از شهرها تا بخارست آورده شده است. این فاصله بر اساس خط مستقیمی که دو شهر را به هم وصل می کنم بدست آمده است.

حال جستجو را از شهر آراد شروع می کنیم.

f(Sibiu)=c(Arad,Sibiu)+h(Sibiu)=140+253=393
f(Timisoara)=c(Arad,Timisoara)+h(Timisoara)=118+329=447
f(Zerind)=c(Arad,Zerind)+h(Zerind)=75+374=449

با توجه به مقدار تابع ارزیابی می توان نتیجه گرفت بهترین جانشین Sibiu می باشد. پس این گره را بسط می دهیم.

f(Arad)=c(Sibiu,Arad)+h(Arad)=280+366=646
f(Fagaras)=c(Sibiu,Fagaras)+h(Fagaras)=239+179=415
f(Oradea)=c(Sibiu,Oradea)+h(Oradea)=291+380=671
f(Rimnicu Vilcea)=c(Sibiu,Rimnicu Vilcea)+ h(Rimnicu Vilcea)=220+192=413

از بین شش گره کاندید برای بسط Rimnicu Vilcea به عنوان گره بعدی انتخاب می شود.

f(Craiova)=c(Rimnicu Vilcea, Craiova)+h(Craiova)=360+160=526
f(Pitesti)=c(Rimnicu Vilcea, Pitesti)+h(Pitesti)=317+100=417
f(Sibiu)=c(Rimnicu Vilcea,Sibiu)+h(Sibiu)=300+253=553

با توجه به مقادیر تابع ارزیابی برای حالت های جانشین از بین هشت گره کاندید Fagaras به عنوان گره بعدی انتخاب می شود.

f(Sibiu)=c(Fagaras, Sibiu)+h(Sibiu)=338+253=591
f(Bucharest)=c(Fagaras,Bucharest)+h(Bucharest)=450+0=450

در اینجا ما یک مسیر به بخارست را پیدا کردیم که تابع ارزیابی آن برابر با 450 است. اما گره Pitesti را داریم که امیدواری آن برای رسیدن به جواب 417 است. پس برای رسیدن به مسیر بهتر جستجو را از Pitesti ادامه می دهیم.

در این مرحله ما یک مسیر دیگر به بخارست پیدا کردیم که هزینه آن برابر با 418 است. از بین گره های کاندید هیچ گرهی وجود ندارد که تخمینی کمتر از 418 داشته باشد، پس این جواب بیانگر بهترین مسیر از آراد به بخارست است.

f(Bucharest)=c(Pitesti,Bucharest)+h(Bucharest)=418+0=418

بررسی معیارهای کارایی در الگوریتم *A

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

سورس کد الگوریتم A star برای یافتن کوتاهترین مسیر در #C

در این سورس کد از الگوریتم Astar برای یافتن کوتاهترین مسیر در بازی Maze استفاده شده است. برای تهیه این سورس کد می توانید روی لینک زیر کلیک کنید.

همین الان کلیک کنید

جستجوی عمیق کننده تکراری ای استار terative-deepening A* search

در این روش اساس کار مانند جستجوی A* است با این تفاوت که در ابتدا برای تابع ارزیابی گره های تولید شده یک محدودیت در نظر می گیریم. بطور مثال در مسأله جستجوی مسیر آراد به بخارست فرض می کنیم گره هایی در حافظه می توانند مقیم باشند که تابع ارزیابی آنها از عدد 480 کمتر باشد. به این شکل به گره های که میزان امیدواری بهتر یا احتمال پیدا کردن مسیر کوتاه تر را دارند در حافظه حفظ می کنیم که به این شکل تعداد گره های کمتری در حافظه مقیم می شوند. در ادامه اگر جستجو با این محدودیت به جواب نرسید یا به جواب مطلوب نرسید محدوده تخمین را بیشتر می کنیم. همان مثال فوق اینبار محدوده تابع ارزیابی را به 500 افزایش می دهیم. و دوباره از اول الگوریتم A* اجرا می کنیم و این روند را تارسیدن به جواب بهینه ادامه می دهیم.

اما خود این روش هم یک مشکل عمده دارد و آن حجم دوباره کاری است که در فرایند اجرای الگوریتم اتفاق می افتد. یعنی با هر بار اصلاح تخمین الگوریتم از ابتدا اجرا خواهد شد و در این حالت یک گره ممکن است چندین بار تولید و مقیم در حافظه شود.

جستجوی اول بهترین بازگشتی (RBFS) Recursive best-first search

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

با محاسبه تابع ارزیابی برای شهر های جانشین arad ، بهترین مقدار sibiu می باشد اما مقدار تابع ارزیابی Timisoara برای یادآوری به عنوان پشتیبان حفظ می شود.

در این مرحله از بین فرزندان sibiu، rimnicu بسط داده می شود ولی مقدار fagaras به عنوان پشتیبان حفظ می شود. با بسط rimnicu و محاسبه تابع ارزیابی گره های جانشین می بینیداز بین گره ای مقیم در حافظه fagaras بهترین تابع ارزیابی را دارد، پس زیر شاخه rimnicu از حافظه حذف می شود ولی مقدار بهترین فرزند یعنی 417 برای Pitesti برای یادآوری ذخیره می شود و خواهیم داشت.

با تولید حالت های جانشین fagaras و محاسبه تابع ارزیابی برای آنها، از بین گره های مقیم در حافظه سراغ rimnicu می رویم که می دانیم فرزندی با تابع برازندگی 417 دارد. که با بسط آن خواهیم داشت.

همان گونه که مشاهده می کنید fagaras با مقدار تابع ارزیابی بهترین فرزند خود برچسب گذاری و سراغ rimnicu می رویم. مسیر منتهی به Bucharest هزینه 418 دارد. در ادامه جستجو گرهی که می توان را از آن ادامه داد، Timisoara است اما چون تابع برازندگی آن بیشتر 418 است جواب بهتری تولید نخواهد کرد.

عمده ترین مشکل این روش تولید زیاد گره هاست، هرچند عملکرد بهتری از IDA* دارد. همان گونه که در مثال بالا دیدید، ممکن است گره های فراموش شده چندین بار بسط داده شوند تا جواب بهینه بدست آید.

روش *SMA

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