موضوع مقاله: الگوریتم ای استار | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم ای استار | مقدمه: در علوم کامپیوتر، الگوریتم A* یک الگوریتم مسیریابی است که برای پیمایش و یافتن مسیر در گراف استفاده می‌شود. | ## بخش 1: الگوریتم ای استار | به علت کامل بودن، بهینه بودن (یافتن جواب بهینه) و سرعت مناسب این الگوریتم، استفاده گسترده‌ای از آن می‌شود. مشکل اصلی این الگوریتم استفادهٔ زیاد از حافظه است که باعث می‌شود در بسیاری از مسائل عملی ضعیف تر از سایر الگوریتم‌ها عمل کند. این الگوریتم در واقع تعمیمی از الگوریتم دیکسترا می‌باشد که با استفاده از روش‌های فرا ابتکاری عملکرد بهتری در زمینه جستجو به‌دست آورده‌است. هدف این پروژه ساخت یک ربات متحرک بود که بتواند کاری‌های خودش را برنامه‌ریزی کند. این الگوریتم از یک تابع هیوریستیک به نام استفاده می‌کند که تخمین فاصله گره تا هدف است. در این الگوریتم اصلاً از تابع که فاصله گره شروع تا را نشان می‌دهد استفاده‌ای نمی‌شود. پیتر هارت مفاهیمی که امروزه با نام‌های قابل قبول و یکپارچه شناخته می‌شوند را ابداع کرد. در ابتدا A* برای پیدا کردن مسیر با کمترین هزینه (هزینه مسیر، جمع هزینه‌های یال‌هایش است) طراحی شده بود. A* یک جستجوی آگاه، یا یک جستجوی ابتدا بهترین است، که یعنی از یک گره مشخص (گره شروع) جستجو را آغاز می‌کند و هدفش پیدا کردن یک مسیر به گره نهایی یا هدف است که کمترین هزینه را دارد. این روش با ترکیب هزینه رسیدن به گره و هیوریستیک یا تخمین هزینه رسیدن از گره م تا هدف گره‌ها را ارزیابی می‌کند:از آنجایی که هزینه مسیر از گره شروع به گره و هزینه تخمینی ارزان‌ترین مسیر از به هدف است، داریم: = هزینه برآورد ارزان‌ترین راه حل از طریق nبنابراین اگر به دنبال ارزان‌ترین راه حل هستیم، اولین کار معقول امتحان گره‌ای است که کمترین مقدار را داراست. اما اگر جستجوی گراف باشد علاوه برای قابل قبول بودن لازم است تا یکپارچه نیز باشد.اگر A* همراه با الگوریتم جستجوی درخت استفاده شود، آنگاه تحلیل بهینگی آن بسیار ساده و سر راست می‌شود. A* بهینه‌است اگر یک آروین قابل قبول باشد؛ یعنی هرگز هزینه رسیدن به هدف را بیش از اندازه واقعی برآورد نکند. این آروین‌ها ذاتاً بهینه هستند زیرا آن‌ها فکر می‌کنند که هزینه راه حل مسئله کمتر از مقدار واقعی آن است. از آنجا که هزینه رسیدن به را به‌طور دقیق نشان می‌دهد، می‌توان بلافاصله نتیجه گرفت که هرگز هزینه واقعی راه حلی که از می‌گذرد را اضافه برآورد نمی‌کند. پیاده‌سازی معمول A* از یک صف اولویت‌دار استفاده می‌کند تا گره‌های دارای کمترین هزینه برآورد شده را در هر مرحله برای باز کردن انتخاب کند. | ## بخش 2: الگوریتم ای استار | در هر مرحله، گره با کمترین از صف حذف می‌شود، سپس تابع همسایه‌های آن گره به روز رسانی می‌شود و در نهایت همسایه‌ها به صف اضافه می‌شوند. جستجو زمانی به پایان می‌رسد که یا مسیری از گره شروع به هدف یافت نمی‌شود، به عبارت دیگر صف خالی می‌شود و دیگری گره‌ای برای باز کردن وجود ندارد. یا به گره هدف می‌رسد که در این صورت مقدار همان کمترین هزینه است برای رسیدن به گره هدف، زیرا تابع در هدف به علت قابل قبول بودن ۰ است. اگر در شرایط تساوی چند گره، پیاده‌سازی به نحوی باشد که آخرین گره ورودی اولین گره خروجی باشد (LIFO)، الگوریتم مشابه جستجو عمق اول عمل می‌کند و از جستجوی مسیرهای بهینه با هزینه یکسان جلوگیری می‌کند. اگر به جز هزینه کمینه خود مسیر هم مورد سؤال باشد، لازم است که در هر گره یک اشاره‌گر به پدر آن گره وجود داشته باشد که با پایان جستجو بتوان مسیر را با دنبال کردن اشاره‌گرها یافت. یک روش این است که اگر گره خواست به صف اضافه شود ولی در صف حضور داشت، به جای اضافه‌کردن مجدد آن، اشاره‌گر پدر و هزینهٔ گره موجود در صف، بروزرسانی گردد. این کار توسط صف‌هایی که بر اساس هرم دودویی ساخته شده‌اند به تنهایی ممکن نیست ولی می‌توان با کمک گرفتن از جدول درهم‌سازی برای ذخیره مکان گره در هرم بروزرسانی را انجام داد. همچنین روش‌های دیگری مثل استفاده از هرم فیبوناچی برای ساخت صف اولویت نیز قابل استفاده هستند. مثال جایگزین=|وسط یک مثال از الگوریتم A* در عمل این است که گره‌ها را شهرهایی فرض کنیم که با جاده‌هایی به هم وصل شده‌اند و فاصله اقلیدسی نقطهٔ x تا نقطه هدف باشد: کلید: سبز:شروع؛ آبی: هدف؛ نارنجی: گره ملاقات شده. مثالی دیگر برای A* مسئله n-puzzle است که در آن هدف مرتب‌سازی پازل است به نحوی که اعداد به ترتیب مرتب شوند. برای این مسئله یک تابع هیوریستیک نسبتاً ساده می‌تواند تعداد خانه‌هایی باشد که در مکان اشتباه قرار دارند. خصوصیات خاتمه و کامل بودن در گراف‌هایی که محدود هستند و یال‌هایشان وزن نامنفی دارند الگوریتم A* کامل است و خاتمه می‌یابد، یعنی اگه مسیری از گره شروع به هدف موجود باشد این الگوریتم آن را پیدا می‌کند. اگر گراف نامحدود باشد تنها در صورتی که یک جواب موجود باشد و برای تمامی یال‌ها یک حد پایین برای وزن موجود باشد مثل ، تضمین می‌شود که الگوریتم خاتمه بیابد. قابل قبول بودن یک الگوریتم جستجو قابل قبول است اگر تضمین شود که یک جواب بهینه پیدا می‌کند. یک اثبات شهودی برای این مسئله به صورت زیر است: وقتی جستجو به پایان می‌رسد، الگوریتم یک جواب پیدا کرده‌است که هزینه‌اش از تمام مسیرهای دیگر کمتر مساوی است. | ## بخش 3: الگوریتم ای استار | وقتی هیوریستیک قابل قبول است یعنی یک حد پایینی از مقدار واقعی را دارد پس برای هر مسیر مقدارش کمتر از مقدار واقعی نیست و A* آن مسیرهایی را که کمینه نیستند را در نظر نمی‌گیرد. ولی یک اثبات نسبتاً کوتاه از این موضوع به شرح زیر است: اگر هزینهٔ کوتاه‌ترین مسیر به هدف باشد و یک الگوریتم دیگر باشد که شروعش با یکی بوده‌است و هیوریستیکش هم یکی باشد و بهینه هم باشد (همواره مسیر بهینه را پیدا کند). حال اگر یک مسئله دیگر باشد دقیقاً مشابه این مسئله با این تفاوت که یک فرزند دارد که خود هدف است و مثلاً نامش است. در این مسئله ، مسیر را باز نمی‌کند؛ یعنی جوابی که در نهایت پیدا می‌کند بیشتر از هزینه می‌شود که این متناقض با بهینه بودن است. پیچیدگی پیچیدگی زمانی پیچیدگی زمانی الگوریتم A* به تابع هیوریستیک آن بستگی دارد. در بدترین حالت، تعداد گره‌های فضای جستجوی درون تراز هدف، نسبت به طول راه حل، نمایی می‌باشد. تعداد گره‌هایی که در الگوریتم باز می‌شود به صورت زیر است: که در این رابطه ضریب انشعاب مؤثر است. در صورتی که محیط جستجو درخت باشد و یک گره هدف وجود داشته‌باشد و خطای تابع آروین سریع تر از لگاریتم هزینه واقعی رشد نکند (عبارت ریاضی در پایین آمده‌است)، پیچیدگی زمانی چندجمله‌ای خواهد بود: که در آن هزینه واقعی رسیدن از گره به هدف است. پیچیدگی فضایی پیچیدگی فضایی الگوریتم A* تقریباً برابر با سایر الگوریتم‌های جستجوی گراف است زیرا تمام گره‌های باز شده را در حافظه نگه‌می‌دارد. از این رو زمان محاسبه، نقطه ضعف اصلی A* نیست و معمولاً بیشتر از آنکه وقت کم بیاورد، حافظه کم می‌آورد. ارتباط با سایر الگوریتم‌ها الگوریتم A* چیزی بین الگوریتم حریصانه و الگوریتم دکسترا است. از نظر در نظر گرفتن شبیه به الگوریتم حریصانه است در واقع اگر در A* صفر باشد یک الگوریتم حریصانه می‌شود. از نظر در نظر گرفتن شبیه به الگوریتم دکسترا است در واقع اگر در A* صفر باشد مشابه دکسترا عمل می‌کند. کاربردها الگوریتم A* در مسائل مسیریابی در بازی‌های کامپیوتری کاربرد گسترده‌ای دارد. | ## جمع‌بندی | همچنین در برنامه‌ریزی عصبی زبانی (NLP)، گرامر مستقل از متن تصادفی (PCFG) و مطالبی از این دست نیز کاربرد دارد.