الگوریتمِ A* برایِ انتخابِ مسیر، هزینهٔ طی‌شدهٔ g را با تخمینِ هزینهٔ باقی‌ماندهٔ h جمع می‌کند و کوچک‌ترینِ f=g+h را از صفِ اولویت برمی‌دارد. درست‌بودنِ این تخمین و قراردادِ بازدید مهم است. اینجا رویِ یک گرافِ کوچک، هم بازگشاییِ واقعیِ یک گره و هم شکستِ تخمینِ بیش‌برآوردکننده را اجرا می‌کنیم.
گراف و هدف را پیش از جست‌وجو ثبت کنیم
یال‌هایِ جهت‌دارِ ساخته‌شده S→Aبا۳، S→Bبا۱، B→Aبا۱، A→Gبا۳ وB→Gبا۱۰هستند. G هدف وUیک گرهٔ جداست. اعدادْ هزینه‌هایِ آموزشیِ نامنفی‌اند؛ زمانِ تماس، مسافتِ شهری یا قیمتِ واقعی نیستند. مسیرِ S→A→G هزینهٔ۶ و مسیرِ S→B→A→G هزینهٔ۵ دارد. برنامه تمامِ مسیرهایِ سادهٔ همین گراف را هم مستقل می‌شمارد تا کمینه را کنترل کند.
مجازبودن با سازگاربودن فرق دارد
تخمین را h(S)=۰، h(A)=۰، h(B)=۴ وh(G)=۰می‌گذاریم. هزینهٔ واقعیِ باقی‌مانده ازAسه وازBچهار است؛ پس این تخمین هیچ‌کدام را بیشتر از واقعیت نمی‌گوید و نامنفی است. اما رویِ یالِB→A، رابطهٔ h(B)≤۱+h(A) برقرار نیست:۴بزرگ‌تر از۱است. بنابراین تخمینِ این مثال مجاز ولی ناسازگار است.
برایِ همین قراردادِ گرافیِ محدود، وقتی مسیرِ ارزان‌تر به گرهٔ قبلاً گسترش‌یافته پیدا می‌شود، باید امکانِ گسترشِ دوباره را حفظ کنیم. یک مجموعهٔ «برایِ همیشه دیده‌شده» می‌تواند پاسخِ بهتر را حذف کند. فایل، بهترینِ gِ شناخته‌شده و gِ آخرینِ گسترش را جدا نگه می‌دارد و فقط بهبودِ سخت‌گیرانه را واردِ صف می‌کند.
چرا A دوباره باز می‌شود؟
| گرهِ برداشته‌شده | g | h | f | رویداد |
|---|---|---|---|---|
| S | ۰ | ۰ | ۰ | Aباg۳ وBباg۱ واردِ صف می‌شوند |
| A | ۳ | ۰ | ۳ | Gباg۶ پیدا می‌شود |
| B | ۱ | ۴ | ۵ | مسیرِ Aبهg۲ بهتر می‌شود |
| A، دوباره | ۲ | ۰ | ۲ | Gبهg۵ بهتر می‌شود |
| G | ۵ | ۰ | ۵ | مسیرِ S→B→A→G برگردانده می‌شود |
فایلِ JSON افزون بر گسترش‌ها، هر تغییرِ old_g به new_g را دارد. نشانِ parent با همان بهبود به‌روز می‌شود و مسیر از هدف به مبدأ بازگردانی می‌شود. هدف را هنگامِ کشفِ اولیه تمام‌شده نمی‌نامیم؛ در آن لحظه هنوز مسیرِ۶را داشتیم.
تخمینِ بد چطور جوابِ بدتر می‌سازد؟
فقط h(B)را۱۰۰می‌کنیم و بقیهٔ گراف و هزینه‌ها ثابت می‌مانند. این بار Bباf۱۰۱ در صف است، پس A و بعدGبا هزینهٔ۶ برداشته می‌شوند. روش با همین قاعدهٔ توقف، مسیرِ۶را برمی‌گرداند، درحالی‌که oracle هزینهٔ۵را دارد. تخمینِ بیش‌ازحد می‌تواند کمینه‌بودنِ نتیجه را از بین ببرد؛ «هوشمندبودنِ تخمین» تضمینِ کیفیت نیست.
در اجرایِ دیگر، همهٔ hها صفرند و هزینهٔ۵به دست می‌آید. این اتصالِ A*به جست‌وجویِ هزینه‌یکنواخت، دلیلِ یکسان‌بودنِ همهٔ فرایندهایِ جست‌وجو نیست. دایکسترا را برایِ دفترِ فاصلهٔ همهٔ گره‌هایِ دسترس‌پذیر، یالِ صفر و رکوردِ کهنه بخوانید؛ مسئلهٔ اصلیِ این صفحه اثرِ تخمین و بازگشایی بود.
حدودِ پیاده‌سازیِ فایل
گرافِ متناهی، وزنِ نامنفیِ متناهی و تخمینِ ثابتِ کامل باhهدفِ صفر خواسته می‌شوند. ترتیبِ تساوی با شمارندهٔ ورود به heap و ترتیبِ فهرستِ همسایه‌ها مشخص است؛ هزینهٔ برابر parent را عوض نمی‌کند. رکوردی که gِ آن دیگر بهترین نیست، کهنه محسوب و کنار گذاشته می‌شود. در این مثالِ صحیح، وزن‌ها عددِ صحیح‌اند و خطایِ گردکردن واردِ حسابِ مسیر نشده است.
برایِ هدفِ U، مسیر و هزینه null می‌شوند؛ nullبه معنیِ مسیرِ هزینهٔصفر نیست. شمارشِ همهٔ مسیرهایِ ساده فقط oracleِ گرافِ بسیار کوچک است و روشِ مقیاس‌پذیرِ عمومی نیست. NetworkX در این تمرین اجرا نشده، مسیرِ واقعی جست‌وجو نشده و تعدادِ گسترش‌ها را بنچمارکِ سرعتِ همهٔ مسائل نمی‌نامیم.
این جست‌وجو با تولیدِ متن یکی نیست
Beam Search پیشوندهایِ دنباله را با قراردادِ احتمال و عرضِ محدود هرس می‌کند؛ اینجا هزینهٔ جمع‌شونده و کرانِ تخمین داریم. پیام‌رسانیِ گرافی هم تغییرِ ویژگیِ گره است، نه همین مسیر‌یابی. برایِ مبانی به آموزشِ هوشِ مصنوعی بروید؛ برایِ نیازِ واقعیِ پاسخ‌گویی، کار و شاهدِ پذیرش را در راهکارهایِ اپرا مطرح کنید. الگوریتمِ داخلیِ محصول از این تمرین نتیجه نمی‌شود.
فایل تمرین و منبع
صفِ اولویت، بازگشایی و oracleِ مسیرهایِ ساده؛ Python · تمامِ بهبودها و گسترش‌ها، تخمینِ مجاز و ضدنمونهٔ نامجاز
- Berkeley CS188؛ g/h/f، مجازبودن و بازدیدِ دوباره در جست‌وجویِ گرافی
- NetworkX؛ قراردادِ تخمین، مرزِ بیش‌برآورد و مسیرِ ناموجود؛ کتابخانه اجرا نشده است
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.