A single pass heuristic search method to be included in a stochastic segment based recognizer is presented. Thanks to a novel and efficient implementation of Nilsson's A/A* graph search algorithm, and thanks to the introduction of an appropriate heuristic function, the presented algorithm significantly outperforms the standard Viterbi beam search. Moreover, it was possible to conceive a time-synchronous search (no prior knowledge of the endpoint needed), and to restrict the amount of storage required. As such, the algorithm is extremely suitable for real-time implementation.