الگوریتم جستجوی A*
- معرفیشده توسط
- Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
- سال
- 1968
- نوع
- algorithm
- خانواده
- Graph Algorithms
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
الگوریتم جستجوی A* که در سال ۱۹۶۸ توسط پیتر ای. هارت، نیلس جی. نیلسون و برترام رافائل توسعه یافت، یک الگوریتم بهینهیابی مسیر است که مزایای الگوریتم دایکسترا را با هدایت ابتکاری ترکیب میکند. این الگوریتم با متعادل کردن فاصله واقعی از مبدأ با فاصله تخمینی تا مقصد، به طور مؤثر کوتاهترین مسیر را پیدا میکند.
شهود پشت روش
A* از یک تابع ارزیابی f(n) = g(n) + h(n) استفاده میکند، که در آن g(n) هزینه واقعی از مبدأ تا گره n و h(n) تخمین ابتکاری هزینه باقیمانده تا مقصد است. با کاوش گرههایی با کمترین مقدار f(n)، الگوریتم فضای جستجو را به طور مؤثر به سمت مقصد محدود میکند و در عین حال، در صورت پذیرفتنی بودن ابتکار (هرگز بیش از حد تخمین نمیزند)، بهینگی را حفظ میکند. این امر A* را به طور قابل توجهی سریعتر از روشهای جستجوی غیرمطلع میسازد و در عین حال تضمین میکند که مسیر بهینه را پیدا کند.
تاریخ
هارت، نیلسون و رافائل در سال ۱۹۶۸ الگوریتم A* را منتشر کردند و نشان دادند که افزودن اطلاعات ابتکاری به الگوریتم دایکسترا میتواند کارایی جستجو را به طور چشمگیری بهبود بخشد و در عین حال بهینگی را حفظ کند. این الگوریتم در هوش مصنوعی و تحقیق در عملیات بنیادی شد. تحولات بعدی شامل A* دوطرفه، IDA* (تعمیق تکراری) و بهبودهای ابتکاری مختلف است. A* همچنان انتخاب استاندارد برای یافتن مسیر در موتورهای بازی مدرن و سیستمهای رباتیک است.
چه زمانی استفاده شود
هنگامی که نیاز به یافتن مسیرهای بهینه در گرافهایی دارید که تابع ابتکاری خوبی در دسترس است، از A* استفاده کنید. این الگوریتم به ویژه برای یافتن مسیر در بازیها، رباتیک و برنامهریزی مسیر مؤثر است، جایی که جستجوی مطلع میتواند محاسبات را به طور قابل توجهی کاهش دهد. زمانی که سرعت مهم است اما بهینگی مورد نیاز است، از آن استفاده کنید. برای مواردی که ابتکار قابل اعتماد وجود ندارد، به جای آن از الگوریتم دایکسترا استفاده کنید.
محدودیتها و ملاحظات
- بهینگی به پذیرفتنی بودن تابع ابتکاری بستگی دارد
- عملکرد با ابتکارات ضعیف یا غیرپذیرفتنی به طور قابل توجهی کاهش مییابد
- مصرف حافظه میتواند در فضاهای جستجوی بزرگ قابل توجه باشد (مجموعههای باز و بسته را حفظ میکند)
- نیاز به دانش صریح دامنه برای طراحی توابع ابتکاری خوب دارد
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- یافتن مسیر بهینه زمانی که ابتکار پذیرفتنی باشد
- بسیار سریعتر از دایکسترا یا جستجوی اول سطح در صورت در دسترس بودن ابتکارات خوب
- انعطافپذیر: با هر تابع ابتکاری پذیرفتنی کار میکند
- مناسب برای مسائل یافتن مسیر تکمقصد
- اعتبارسنجی گسترده در دنیای واقعی در بازیها، رباتیک و سیستمهای ناوبری
کاربردها
- یافتن مسیر در بازیهای ویدیویی: ناوبری NPC در زمان واقعی در محیطهای بازی پویا
- برنامهریزی حرکت ربات: برنامهریزی مسیر بهینه برای رباتهای خودکار با اجتناب از موانع
- ناوبری GPS: محاسبه مسیرهای کارآمد با در نظر گرفتن شبکههای جادهای و ترافیک
- حل معما: یافتن راهحلهای بهینه در مسائل ترکیبی مانند معمای ۱۵
- مسیریابی شبکه: تعیین مسیرهای بستهای کارآمد با ابتکارات کیفیت پیوند
- بیوانفورماتیک: جستجوهای همترازی توالی و پیشبینی ساختار پروتئین
چگونه کار میکند
چگونه کار میکند
یک مجموعه باز با گره مبدأ ایجاد کنید، مقدار g آن (هزینه از مبدأ) را صفر قرار دهید و مقدار h آن را با استفاده از تابع ابتکاری محاسبه کنید.
گره با کمترین مقدار f را از مجموعه باز انتخاب کنید، مقادیر f را برای همسایگان بازدید نشده آن محاسبه کنید و همسایگان امیدوارکننده را به مجموعه باز اضافه کنید.
گسترش گرهها را تا رسیدن به مقصد با کمترین مقدار f ادامه دهید، که مسیر بهینه را تضمین میکند؛ مسیر را با ردیابی اشارهگرهای والد بازسازی کنید.
دامهای رایج
- استفاده از یک ابتکار غیرپذیرفتنی که هزینهها را بیش از حد تخمین میزند و منجر به مسیرهای غیربهینه میشود
- انتخاب یک ابتکار که بیش از حد ساده یا نامرتبط با مسئله است و کارایی جستجو را کاهش میدهد
- پیادهسازی ناکارآمد مجموعه باز (باید از صف اولویت استفاده شود)، که باعث انتخاب کند گره میشود
پرسشهای متداول
یک ابتکار پذیرفتنی چیست و چرا اهمیت دارد؟
یک ابتکار پذیرفتنی هرگز هزینه واقعی تا مقصد را بیش از حد تخمین نمیزند. این ویژگی تضمین میکند که A* مسیر بهینه را پیدا کند. اگر یک ابتکار بیش از حد تخمین بزند، A* ممکن است مسیرهای کوتاهتر را از دست بدهد و راهحلهای غیربهینه را برگرداند.
چگونه یک ابتکار خوب برای یک مسئله طراحی میکنید؟
ابتکارات خوب بر اساس دانش دامنه و ساختار مسئله استوار هستند. برای یافتن مسیر مبتنی بر شبکه، فاصله منهتن یا اقلیدسی به خوبی کار میکند. برای مسائل پیچیدهتر، به استراحت دادن محدودیتها یا استفاده از پایگاه دادههای الگو برای محاسبه ابتکارات پذیرفتنی فکر کنید.
تفاوت بین الگوریتم A* و دایکسترا چیست؟
هر دو مسیرهای بهینه را پیدا میکنند، اما A* از یک ابتکار برای اولویتبندی کاوش به سمت مقصد استفاده میکند و آن را در صورت در دسترس بودن ابتکار خوب بسیار سریعتر میسازد. دایکسترا به طور یکنواخت در همه جهات کاوش میکند و زمانی که ابتکارات قابل اعتماد نیستند، ایمنتر است.
آیا A* میتواند تضمین کند که کوتاهترین مسیر را پیدا کند؟
بله، A* زمانی که ابتکار پذیرفتنی باشد (هرگز هزینه واقعی را بیش از حد تخمین نمیزند)، کوتاهترین مسیر را تضمین میکند. با ابتکارات غیرپذیرفتنی، بهینگی تضمین نمیشود.
روشهای مرتبط
منابع
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
باز کردن مرجع DOIکپی شد.Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.
شابک: 978-0-13-604259-4کپی شد.