Since the complexity of finding optimal solutions to these problems is generally exponential in practice, in order to solve significantly larger problems, the optimality requirement must be released. An early approach to this problem was the heuristic path algorithm (HPA).
Heuristic path algorithm is a best-first search algorithm, where the figure of merit of node n is f(n) = (1-w)*g(n)+w*h(n). Varying w produces a range of algorithms from uniform-cost search (w=0) through A* (w=1/2) to pure heuristic search (w=1). Increasing w beyond ½ generally decreases the amount of computation while increasing the cost of the solution generated.
The trade off is often quite favorable, with small increases in solution cost yielding huge savings in computation. Moreover, it shows that the solutions found by this algorithm are guaranteed to be no more than a factor of w/(1-w) greater than optimal, but often are significantly better.