*جست وجوی اول بهترین(best-first) مثالی از الگوریتم های Tree searchو Graph search است.
نودها برای گسترش، بر اساس یک تابع ارزیابی مثل [tex]f(n)[/tex] انتخاب می شود، یعنی در هرمرحله گره ای که کم ترین مقدار ارزیابی را دارد برای گسترش انتخاب می شود.
*تابع اکتشافی با [tex]H(n)[/tex] نمایش داده می شود.
هزینه تخمینی ارزان ترین مسیر از حالت n تا هدف [tex]H(n)=[/tex]
* اگر n هدف باشد،آنگاه [tex]H(n)=0[/tex] است.
انواع جست وجوی آگاهانه:
) اول- بهترین حریصانه
)جست و جوی [tex][tex]A^{*}[/tex][/tex] (با استفاده از Tree search وgraph search)
)[tex]RBFS[/tex]
)[tex]SMA^{*}[/tex]
)[tex]IDA^{*}[/tex]
)الگوریتم های جست و جوی محلی
)...
جست و جوی اولین بهترین حریصانهGreedy best-first
* نودی را گسترش می دهد که به هدف نزدیک تر است.
*از روش اول-عمق استفاده می کند.
*این روش، گره ها را فقط بر اساس تابع هیورستیک ارزیابی می کند یعنی [tex]f(n)=h(n)[/tex]
*جست و جوی اول بهترین حریصانه، مانند جست و جوی اول عمق ترجیح می دهد که برای رسیدن به هدف یک مسیر را دنبال کند و در صورتی که به بن بست رسید به بالا برگردد،لذا این روش بهینه و کامل نیست.
*چرا بهینه و کامل نیست؟زیرا ممکن است یک مسیر متناهی به سمت پایین شروع کند و هرگز برای بررسی بقیه برنگردد.
*پیچیدگی مکانی و زمانی آن[tex]O(b^{m})[/tex] که m عمق ماکزیمم فضای حالت است.
*کاهش پیچیدگی به نوع مسئله و کیفیت تابع هیورستیک بستگی دارد.
*تفاوت مهم این روش با روش اول عمق آن است که، در بین فرزندان گره جاری، گره ای انتخاب می شود که کوچک ترین مقدار f را داشته باشد.
جست جوی [tex][tex]A^{*}[/tex][/tex]
* معروف ترین فرم جست و جوی اول -بهترین الگوریتم[tex][tex]A^{*}[/tex][/tex] نامیده می شود اگر[tex]\forall h(n)\leq h^{*}(n)[/tex]
*نحوه ارزیابی گره ها:
[tex]f(n)=g(n) h(n)[/tex]
[tex]f(n)[/tex] = هزینه تخمینی ارزان ترین راه حل از طریق نود n
[tex]g(n)[/tex]= هزینه مسیر از نود شروع تا نود n
[tex]h(n)[/tex]= هزینه تخمینی ارزان ترین مسیر از n تا هدف
*اگر تابع هیورستیک شرایط لازم را داشته باشد، جست و جوی [tex][tex]A^{*}[/tex][/tex] کامل و بهینه است.
پیاده سازی [tex][tex]A^{*}[/tex][/tex] با استفاده از الگوریتم Tree search
*در این مورد [tex][tex]A^{*}[/tex][/tex] زمانی بهینه است که [tex]h(n)[/tex] قابل قبول باشد.
*تابع هیورستیکی در صورتی قابل قبول است که:هرگز هزینه رسیدن به هدف را بیشتر از هزینه واقعی تخمین نزند.
پیاده سازی[tex][tex]A^{*}[/tex][/tex] با استفاده از الگوریتم Graph search
* در چه صورتی تابع هیورستیک سازگار با یکنواست؟ تابع [tex]h(n)[/tex] یکنواست،
اگر [tex]h(n)< C(n,a,n{}') h(n{}')[/tex]
[tex]n{}'[/tex] = با استفاده از عمل a بر روی حالت n تولید شده است.
[tex]C(n,a,n{}')[/tex] =هزینه عمل a را نشان می دهد.
*[tex][tex]A^{*}[/tex][/tex] که با الگوریتم Graph search پیاده سازی می شود، در صورتی بهینه است که [tex]h(n)[/tex] یکنوا باشد.
*اگر[tex]h(n)[/tex] یکنوا باشد، مقادیر[tex]f(n)[/tex] درهر مسیر غیرکاهشی است.
*خصوصیت غیرکاهشی f ، امکان تعریف و ترسیم کانتورها را فراهم می نماید.
*کانتورها متحدالمرکز بوده و در جست و جو با هزینه یکنواخت در اطراف حالت اولیه، حلقوی اند.
* هرچه [tex]h(n)[/tex] به[tex]h^{*}(n)[/tex] نزدیک تر باشد، کانتورها به سمت حالت هدف کشیده شده و در اطراف مسیر بهینه، باریک تر می شود.
چه الگوریتمی امکان پذیر است؟الگوریتمی که کامل و بهینه باشد.
*الگوریتم [tex]A^{*}[/tex] امکان پذیر است.
*شروط امکان پذیری:
۱) فاکتور انشعابb باید متناهی باشد.
۲) وزن(هزینه) تمامی لبه های گراف فضای حالت باید مثبت باشد.(یعنی فاقد گذر تهی و وزن منفی باشد.)
۳)شرط [tex]A^{*}[/tex] [tex]\forall h(n)\leq h^{*}(n)[/tex] برای تمامی گره های گراف برقرار باشد.
*اگرخطای تابع هیورستیک از لگاریتم هزینه واقعی بیشتر نباشد، تعداد نودها در جست و جوی [tex]A^{*}[/tex] رشد نمایی ندارد.
[tex]\left | h(n)-h^{*}(n) \right |\leq O(log h^{*}(n))[/tex]
معایب [tex]A^{*}[/tex]
* نمایی بودن زمان
* از آن جایی که [tex]A^{*}[/tex] تمام نودهای تولید شده را در حافظه نگه می دارد، حافظه ی بسیار زیادی مصرف می کند.به همین دلیل در مسائل کاربردی دشوار، قابل استفاده نیست.
** اگرچه الگوریتم [tex]A^{*}[/tex] امکان پذیر است، ولی ممکن است حین برخورد با گره های قبلا ملاقات شده، مسیر بهتری از مسیر اولیه پیدا شود و این امر منجر به اصلاح مسیر خواهد شد،که این اصلاحات سنگین بوده و با استفاده از خاصیت سازگاری این مشکل حل می شود.
* اگر دو نسخه از الگوریتم [tex]A^{*}[/tex] به نام های[tex]A_{1}^{*}[/tex] و[tex]A_{2}^{*}[/tex] برای حل یک مسئله داشته باشیم، به طوری که [tex]\forall n h_{1}(n)\leq h_{2}(n)[/tex] آنگاه [tex]A_{2}^{*}[/tex] آگاه تر از[tex]A_{1}^{*}[/tex] نامیده می شود.