جستجوی ابتدا بهترین

**جستجوی ابتدا-بهترین** (best-first search) یک الگوریتم جستجو است که یک  گراف را با بسط دادن محتمل‌ترین راس، که بنابر قوانین خاص انتخاب می‌شود، پیمایش می‌کند.

این نوع جستجو را به عنوان تخمین تعهد نود n به وسیلهٔ heuristic evaluation function  توصیف می‌کند، که به صورت کلی، ممکن است بر پایه توصیف n، توصیف هدف، اطلاعات جمع‌آوری شده به وسیلهٔ جستجو تا آن نقطه و هر گونه اطلاعات اضافی در زمینهٔ مسئله باشد.

بعصی از نویسندگان از جستجوی ابتدا-بهترین به عنوان الگوریتم جستجویی یاد می‌کنند که با استفاده از یک هیوریستیک سعی می‌کند پیش‌بینی کند که انتهای مسیر چقدر به یک راه‌حل نزدیک است. در نتیجه، مسیری که طبق ارزیابی به انتهای مسیر نزدیک‌تر است، زودتر توسعه پیدا کرده و دنبال می‌شود.

الگوریتم جستجوی *A یک نمونه از الگوریتم ابتدا-بهترین است. الگوریتم ابتدا-بهترین معمولاً برای پیدا کردن مسیر در جستجوهای ترکیبی استفاده می‌شود.

## الگوریتم‌ها

```html4strict
OPEN = [initial state]
while OPEN is not empty or until a goal is found
do
 1. Remove the best node from OPEN, call it n.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. Evaluate each successor, add it to OPEN, and record its parent.
done
```

توجه داشته باشید که این نمونه از الگوریتم کامل نیست، همچنین این الگریتم همیشه یک راه را برای دو نقطه پیدا نمی‌کند حتی اگر فقط یک راه وجود داشته باشد. برای مثال، ای داخل یک استگ لوپ می‌افتد اگر به بن بست برسد، که این یک نقطه‌است که جانشین پدر خود می‌شود که ممکن است دوباره به پدرش باز گردد، یک بن بست به لیست اضافه کند و باز به همین شکل. نمونهٔ زیر گسترش می‌دهد برای استفاده از یک لیست بسته‌های اضافی، شامل تمام نقاطی است، ارزیابی شده و دوباره باز بینی نمی‌شود. که باعث پیشگیری از بررسی دوبارهٔ گره می‌شود که آن  منوط به حلقه‌های نامتناهی است.


```html4strict
OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
 1. Remove the best node from OPEN, call it n, add it to CLOSED.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. For each successor do:
       a. If it is not in CLOSED: evaluate it, add it to OPEN, and record its parent.
       b. Otherwise: change recorded parent if this new path is better than previous one.
done
```


توجه کنید که این نسخه الگوریتم کامل نیست یعنی همیشه یک مسیر ممکن بین دو راس را پیدا نمی‌کند حتی اگر چنین مسیری وجود داشته باشد که نسخهٔ کامل ان در زیر امده.

## منابع مرتبط
* الگوریتم جستجوی بیم
* الگوریتم جستجوی A*
* الگوریتم دیکسترا

## منابع

## پیوند به بیرون
* [wikibooks:Artificial Intelligence/Search/Heuristic_search/Best-first_search|Wikibooks: Artificial Intelligence: Best-First Search]
* Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
*http://aima.cs.berkeley.edu/ ^ a b Russell, Stuart J. ; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New] Jersey: Prentice Hall, ISBN 0-13-790395-2. pp.&nbsp;94 and 95 (note 3).
* https://web.archive.org/web/20070601182035/http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html Best First Search
* http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Greedy Best-First Search when EHC Fails, Carnegie Mellon

رده:الگوریتم‌های جستجو