Наиболее широко известная разновидность поиска по первому наилучшему совпадению называется поиском А* (читается как "А звездочка"). В нем применяется оценка узлов, объединяющая в себе д(п), стоимость достижения данного узла, и h (п), стоимость прохождения от данного узла до цели:

Поскольку функция д(п) позволяет определить стоимость пути от начального узла до узла л, а функция h(n) определяет оценку стоимости наименее дорогостоящего пути от узла п до цели, то справедлива следующая формула:

Таким образом, при осуществлении попытки найти наименее дорогостоящее решение, по-видимому, разумнее всего вначале попытаться проверить узел с наименьшим значением. Как оказалось, данная стратегия является больше чем просто разумной: если эвристическая функция h(n) удовлетворяет некоторым условиям, то поиск А* становится и полным, и оптимальным.

Анализ оптимальности поиска А* является несложным, если этот метод используется в сочетании с алгоритмом Tree-Search. В таком случае поиск А* является оптимальным, при условии, что h (п) представляет собой допустимую эвристическую функцию, т.е. при условии, что h (n) никогда не переоценивает стоимость достижения цели. Допустимые эвристические функции являются по своей сути оптимистическими функциями, поскольку возвращают значения стоимости решения задачи, меньшие по сравнению с фактическими значениями стоимости. А поскольку д(п) — точная стоимость достижения узла л, из этого непосредственно следует, что функция f(n) никогда не переоценивает истинную стоимость достижения решения через узел л.