*جست وجوی اول بهترین(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] درهر مسیر غیرکاهشی است.