# best-first search

> algorithm

**Wikidata**: [Q830527](https://www.wikidata.org/wiki/Q830527)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/Best-first_search)  
**Source**: https://4ort.xyz/entity/best-first-search

## Summary
Best-first search is an informed search algorithm used in graph traversal to explore the most promising paths first. It operates by utilizing preliminary information, generally in the form of a heuristic, to estimate the cost of reaching a goal. The algorithm is classified as a graph algorithm and serves as a foundational concept in artificial intelligence.

## Key Facts
- **Classification:** Best-first search is an instance of both a **graph algorithm** and an **informed search algorithm**.
- **Methodology:** It functions using **preliminary information**, generally heuristic data, to guide the search process.
- **Key Relationship:** It is structurally related to **beam search**, which is classified as a heuristic search algorithm.
- **Academic Source:** The algorithm is described and analyzed in the textbook **"Artificial Intelligence: A Modern Approach"** (specifically referenced on page 92).
- **Identifiers:** It holds the Freebase ID `/m/012_wm` and the Dictionary of Algorithms and Data Structures ID `bestfirst`.
- **Global Reach:** The concept is documented across at least 10 Wikipedia language editions, including English, Arabic, German, French, and Japanese.
- **Aliases:** Also known as "recherche best-first" (French), "最良優先搜索" (Chinese), and "Best First Search."

## FAQs
### Q: What type of algorithm is best-first search?
A: Best-first search is an informed search algorithm and a graph algorithm. It distinguishes itself from uninformed searches by using preliminary information—typically heuristics—to make decisions during traversal.

### Q: How is best-first search related to beam search?
A: In the context of algorithm classification, beam search is identified as a related heuristic search algorithm. While best-first search utilizes heuristics to evaluate nodes, beam search acts as a specific heuristic variation that limits the search space.

### Q: Where is best-first search formally documented?
A: The algorithm is a standard topic in computer science literature, notably described in the seminal textbook "Artificial Intelligence: A Modern Approach." It is also indexed in the Dictionary of Algorithms and Data Structures.

## Why It Matters
Best-first search matters because it provides a structured method for navigating complex graphs and problem spaces efficiently. Unlike uninformed (blind) search algorithms that explore without guidance, best-first search leverages heuristic estimates to prioritize paths that appear most likely to reach a goal. This use of "preliminary information" allows for faster problem-solving in scenarios where the entire search space is too large to process exhaustively.

As a core component of artificial intelligence, it represents the bridge between basic graph traversal and advanced problem-solving strategies. Its inclusion in authoritative sources like *Artificial Intelligence: A Modern Approach* underscores its status as a fundamental building block for modern AI systems. By serving as the parent or related class for other techniques like beam search, it establishes the theoretical framework for heuristic optimization used in various applications ranging from pathfinding to machine learning.

## Notable For
- Being a primary example of an **informed search algorithm** that utilizes heuristic data.
- Its inclusion in the standard AI textbook **"Artificial Intelligence: A Modern Approach."**
- Serving as the conceptual foundation or parent class for **beam search**.
- Acting as a versatile **graph algorithm** applicable to various computational problems.
- Its recognition across diverse linguistic and academic platforms, evidenced by multiple aliases and global Wikipedia entries.

## Body
### Algorithmic Classification
Best-first search is defined within computer science as a **graph algorithm** and an **informed search algorithm**. As an informed search method, it differs from blind search techniques by employing an evaluation function to decide which node to expand next. The raw data specifies that this classification relies on the availability of **preliminary information**, which is generally provided by a **heuristic**.

### Relationship to Other Algorithms
The knowledge entry explicitly links best-first search to **beam search**. In the provided hierarchy, beam search is listed as a "Part of / Parent" or related class, defined specifically as a **heuristic search algorithm**. This relationship highlights best-first search as a broader category or structural precursor to more specific heuristic optimization strategies like beam search.

### Academic and Data Identifiers
Best-first search is a well-documented entity across multiple knowledge bases:
- **Literature:** It is described by the source **"Artificial Intelligence: A Modern Approach"**, with specific reference to page 92.
- **Dictionary IDs:** It is indexed as `bestfirst` in the **Dictionary of Algorithms and Data Structures** and holds the **De Agostini ID** `best-first+search`.
- **Database IDs:** The algorithm tracks the discontinued **Microsoft Academic ID** `46011968` and the **Freebase ID** `/m/012_wm`.

### Linguistic Data
The algorithm possesses significant international recognition, documented under various titles such as **"recherche best-first"** and **"最良優先搜索"**. It maintains a presence on Wikipedia across at least 10 languages, including **Arabic, Czech, German, English, Persian, French, Hungarian, Italian, Japanese, and Korean**.

## References

1. Freebase Data Dumps. 2013
2. [OpenAlex](https://docs.openalex.org/download-snapshot/snapshot-data-format)