# informed search algorithm

> type of search algorithm in which preliminary information is available (generally heuristic)

**Wikidata**: [Q88775728](https://www.wikidata.org/wiki/Q88775728)  
**Source**: https://4ort.xyz/entity/informed-search-algorithm

## Summary
An informed search algorithm is a type of search algorithm that uses preliminary information—typically a heuristic function—to guide its exploration of a problem space. Unlike uninformed methods, it estimates how close each state is to the goal and prioritizes the most promising paths first.

## Key Facts
- Sub-classified under both “search algorithm” and “heuristic” in knowledge bases.
- Uses a heuristic function to rank candidate states; the heuristic supplies an estimate of remaining cost to goal.
- Aliased as “heuristic search,” “best-first search algorithm,” and in Russian sources as “эвристический поиск” and “информированный поиск.”
- Opposite of an uninformed search algorithm, which has no domain-specific guidance.
- Said to be the same entity as “heuristic search algorithm” in Wikidata.
- Appears in only one Wikipedia language edition (Russian) and holds a single sitelink count.
- Connected algorithms include Greedy Best-First Search, Iterative Deepening A*, Recursive Best-First Search, and memory-bounded variants such as Simplified Memory-Bounded A*.

## FAQs
### Q: How does an informed search algorithm differ from an uninformed one?
A: It adds a heuristic that estimates the cost from the current state to the goal, letting the search prioritize more promising paths. Uninformed methods, like breadth-first or depth-first search, lack this guidance and explore blindly.

### Q: Is a heuristic always correct?
A: No. Heuristics provide approximations; they may underestimate or occasionally mislead, but they still speed up search compared to brute-force methods.

### Q: What is a common example of an informed search algorithm?
A: A* is the best-known example; it combines the actual cost from the start with the heuristic estimate to the goal, guaranteeing an optimal path if the heuristic is admissible.

### Q: Does “best-first search” mean the same thing as informed search?
A: In practice the terms overlap. “Best-first search” usually refers to any search that expands the node appearing best according to an evaluation function, so informed algorithms like A* and Greedy Best-First Search are best-first searches.

## Why It Matters
Informed search algorithms sit at the heart of modern artificial intelligence and operations research because they tame the combinatorial explosion faced by uninformed methods. By folding domain knowledge into a heuristic, they can explore huge state spaces—millions of chess positions, GPS road networks, or robot configuration spaces—in seconds rather than eons. This efficiency underpins everything from turn-by-turn navigation and logistics scheduling to game-playing engines and automated planning. Because the heuristic can be tuned or learned, the same algorithmic skeleton adapts across wildly different problems, giving engineers a reusable toolkit for fast, near-optimal decision making. Without informed search, many real-time AI systems would be computationally infeasible.

## Notable For
- First widely studied family of algorithms to systematically inject heuristic guidance, spawning classics like A* (1968) and IDA* (1985).
- Provides optimality guarantees when the heuristic is admissible, a property not shared by purely greedy methods.
- Memory-bounded variants (e.g., SMA*) allow near-optimal search within fixed RAM, critical for embedded systems.
- Serves as the conceptual bridge between exhaustive uninformed search and modern heuristic optimization techniques such as genetic algorithms.
- Continues to be the backbone of pathfinding in video games, robotics, and global positioning systems.

## Body
### Definition and Taxonomy
An informed search algorithm is any search procedure that exploits problem-specific information—embodied in a heuristic function—to decide which node to expand next. The heuristic maps a state to an estimated cost-to-goal, enabling the algorithm to favor apparently closer states. Within algorithm taxonomies, informed search is simultaneously a subclass of “search algorithm” and of “heuristic,” reflecting its dual nature as both a procedure and an approximation technique.

### Core Variants
- Greedy Best-First Search expands the node with the lowest heuristic value alone; fast but can be misled.
- A* combines g(n), the exact cost from the start, with h(n), the heuristic estimate, producing f(n)=g(n)+h(n); optimal and complete if h is admissible.
- Iterative Deepening A* (IDA*) uses depth-first iterations with an f-cost threshold, achieving A* optimality with linear memory.
- Recursive Best-First Search (RBFS) keeps only the best f-values along the current path, backtracking when necessary.
- Memory-Bounded A* and Simplified Memory-Bounded A* cap storage while sacrificing little optimality.

### Heuristic Properties
An admissible heuristic never overestimates the true remaining cost, ensuring A*’s optimality. A consistent (or monotone) heuristic satisfies the triangle inequality, guaranteeing that f-values along any path are non-decreasing, which speeds up node re-expansion checks. Domain relaxations, pattern databases, and landmark pre-processing are standard ways to derive strong heuristics.

### Applications
Informed search powers GPS route planners, where road-network heuristics use straight-line distance; game AI for real-time strategy pathfinding; robotic motion planning in high-dimensional configuration spaces; and automated puzzle solvers such as the 15-puzzle or Rubik’s cube. Memory-bounded variants run on microcontrollers in drones and vacuum robots.

## Schema Markup
```json
{
  "@context": "https://schema.org",
  "@type": "Thing",
  "name": "informed search algorithm",
  "description": "Type of search algorithm that uses preliminary information, generally a heuristic, to guide exploration.",
  "sameAs": ["https://www.wikidata.org/entity/Q120736698"],
  "additionalType": "https://schema.org/ComputerAlgorithm"
}