# admissible search algorithm > algorithm that is always optimistic; it either underestimates the path cost to the goal or provides a correct estimate for the path cost to the goal, but it never overestimates the path cost to the goal **Wikidata**: [Q130370867](https://www.wikidata.org/wiki/Q130370867) **Source**: https://4ort.xyz/entity/admissible-search-algorithm ## Summary An admissible search algorithm is a type of informed search algorithm designed to be consistently optimistic when evaluating the cost to reach a goal. It is defined by its reliance on an admissible heuristic, ensuring it never overestimates the path cost to the goal. This characteristic means the algorithm's estimated cost is always lower than or equal to the actual cost required to reach the goal state. ## Key Facts - **Definition:** An admissible search algorithm never overestimates the path cost to the goal; it either provides a correct estimate or underestimates the cost. - **Classification:** It is a subclass of the **informed search algorithm**, a category of search algorithms where preliminary information (generally heuristics) is available. - **Core Component:** The algorithm utilizes an **admissible heuristic** to assess the cost of reaching the goal state. - **Heuristic Constraint:** For an algorithm to be admissible, the estimated cost determined by the heuristic must be lower than or equal to the true cost of reaching the goal state. - **Alternative Name:** It is also known as an **admissible algorithm**. - **Key Association:** This concept is fundamentally related to the **A* search algorithm**, which is used for pathfinding and graph traversal. - **Behavioral Trait:** The algorithm is described as "always optimistic" because it assumes the cost to reach the goal will be less than or equal to the reality. ## FAQs ### Q: What makes a search algorithm "admissible"? A: A search algorithm is considered admissible if it never overestimates the cost to reach the goal. This means the estimated path cost it calculates is always less than or equal to the actual cost. ### Q: What is the role of a heuristic in an admissible search algorithm? A: The algorithm uses an "admissible heuristic" to evaluate the cost of reaching the goal state. This heuristic provides the preliminary information necessary to guide the search without breaking the rule of never overestimating the true cost. ### Q: How does an admissible search algorithm relate to the A* search algorithm? A: The A* search algorithm is a specific, widely used instance of an informed search algorithm that utilizes the principles of admissibility for pathfinding and graph traversal. ### Q: Is an admissible search algorithm considered "optimistic"? A: Yes. Because the algorithm must underestimate or correctly guess the path cost—and never overestimate it—it is described as being "always optimistic" regarding the effort required to reach the goal. ## Why It Matters The admissible search algorithm is a critical concept in computer science and artificial intelligence because it provides a guarantee of efficiency and accuracy in problem-solving. By defining strict parameters for cost estimation—specifically the requirement to never overestimate path costs—these algorithms ensure that the search for a goal is optimized. This methodology is foundational for pathfinding and graph traversal, most notably utilized in the A* search algorithm. In practical applications, such as logistics, robotics, and game development, the use of an admissible algorithm ensures that the "optimistic" path is explored first, preventing the algorithm from wasting resources on routes that are clearly more expensive than the estimated best option. By strictly adhering to heuristics that are lower than or equal to true costs, developers can create systems that find the shortest path without unnecessary computation. ## Notable For - Being **"always optimistic"** in its estimation of path costs. - **Never overestimating** the cost to reach the goal state, a strict requirement for its definition. - Serving as the operational logic behind the **A* search algorithm**, a standard for pathfinding. - Strict adherence to the constraint that the **estimated cost must be lower than or equal** to the true cost. - Functioning as a specialized subclass of **informed search algorithms**. ## Body ### Definition and Core Behavior An admissible search algorithm is defined by its specific approach to cost estimation. It operates on the principle of being "always optimistic." In the context of search algorithms, this optimism translates to a guarantee that the algorithm will never estimate a path cost to the goal that is higher than the actual cost. The algorithm functions by either: 1. Underestimating the path cost to the goal. 2. Providing a correct estimate for the path cost to the goal. It explicitly **never overestimates** the path cost. This behavior is essential for ensuring the validity and efficiency of the search process. ### Relationship to Informed Search The admissible search algorithm is classified as a type of **informed search algorithm**. This parent class is characterized by the availability of preliminary information, usually in the form of a heuristic, which helps guide the search process toward the goal more efficiently than uninformed (blind) search methods. ### The Admissible Heuristic The functionality of the algorithm depends on a specific component known as the **admissible heuristic**. This heuristic is responsible for assessing the cost of reaching the goal state. To maintain admissibility, the value produced by this heuristic must satisfy a specific condition: it must be lower than or equal to the true cost of reaching the goal state. ### Application in A* Search The properties of the admissible search algorithm are practically applied in the **A* search algorithm**. A* is a prominent algorithm used for pathfinding and graph traversal that leverages the admissibility condition to efficiently find the shortest path between points. The "admissible algorithm" is effectively the broader classification or alias for the logic that powers such pathfinding tools. ## References 1. [Source](https://www.geeksforgeeks.org/a-is-admissible/)