*جست وجوی اول بهترین(best-first) مثالی از الگوریتم های Tree searchو Graph search است.
نودها برای گسترش، بر اساس یک تابع ارزیابی مثل $f(n)$ انتخاب می شود، یعنی در هرمرحله گره ای که کم ترین مقدار ارزیابی را دارد برای گسترش انتخاب می شود.

*تابع اکتشافی با $H(n)$ نمایش داده می شود.

هزینه تخمینی ارزان ترین مسیر از حالت n تا هدف $H(n)=$

* اگر n هدف باشد،آنگاه $H(n)=0$ است.

---

انواع جست وجوی آگاهانه:

) اول- بهترین حریصانه
)جست و جوی $[tex]A^{*}$[/tex] (با استفاده از Tree search وgraph search)
)$RBFS$
)$SMA^{*}$
)$IDA^{*}$
)الگوریتم های جست و جوی محلی
)...

---

جست و جوی اولین بهترین حریصانهGreedy best-first

* نودی را گسترش می دهد که به هدف نزدیک تر است.
*از روش اول-عمق استفاده می کند.
*این روش، گره ها را فقط بر اساس تابع هیورستیک ارزیابی می کند یعنی $f(n)=h(n)$
*جست و جوی اول بهترین حریصانه، مانند جست و جوی اول عمق ترجیح می دهد که برای رسیدن به هدف یک مسیر را دنبال کند و در صورتی که به بن بست رسید به بالا برگردد،لذا این روش بهینه و کامل نیست.

*چرا بهینه و کامل نیست؟زیرا ممکن است یک مسیر متناهی به سمت پایین شروع کند و هرگز برای بررسی بقیه برنگردد.
*پیچیدگی مکانی و زمانی آن$O(b^{m})$ که m عمق ماکزیمم فضای حالت است.
*کاهش پیچیدگی به نوع مسئله و کیفیت تابع هیورستیک بستگی دارد.
*تفاوت مهم این روش با روش اول عمق آن است که، در بین فرزندان گره جاری، گره ای انتخاب می شود که کوچک ترین مقدار f را داشته باشد.

---

جست جوی $[tex]A^{*}$[/tex]

* معروف ترین فرم جست و جوی اول -بهترین الگوریتم$[tex]A^{*}$[/tex] نامیده می شود اگر$\forall h(n)\leq h^{*}(n)$

*نحوه ارزیابی گره ها:
$f(n)=g(n) h(n)$

$f(n)$ = هزینه تخمینی ارزان ترین راه حل از طریق نود n
$g(n)$= هزینه مسیر از نود شروع تا نود n
$h(n)$= هزینه تخمینی ارزان ترین مسیر از n تا هدف


*اگر تابع هیورستیک شرایط لازم را داشته باشد، جست و جوی $[tex]A^{*}$[/tex] کامل و بهینه است.

---

پیاده سازی $[tex]A^{*}$[/tex] با استفاده از الگوریتم Tree search

*در این مورد $[tex]A^{*}$[/tex] زمانی بهینه است که $h(n)$ قابل قبول باشد.

*تابع هیورستیکی در صورتی قابل قبول است که:هرگز هزینه رسیدن به هدف را بیشتر از هزینه واقعی تخمین نزند.

---

پیاده سازی$[tex]A^{*}$[/tex] با استفاده از الگوریتم Graph search

* در چه صورتی تابع هیورستیک سازگار با یکنواست؟ تابع $h(n)$ یکنواست،
اگر $h(n)< C(n,a,n{}') h(n{}')$

$n{}'$ = با استفاده از عمل a بر روی حالت n تولید شده است.
$C(n,a,n{}')$ =هزینه عمل a را نشان می دهد.

*$[tex]A^{*}$[/tex] که با الگوریتم Graph search پیاده سازی می شود، در صورتی بهینه است که $h(n)$ یکنوا باشد.
*اگر$h(n)$ یکنوا باشد، مقادیر$f(n)$ درهر مسیر غیرکاهشی است.