الگوریتم جست وجوی *A، مینیمم کردن کل هزینه جواب

الگوریتم جست وجوی*A، مینیمم کردن کل هزینه جواب

معروفترین شکل"جست وجوی اول-بهترین" جست وجوی A* نام دارد که از دیگر  استراتژی های جست وجوی آگاهانه میباشد  . این روش گره ها را با ترکیب g(n) یعنی هزینه رسیدن به گره و h(n) یعنی هزینه رسیدن از این گره به گره هدف، ارزیابی میکند:

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

چون g(n) هزینه مسیری از گره شروع به گره n و h(n) هزینه برآورد شده ی ارزانترین مسیر از n به گره هدف است، داریم:

 f(n) = n هزینه برآورد شده ارزانترین جواب از طریق  

پس اگر سعی در یافتن ارزانترین جواب داشته باشیم، منطقی است که ابتدا راجع به گره ای فکر کنیم که کمترین مقدار  g(n)+h(n)را دارد. پس نتیجه میشود که این استراتژی فراتر از منطقی بودن است، بطوریکه اگر تابع ابتکاری h(n) بعضی از شرایط را برآورده کند، جست وجوی A* کامل و بهینه است.

شرایط بهینگی: قابل قبول بودن و سازگاری الگوریتم های چستوجو

اولین شرط بهینگی این است که  h(n) یک ابتکار قابل قبول باشد. ابتکار قابل قبول آن است که هزینه رسیدن به هدف را هرگز برآورد نکند. چون g(n) هزینه واقعی برای رسیدن به گره n در امتداد مسیر فعلی است و f(n)=g(n)+h(n) ، نتیجه میگیریم که f(n) هرگز هزینه جواب را در امتداد مسیر فعلی از طریق گره n ،زیاد برآورد نمیکند.

ابتکارهای قابل قبول ،ذاتا بهینه هستند، زیرا آنها فکر میکنند که هزینه حل مسئله کمتر از چیزی است که واقعا باید باشد.

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

h(n)<=c(n,a,n’)+h(n’)

 

بهینه بودن الگوریتم جست وجوی A*

A* دارای این خاصیت است: نسخه جست وجوی درختی A* در صورتی بهینه است که  h(n) قابل قبول باشد، درحالیکه نسخه جست وجوی گرافی A* در صورتی بهینه است که h(n) سازگار باشد.

نکته بعدی در مورد این الگوریتم این است که هر وقت A* گره ای را برای بسط انتخاب میکند، مسیر بهینه ای برای آن گره پیدا شده است.

پس نتیجه میشود که دنباله ای از گره ها که توسط A* و با استفاده از جست وجوی گرافی بسط داده میشوند، برحسب f(n) به ترتیب غیرنزولی هستند. بنابراین، اولین گره هدفی که برای بسط انتخاب شد باید یک جواب بهینه باشد، زیرا f هزینه گره های هدف است و تمام گره های هدف بعدی، گرانتر خواهند بود.

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

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